EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)



Approach 3種類の解き方をパラメータを見てから使い分けました。
  • 焼きなまし法
    • D日後が入力されたgridに近くなるように0日目を焼きなます
    • 実際はD日後ではなく、(D%2==0?2:1)日後で評価した
    • 近傍 : 入力されたgridの生成方法をまねて、ランダムな長方形で上書きする
      • 隣のセルの色を交換するような小さい近傍では過学習した
    • D<=1 または C<=2 または K<=3 のときに使いました
  • 入力されたgridをもう1日進めたもの
    • 色数が少ないときに、1日進めるたびに反転するパターンがあるので
    • 焼きなまし法を使うとき以外で、Dが奇数 かつ C<=4 のときに使いました
  • 入力されたgridをそのまま返す
    • 最小の色が複数ある時、そのセルの色はそのままなので

感想
どこをどれだけよくできるか全くわからない難しい問題だった。
焼きなまし法で過学習や、1を聞いて10を知る(過汎化?)のも見れて面白かった。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class GlowingBacteria {
    private int N;
    private int C;
    private int D0;
    private int D;
    private int K;
    private int[][] truthD;
    private int[][][] prediction;

    static final Watch watch = new Watch();
    static final XorShift rng = new XorShift(System.nanoTime());
    private SAState sa = new SAState();

    private int score;
    private int bestScore;
    private int[][] bestSolution;

    private ArrayList<Integer> dr;
    private ArrayList<Integer> dc;

    public char[] findSolution(int N, int C, int D, int K, char[] grid) {
        init(N, C, D, K, grid);
        solve();
        return makeSolution();
    }

    private void init(int N, int C, int D, int K, char[] grid) {
        this.N = N;
        this.C = C;
        this.D0 = D;
        D = D % 2 == 0 ? 2 : 1;
        this.D = D;
        this.K = K;
        this.truthD = new int[N][N];
        this.prediction = new int[D + 1][N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                truthD[r][c] = grid[r * N + c] - '0';
                prediction[0][r][c] = (int) (C * rng.nextDouble());
            }
        }
        this.bestSolution = new int[N][N];

        dr = new ArrayList<>();
        dc = new ArrayList<>();
        {
            int r = 0;
            int c = 0;
            for (int r2 = -10; r2 <= 10; r2++) {
                for (int c2 = -10; c2 <= 10; c2++) {
                    int dr = Math.abs(r2 - r);
                    int dc = Math.abs(c2 - c);
                    int dist = dr * dr + dc * dc;
                    if (dist > 0 && dist <= K) {
                        this.dr.add(r2);
                        this.dc.add(c2);
                    }
                }
            }
        }
        score = calculateScore();
        bestScore = -1;
        saveBest();
        Utils.debug("D", D0, "N", N, "C", C, "K", K);
    }

    private void solve() {
        if (C <= 2 || D0 <= 1 || K <= 3) {
            SA();
        } else {
            if (D0 % 2 == 1 && C <= 4) {
                this.prediction = new int[2][N][N];
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        this.prediction[0][r][c] = truthD[r][c];
                    }
                }
                int[] counts = new int[C];
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        for (int i = 0; i < C; i++) {
                            counts[i] = 0;
                        }
                        for (int k = 0; k < this.dr.size(); k++) {
                            int dr = this.dr.get(k).intValue();
                            int dc = this.dc.get(k).intValue();
                            if (r + dr < 0 || r + dr >= N || c + dc < 0 || c + dc >= N) {
                                continue;
                            }
                            counts[prediction[0][r + dr][c + dc]]++;
                        }

                        int min = Integer.MAX_VALUE;
                        java.util.List<Integer> vals = new ArrayList<Integer>();

                        for (int i = 0; i < C; i++) {
                            if (counts[i] <= min && counts[i] > 0) {
                                if (counts[i] < min) {
                                    vals.clear();
                                }
                                vals.add(i);
                                min = counts[i];
                            }
                        }
                        if (vals.size() == 1) {
                            bestSolution[r][c] = vals.get(0);
                        } else {
                            bestSolution[r][c] = prediction[0][r][c];
                        }
                    }
                }
            } else {
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        bestSolution[r][c] = truthD[r][c];
                    }
                }
            }
        }
    }

    private void SA() {
        double second = watch.getSecond();
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 3) - 1)) == 0) {
                sa.update();

                if (sa.isTLE()) {
                    loadBest();
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%d", score), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    break;
                }

                if (sa.time > second) {
                    second++;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%d", score), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
            }

            mutate();
        }
    }

    private void mutate() {
        double random = 1 * rng.nextDouble();
        if (random < 1) {
            changeRectUseTruthDColor();
        }
    }

    private void changeRectUseTruthDColor() {
        int r = (int) (N * rng.nextDouble());
        int c = (int) (N * rng.nextDouble());
        int width = rng.nextInt(N / 4) + 1;
        int height = rng.nextInt(N / 4) + 1;

        int r3 = r + (int) (height * rng.nextDouble());
        int c3 = c + (int) (width * rng.nextDouble());
        while (r3 >= N || c3 >= N) {
            r3 = r + (int) (height * rng.nextDouble());
            c3 = c + (int) (width * rng.nextDouble());
        }

        int color = rng.nextDouble() < 0.5 ? truthD[r3][c3] : ((int) (C * rng.nextDouble()));

        boolean update = false;
        int[][] copy = new int[N][N];
        for (int r2 = r; r2 < N && r2 < r + height; r2++)
            for (int c2 = c; c2 < N && c2 < c + width; c2++) {
                if (prediction[0][r2][c2] != color) {
                    update = true;
                }
                copy[r2][c2] = prediction[0][r2][c2];
                prediction[0][r2][c2] = color;
            }
        if (!update) {
            return;
        }

        int deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            for (int r2 = r; r2 < N && r2 < r + height; r2++)
                for (int c2 = c; c2 < N && c2 < c + width; c2++) {
                    prediction[0][r2][c2] = copy[r2][c2];
                }
        }
    }

    private IntList vals = new IntList(10);

    private int[] counts = new int[10];

    private int calculateScore() {
        for (int step = 0; step < D; step++) {
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    for (int i = 0; i < C; i++) {
                        counts[i] = 0;
                    }
                    for (int k = 0; k < this.dr.size(); k++) {
                        int dr = this.dr.get(k).intValue();
                        int dc = this.dc.get(k).intValue();
                        if (r + dr < 0 || r + dr >= N || c + dc < 0 || c + dc >= N) {
                            continue;
                        }
                        counts[prediction[step][r + dr][c + dc]]++;
                    }

                    int min = Integer.MAX_VALUE;
                    vals.clear();

                    for (int i = 0; i < C; i++) {
                        if (counts[i] <= min && counts[i] > 0) {
                            if (counts[i] < min) {
                                vals.clear();
                            }
                            vals.add(i);
                            min = counts[i];
                        }
                    }
                    if (vals.size() == 1) {
                        prediction[step + 1][r][c] = vals.get(0);
                    } else {
                        prediction[step + 1][r][c] = prediction[step][r][c];
                    }
                }
            }
        }
        int score = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (prediction[D][r][c] == truthD[r][c]) {
                    score++;
                }
            }
        }
        return score;
    }

    private char[] makeSolution() {
        char[] res = new char[N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                res[r * N + c] = (char) ((int) ('0') + bestSolution[r][c]);
            }
        }
        return res;
    }

    private void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    bestSolution[r][c] = prediction[0][r][c];
                }
            }
        }
    }

    private void loadBest() {
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            int C = Integer.parseInt(br.readLine());
            int D = Integer.parseInt(br.readLine());
            int K = Integer.parseInt(br.readLine());
            char[] grid = new char[N * N];
            for (int i = 0; i < N * N; i++) {
                grid[i] = br.readLine().charAt(0);
            }
            GlowingBacteria gb = new GlowingBacteria();
            char[] ret = gb.findSolution(N, C, D, K, grid);

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; i++) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;
    public double startTemperature = 1;
    public double endTemperature = 0;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 0;
    public double endRange = 0;
    public double range = startRange;

    public int numIterations;
    public int validIterations;
    public int acceptIterations;

    private double minAbsDeltaScore;
    private double maxAbsDeltaScore;
    private MeanHelper helper = new MeanHelper();

    private static final double[] log = new double[32768];
    static {
        for (int i = 0; i < log.length; i++) {
            log[i] = Math.log((i + 0.5) / log.length);
        }
    }

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;

        minAbsDeltaScore = 1e99;
        maxAbsDeltaScore = 1e-99;
        helper.clear();

        startTime = useTime ? GlowingBacteria.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
        updateRange();
    }

    public boolean useMean = true;
    public boolean useMax = !true;
    public double startRate = 0.01;
    public double endRate = 0.01;
    public boolean useExp = !true;

    public void updateStartTemperature() {
        if (useMean) {
            double d = helper.mean(maxAbsDeltaScore);
            d = d > 0 ? d : maxAbsDeltaScore;
            startTemperature = (-1.0 * d) / Math.log(startRate);
        } else if (useMax) {
            startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

    public void updateEndTemperature() {
        endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
    }

    public void updateTemperature() {
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);

            inverseTemperature = 1.0 / temperature;
        } else {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double temperature = interpolate(startY, endY, time0to1);

            inverseTemperature = 1.0 / temperature;
        }
    }

    private double elapsedPercentage(double min, double max, double v) {
        return (v - min) / (max - min);
    }

    private double interpolate(double v0, double v1, double d0to1) {
        return v0 + (v1 - v0) * d0to1;
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateTime() {
        time = useTime ? GlowingBacteria.watch.getSecond() : numIterations;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        double abs = Math.abs(deltaScore);
        if (abs > 1e-9) {
            helper.add(deltaScore);
            minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
            maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
        }
        return acceptB(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;

        if (deltaScore > -1e-9) {
            acceptIterations++;
            return true;
        }

        assert deltaScore < 0 : Utils.toString(deltaScore);
        assert 1.0 / inverseTemperature >= 0;

        if (deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (log[GlowingBacteria.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

    public boolean acceptS(double deltaScore) {
        validIterations++;

        if (deltaScore < 1e-9) {
            acceptIterations++;
            return true;
        }

        assert deltaScore > 0;
        assert 1.0 / inverseTemperature >= 0;

        if (-deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (log[GlowingBacteria.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        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 Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    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 int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

    public long nextLong() {
        long a = nextInt();
        long b = nextInt();
        return (a << 32) ^ b;
    }

}

class IntList {
    private static final int EMPTY = -1;
    private int[] values;
    private int size;

    public IntList(int capacity) {
        values = new int[capacity];
        clear();
    }

    public void clear() {
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

    public boolean add(int value) {
        values[size++] = value;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int remove(int index) {
        int value = values[index];
        for (int i = index; i + 1 < size; i++) {
            values[i] = values[i + 1];
        }
        size--;
        return value;
    }

    public int removeFast(int index) {
        int value = values[index];
        values[index] = values[size - 1];
        size--;
        return value;
    }

    public int get(int index) {
        return values[index];
    }

    public int set(int index, int value) {
        int oldValue = values[index];
        values[index] = value;
        return oldValue;
    }

    public void add(int index, int value) {
        assert index <= size;
        for (int i = size - 1; i >= index; i--) {
            values[i + 1] = values[i];
        }
        size++;
        values[index] = value;
    }

    public int indexOf(int value) {
        for (int i = 0; i < size; i++) {
            if (values[i] == value) {
                return i;
            }
        }
        return EMPTY;
    }

    public int lastIndexOf(int value) {
        for (int i = size - 1; i >= 0; i--) {
            if (values[i] == value) {
                return i;
            }
        }
        return EMPTY;
    }

}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, double number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        return Math.sqrt(variance(defaultValue));
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}


 


tomerun さんの7 days of a Marathon Competitor は、私がやってるのと違うな~と思ってたら、近いことをやってる人を見つけました。Ponanza の山本さんで、6時間に1つアイデアを考えるがそっくりだった。
私はAWSとか使わないので規模は全然違うけど、”計算資源を有効に使い続けないといけない駆動開発”という感じは同じです。

tomerun さんのスライドと違って、テストはシングルスレッドで行います。そして、できるだけ多くのテストを行っているようにします。今日が何日目っていうのも関係なく、高速化やパラメータチューニングも、新しいbranchが思いつかなければ、いつでも行います。こういう風にやっていると、同時に複数のコンテストに参加できるようになっていきます。っといっても2が限界だけど。

あと、寝ている時間や外出している時間は、パラメータチューニングやアルゴリズム間の誤差レベルの差をはっきりさせるのに使います。大量にテストする時間です。

他には、部屋を掃除するのも
なぜ“汚部屋”のほうがアイデアを出せるか
みたいな記事があるので、コンテストが終わってからの方が良いのでは?



Approach A はビームサーチを使いました。B は貪欲法を使いました。

A
  • 最初の頃MLEになったので、Double-Ended PQ(hogloidさんの4PQ) を使いました。
  • 幅 : 約300
  • 枝狩り : 同じ頂点で次の注文までの時間が800以内ならまとめる
  • 枝狩り : 距離が25以下のところまたは店に移動する
  • スコア : 待ち時間の2乗引くのが本当のスコアだが、貪欲法の気持ちになると、足した方が良いと思って、やってみたら良かった。


B
  • 注文が来たら、巡回セールスマン問題をGuided Local Searchで解いて、店に早く戻ってくるのを繰り返す(スコア : 1410...)
  • 頂点数が400の時、巡回セールスマン問題は戻ってくるまで1200以上かかるが、同じ頂点からの注文は平均600ほどで来る。A では注文をまとめた(後回しにする)けど、逆に早く店に戻るのが良いと分かる。巡回セールスマン問題自体は頑張って解いていて、これより大幅に早く戻ることはできないので、途中で店に寄り道するしかない。(スコア : 1414...)
  • 途中で戻ってくる巡回路を作るために、最初から頂点を2、3のグループに分けた。(スコア : 14169...)
  • 途中で戻ってきたときに、注文が分かるのでその情報を使う。(スコア : 実装間に合わなかった)


感想というか失敗したこと

スコアを合わせるのに時間がかかったけど、上位とは配達できた注文で圧倒的に差がついてたし、A もB も無視して結局本当のスコアを使わなかった。



このページのトップヘ