EvbCFfp1XB

problem and my answer.

一ヶ所変化させるシミュレーテッドアニーリングで885点210位

English と言うか Google Translate
I used simulated annealing which changes one place.
885 points
210th place


source code

    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Scanner;
     
    public class Main {
        private static final TimeManager TIME_MANAGER = new TimeManager();
        private static final XorShift RNG = new XorShift();
     
        private static final int DOT = 0;
        private static final int o = 3;
        private static final int x = 4;
        private static final int PLUS = 1;
        private static final int MINUS = 2;
        private static final int WALL = -1;
     
        public static void main(String[] args) {
            new Main().run();
        }
     
        private int score = 0;
     
        int N = 50;
        int[][] board = new int[N][N];
        int[][] boardRotate = new int[N][N];
        IntArray dots = new IntArray();
        int[][] boardRotateDisappear = new int[N + 2][N + 2];
     
        private void run() {
     
            init();
     
            SA();
     
            printSolution();
     
        }
     
        private void printSolution() {
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    board[N - 1 - j][i] = boardRotate[i][j];
                }
            }
     
            Utils.debug("board");
            print(board);
            Utils.debug("boardRotate");
            print(boardRotate);
            Utils.debug("boardRotateDisappear");
            print(boardRotateDisappear);
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == DOT) {
                        System.out.print('.');
                        continue;
                    }
                    if (board[i][j] == PLUS) {
                        System.out.print('+');
                        continue;
                    }
                    if (board[i][j] == MINUS) {
                        System.out.print('-');
                        continue;
                    }
                    if (board[i][j] == o) {
                        System.out.print('o');
                        continue;
                    }
                    if (board[i][j] == x) {
                        System.out.print('x');
                        continue;
                    }
                }
                System.out.println();
            }
     
        }
     
        private void SA() {
            for (loop = 0, change = 0, ac = 0; !isTimeover(); loop++) {
     
                int before = score;
     
                int v = dots.values[(int) (dots.length * RNG.nextDouble())];
                int r = v >>> 8;
                int c = v & 255;
     
                int current = boardRotate[r][c];
                boardRotate[r][c] = (int) (3 * RNG.nextDouble());
     
                updateDisappear(r);
     
                int after = calculateScore(boardRotateDisappear);
     
                change++;
                if (after >= before || SAaccept(temperature, before, after)) {
                    ac++;
     
                    score = after;
                } else {
                    boardRotate[r][c] = current;
                    updateDisappear(r);
                }
     
            }
        }
     
        private void init() {
            try (Scanner scanner = new Scanner(System.in)) {
                for (int i = 0; i < N; i++) {
                    char[] charArray = scanner.nextLine().toCharArray();
                    for (int j = 0; j < N; j++) {
                        board[i][j] = charArray[j] == '.' ? DOT : charArray[j] == 'o' ? o : x;
                    }
                }
            }
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    boardRotate[i][j] = board[N - 1 - j][i];
                }
            }
     
            Utils.debug("board");
            print(board);
     
            Utils.debug("boardRotate");
            print(boardRotate);
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (boardRotate[i][j] == DOT) {
                        dots.add((i << 8) | (j));
                    }
                }
            }
     
            for (int i = 0; i < N + 2; i++) {
                for (int j = 0; j < N + 2; j++) {
                    boardRotateDisappear[i][j] = WALL;
                }
            }
            for (int i = 0; i < N; i++) {
                updateDisappear(i);
            }
     
            Utils.debug("boardRotateDisappear");
            print(boardRotateDisappear);
     
        }
     
        private void print(int[][] board2) {
            for (int i = 0; i < board2.length; i++) {
                for (int j = 0; j < board2[i].length; j++) {
                    if (board2[i][j] == WALL) {
                        System.err.print(' ');
                        continue;
                    }
                    if (board2[i][j] == DOT) {
                        System.err.print('.');
                        continue;
                    }
                    if (board2[i][j] == PLUS) {
                        System.err.print('+');
                        continue;
                    }
                    if (board2[i][j] == MINUS) {
                        System.err.print('-');
                        continue;
                    }
                    if (board2[i][j] == o) {
                        System.err.print('o');
                        continue;
                    }
                    if (board2[i][j] == x) {
                        System.err.print('x');
                        continue;
                    }
                }
                System.err.println();
            }
        }
     
        private void updateDisappear(int i) {
            int j2 = 0;
            for (int j = 0; j < N; j++) {
                if (boardRotate[i][j] == DOT) {
                    continue;
                }
                if (boardRotate[i][j] == MINUS) {
                    for (; j2 < j; j2++) {
                        boardRotateDisappear[i + 1][1 + j2] = WALL;
                    }
                    boardRotateDisappear[i + 1][1 + j2++] = boardRotate[i][j];
                    continue;
                }
                if (boardRotate[i][j] == PLUS || boardRotate[i][j] == o || boardRotate[i][j] == x) {
                    boardRotateDisappear[i + 1][1 + j2++] = boardRotate[i][j];
                    continue;
                }
            }
            for (; j2 < N; j2++) {
                boardRotateDisappear[i + 1][1 + j2] = WALL;
            }
        }
     
        private static final int[] dr = new int[] { -1, 0, 0, 1, };
        private static final int[] dc = new int[] { 0, -1, 1, 0, };
     
        int[][] used = new int[N][N];
        int countCalculateScore = 0;
     
        private int calculateScore(int[][] boardRotateDisappear) {
            countCalculateScore++;
     
            int scoreO = 0;
            int scoreX = 0;
            LinkedList queue = new LinkedList<>();
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (used[r][c] == countCalculateScore) {
                        continue;
                    }
     
                    if (boardRotateDisappear[r][c] == o || boardRotateDisappear[r][c] == x) {
     
                    } else {
                        continue;
                    }
     
                    queue.add((1 << 16) | (r << 8) | c);
                    used[r][c] = countCalculateScore;
     
                    for (; !queue.isEmpty();) {
                        int v = queue.pollFirst();
                        int count = (v >>> 16) & ((1 << 16) - 1);
                        int r2 = (v >>> 8) & 255;
                        int c2 = v & 255;
     
                        if (boardRotateDisappear[r2][c2] == o) {
                            scoreO = Math.max(scoreO, count);
                        }
                        if (boardRotateDisappear[r2][c2] == x) {
                            scoreX = Math.max(scoreX, count);
                        }
     
                        for (int d = 0; d < dr.length; d++) {
                            int nextR = r2 + dr[d];
                            int nextC = c2 + dc[d];
     
                            if (nextR < 0 || nextR >= N) {
                                continue;
                            }
                            if (nextC < 0 || nextC >= N) {
                                continue;
                            }
                            if (used[nextR][nextC] == countCalculateScore) {
                                continue;
                            }
                            if (boardRotateDisappear[nextR][nextC] != boardRotateDisappear[r2][c2]) {
                                continue;
                            }
     
                            queue.add(((count + 1) << 16) | (nextR << 8) | nextC);
                            used[nextR][nextC] = countCalculateScore;
                        }
                    }
                }
            }
            return scoreO + scoreX;
        }
     
        private boolean SAaccept(double temperature, double score, double newScore) {
            boolean accept = RNG.nextDouble() < StrictMath.exp(-(score - newScore) / temperature);
            return accept;
        }
     
        private static final boolean useTime = true;
     
        private double startTime = 0;
        private double endTime = 10.0 * 0.95;
        private double time = startTime;
     
        private double startTemperature = 3.15;
        private static final double endTemperature = 0;
        private double temperature = startTemperature;
     
        private int loop = 0;
        private int change;
        private int ac;
     
        private static final int mask = (1 << 10) - 1;
     
        private boolean isTimeover() {
            if ((loop & mask) != 0) {
                return false;
            }
     
            time = useTime ? TIME_MANAGER.getSecond() : loop;
     
            if (time >= endTime) {
                return true;
            }
     
            temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
     
            if ((loop & mask) != 0) {
            } else {
                Utils.debug(String.format("loop, %8d, change, %5.2f, AC, %5.2f, temperature, %5.2f, score, %10d, time, %s", loop, 100.0 * change / loop, 100.0 * ac / change, temperature, score, TIME_MANAGER.getSecondString()));
            }
     
            return false;
        }
     
    }
     
    final class Utils {
        private Utils() {
        }
     
        public static final void debug(Object... o) {
            System.err.println(toString(o));
        }
     
        public static final String toString(Object... o) {
            return Arrays.deepToString(o);
        }
     
    }
     
    class IntArray {
        public int[] values;
        public int length;
     
        public IntArray() {
            this(new int[4], 0);
        }
     
        public IntArray(int capacity) {
            this(new int[capacity], 0);
        }
     
        public IntArray(int[] values) {
            this(values, values.length);
        }
     
        public IntArray(int[] values, int length) {
            this.values = values;
            this.length = length;
        }
     
        public void add(int value) {
            if (length == values.length) {
                values = Arrays.copyOf(values, values.length << 1);
            }
            values[length++] = value;
        }
     
        public int remove() {
            return values[--length];
        }
     
        public boolean contains(int value) {
            for (int i = 0; i < length; i++) {
                if (values[i] == value) {
                    return true;
                }
            }
            return false;
        }
     
        public void clear() {
            length = 0;
        }
     
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            for (int i = 0; i < length; i++) {
                sb.append(values[i] + ",");
            }
            sb.append("}");
            return sb.toString();
        }
     
        public boolean isEmpty() {
            return length == 0;
        }
     
        public int remove(int index) {
            if (index >= length) {
                throw new AssertionError();
            }
     
            if (index == length - 1) {
                return remove();
            }
     
            int res = values[index];
            System.arraycopy(values, index + 1, values, index, length - (index + 1));
            length--;
     
            return res;
        }
     
        public void set(int index, int value) {
            if (index >= length) {
                throw new AssertionError();
            }
     
            if (length >= values.length - 1) {
                values = Arrays.copyOf(values, values.length << 1);
            }
            System.arraycopy(values, index, values, index + 1, length - index);
            length++;
     
            values[index] = value;
        }
     
        public IntArray copy() {
            return new IntArray(Arrays.copyOf(values, length), length);
        }
     
        public int[] toArray() {
            return Arrays.copyOf(values, length);
        }
     
    }
     
    class TimeManager {
        private long start;
        private int count;
     
        public TimeManager() {
            init();
        }
     
        public int getCount() {
            return count;
        }
     
        public double getSecond() {
            count++;
            return (System.nanoTime() - start) * 1e-9;
        }
     
        public long getTime() {
            count++;
            return System.nanoTime() - start;
        }
     
        public void init() {
            init(System.nanoTime());
        }
     
        public void init(long start) {
            this.start = start;
            count = 0;
        }
     
        public String toString() {
            return toString(getSecond());
        }
     
        public String getSecondString() {
            return toString(getSecond());
        }
     
        public static final String toString(double second) {
            if (second < 60) {
                return String.format("%5.2fs", second);
            } else if (second < 60 * 60) {
                int minute = (int) (second / 60);
                return String.format("%2dm%2ds", minute, (int) (second % 60));
            } else {
                int hour = (int) (second / (60 * 60));
                int minute = (int) (second / 60);
                return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
            }
        }
     
    }
     
    class XorShift {
        private static final double toDouble = 1.0 / 2147483648.0;
        private int w = 88675123;
        private int x = 123456789;
        private int y = 362436069;
        private int z = 521288629;
        private int count = 0;
     
        public XorShift() {
            x = (int) System.nanoTime();
        }
     
        public XorShift(long l) {
            x = (int) l;
        }
     
        public int getCount() {
            return count;
        }
     
        public double nextDouble() {
            return (nextInt() & Integer.MAX_VALUE) * toDouble;
        }
     
        public int nextInt() {
            count++;
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
            return w;
        }
     
        public int nextInt(int n) {
            return (int) (n * nextDouble());
        }
     
        public long nextLong() {
            long a = nextInt();
            long b = nextInt();
            return (a << 32) ^ b;
        }
     
    }



一つのセルを2*2(seed2)から11*11(seed1)のサブセルに分割する。
ライトを置く位置は、サブセルの頂点のみとして、ライトの位置に対する、照らすことのできるサブセルを覚えておく。
Simulated Annealing でライトの置く位置を最適化する。



いつ guess するか
  • 1位と2位の一致した色の数の差が2より大きくなったとき
  • 9秒以上経ったとき
  • 1位が10回以上単独首位になったとき


どこを look するか

単独首位がいるとき

  • 1位と2位の一致した色の数の差を大きく出来そうな所(2位グループと一致した色の数が最も少ない所)


それ以外

  • 1位グループをどれだけ散けさせられるかをエントロピー(分類のランダムフォレストなどで出てくるもの)で評価した(エントロピーが大きい方が良い)。
  • 各場所の評価を次のように計算する。1位グループからその場所(4ヶ所)の期待される色を求める。色が反転する確率を0.2として、
     16通りの(期待される色から変化する確率*エントロピー)の和
    を各場所の評価とする。
  • breadth first search で近い方から見ていって、評価が0より大きくなった距離以下で最大の所を look する。


このページのトップヘ