EvbCFfp1XB

problem and my answer.



Approach

  • 本質的に同じ解が異なるスコアになるので、ローカルのテストは、スコアの計算を1万回して、平均を使いました。
  • ソルバーでは128回の平均を使っていました。
  • 5-0-5 のシステムを使いました。
  • Forward と Defender のそれぞれ30人の優先順位を焼き鈍しました。(10のラインナップに30人全員登場させても良いので)
  • スコアの計算中に出てきた有効そうなラインナップの情報を焼き鈍しの近傍に使いました。(でも効果は誤差レベル)


source code

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

public class WorldCupLineup {
    private static final int numTests = 128;
    private static final char[] positionNames = new char[] { 'F', 'M', 'D' };
    private static final int[] atkCoefficient = { 2, 1, 0, };
    private static final int[] defCoefficient = { 0, 1, 2, };

    private int numPlayers;
    private int numGroups;
    private int numLineups;

    private Player[] players;
    private Group[] groups;

    private double score;
    private int[] lineupIndexToPositionIndex;
    private ArrayList[] lineupIndexToPlayerIndexes;

    private double bestScore;
    private int[] bestLineupIndexToPositionIndex;
    private ArrayList[] bestLineupIndexToPlayerIndexes;

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

    public String[] selectPositions(String[] players, String[] groups) {
        init(players, groups);
        solve();
        Utils.debug("countUseBest", countUseBest);
        return makeSolution();
    }

    private void init(String[] players, String[] groups) {
        this.numPlayers = 30;
        this.players = new Player[numPlayers];
        for (int i = 0; i < numPlayers; i++) {
            String[] split = players[i].split(",");
            int atk = Integer.parseInt(split[0]);
            int def = Integer.parseInt(split[1]);
            int agg = Integer.parseInt(split[2]);
            this.players[i] = new Player(atk, def, agg);
        }

        this.numGroups = groups.length;
        this.groups = new Group[numGroups];
        for (int i = 0; i < numGroups; i++) {
            String[] split = groups[i].split(" ");

            ArrayList players2 = new ArrayList<>();
            {
                String[] split0 = split[0].split(",");
                for (int j = 0; j < split0.length; j++) {
                    players2.add(Integer.parseInt(split0[j]));
                }
            }

            int set = 0;
            for (Integer playerIndex : players2) {
                set |= (1 << playerIndex.intValue());
            }

            {
                String[] split1 = split[1].split(",");
                int atk = Integer.parseInt(split1[0]);
                int def = Integer.parseInt(split1[1]);
                int agg = Integer.parseInt(split1[2]);
                this.groups[i] = new Group(atk, def, agg, players2, set);
            }
        }

        this.numLineups = 10;
        lineupIndexToPositionIndex = new int[numLineups];
        lineupIndexToPlayerIndexes = new ArrayList[positionNames.length];
        for (int i = 0; i < lineupIndexToPlayerIndexes.length; i++) {
            lineupIndexToPlayerIndexes[i] = new ArrayList<>();
        }
        bestLineupIndexToPositionIndex = new int[numLineups];
        bestLineupIndexToPlayerIndexes = new ArrayList[positionNames.length];
        for (int i = 0; i < bestLineupIndexToPlayerIndexes.length; i++) {
            bestLineupIndexToPlayerIndexes[i] = new ArrayList<>();
        }

        Utils.debug("init", "time", watch.getSecondString());
    }

    private void solve() {
        random();
        SA();
    }

    private void random() {
        for (int positionIndex = 0; positionIndex < 5; positionIndex++) {
            lineupIndexToPositionIndex[positionIndex] = 0;
        }
        for (int positionIndex = 5; positionIndex < numLineups; positionIndex++) {
            lineupIndexToPositionIndex[positionIndex] = 2;
        }
        for (int playerIndex = 0; playerIndex < numPlayers; playerIndex++) {
            lineupIndexToPlayerIndexes[0].add(playerIndex);
            lineupIndexToPlayerIndexes[1].add(playerIndex);
            lineupIndexToPlayerIndexes[2].add(playerIndex);
        }

        score = calculateScore();
        bestScore = 0;
        saveBest();

        Utils.debug("random", "time", watch.getSecondString(), "score", score);
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());

        sa.startTime = watch.getSecond();
        sa.endTime = 9.5;
        sa.init();
        for (;; sa.numIterations++) {
            if ((sa.numIterations & ((1 << 5) - 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("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    break;
                }

                if (watch.getSecond() > 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("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
            }

            mutate();
        }

        Utils.debug("SA", "time", watch.getSecondString());
    }

    private void mutate() {
        if (bestOut.size() + bestIn.size() > 0) {
            countUseBest++;
            useBest();
            bestIn.clear();
            bestOut.clear();
        } else {
            swapPlayerInSamePosition();
        }
    }

    private void useBest() {

        ArrayList copy = new ArrayList<>();
        copy.addAll(lineupIndexToPlayerIndexes[0]);
        ArrayList copy2 = new ArrayList<>();
        copy2.addAll(lineupIndexToPlayerIndexes[2]);

        for (Integer out : bestOut) {
            int positionIndex = lineupIndexToPositionIndex[out.intValue() >>> 16];
            int playerIndex = out.intValue() & ((1 << 16) - 1);
            ArrayList playerIndexes = lineupIndexToPlayerIndexes[positionIndex];
            Integer remove = playerIndexes.remove(playerIndexes.indexOf(playerIndex));
            playerIndexes.add(remove);
        }

        bestIn.clear();
        bestOut.clear();

        double deltaScore = calculateScore() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            lineupIndexToPlayerIndexes[0].clear();
            lineupIndexToPlayerIndexes[0].addAll(copy);
            lineupIndexToPlayerIndexes[2].clear();
            lineupIndexToPlayerIndexes[2].addAll(copy2);
        }
    }

    private void swapPlayerInSamePosition() {
        int positionIndex = (int) (2 * rng.nextDouble());
        if (positionIndex == 1) {
            positionIndex = 2;
        }

        ArrayList playerIndexes = lineupIndexToPlayerIndexes[positionIndex];
        int index0 = (int) (playerIndexes.size() * rng.nextDouble());
        int index1 = (int) ((playerIndexes.size() - 1) * rng.nextDouble());
        if (index1 >= index0) {
            index1++;
        }

        playerIndexes.set(index0, playerIndexes.set(index1, playerIndexes.get(index0)));

        double deltaScore = calculateScore() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            playerIndexes.set(index0, playerIndexes.set(index1, playerIndexes.get(index0)));
        }
    }

    private boolean[] done = new boolean[30];
    private boolean[] carded = new boolean[30];
    private int[] lineup = new int[10];
    private int[] lineupInverse = new int[30];

    private int bestLineup = 0;
    private ArrayList bestIn = new ArrayList<>();
    private ArrayList bestOut = new ArrayList<>();

    private double calculateScore() {
        bestLineup = 0;
        bestIn.clear();
        bestOut.clear();

        double sum = 0;
        for (int test = 0; test < numTests; test++) {

            Arrays.fill(done, false);
            Arrays.fill(carded, false);
            for (int i = 0; i < 10; i++) {
                lineup[i] = -1;
            }

            ArrayList in = new ArrayList<>();
            ArrayList out = new ArrayList<>();

            int totalScore = 0;

            int createCurrentLineup1 = createCurrentLineup();
            totalScore += createCurrentLineup1;

            if (createCurrentLineup1 > bestLineup) {
                bestLineup = createCurrentLineup1;
                bestIn.clear();
                bestIn.addAll(in);
                bestOut.clear();
                bestOut.addAll(out);
            }

            int numOuts = processLineup(out);

            int createCurrentLineup2;
            if (numOuts > 0) {
                createCurrentLineup2 = createCurrentLineup(in);
            } else {
                createCurrentLineup2 = createCurrentLineup1;
            }
            totalScore += createCurrentLineup2;

            if (createCurrentLineup2 > bestLineup) {
                bestLineup = createCurrentLineup2;
                bestIn.clear();
                bestIn.addAll(in);
                bestOut.clear();
                bestOut.addAll(out);
            }

            numOuts = processLineup(out);

            int createCurrentLineup3;
            if (numOuts > 0) {
                createCurrentLineup3 = createCurrentLineup(in);
            } else {
                createCurrentLineup3 = createCurrentLineup2;
            }
            totalScore += createCurrentLineup3;

            if (createCurrentLineup3 > bestLineup) {
                bestLineup = createCurrentLineup3;
                bestIn.clear();
                bestIn.addAll(in);
                bestOut.clear();
                bestOut.addAll(out);
            }

            numOuts = processLineup(out);

            int createCurrentLineup4;
            if (numOuts > 0) {
                createCurrentLineup4 = createCurrentLineup(in);
            } else {
                createCurrentLineup4 = createCurrentLineup3;
            }
            totalScore += createCurrentLineup4;

            if (createCurrentLineup4 > bestLineup) {
                bestLineup = createCurrentLineup4;
                bestIn.clear();
                bestIn.addAll(in);
                bestOut.clear();
                bestOut.addAll(out);
            }

            numOuts = processLineup(out);

            int createCurrentLineup5;
            if (numOuts > 0) {
                createCurrentLineup5 = createCurrentLineup(in);
            } else {
                createCurrentLineup5 = createCurrentLineup4;
            }
            totalScore += createCurrentLineup5;

            if (createCurrentLineup5 > bestLineup) {
                bestLineup = createCurrentLineup5;
                bestIn.clear();
                bestIn.addAll(in);
                bestOut.clear();
                bestOut.addAll(out);
            }

            totalScore = Math.max(0, totalScore);

            sum += totalScore;
        }
        return sum / numTests;
    }

    private int[] calcAtk = new int[10];
    private int[] calcDef = new int[10];
    private int[] calcAgg = new int[10];

    private int createCurrentLineup() {
        for (int i = 0; i < 10; i++) {
            if (lineup[i] > -1)
                continue;
            int index = lineupIndexToPositionIndex[i];
            ArrayList players = lineupIndexToPlayerIndexes[index];
            for (int j = 0; j < players.size(); j++) {
                if (!done[players.get(j).intValue()]) {
                    lineup[i] = players.get(j).intValue();
                    done[lineup[i]] = true;
                    lineupInverse[lineup[i]] = i;
                    break;
                }
            }
        }

        for (int i = 0; i < 10; i++) {
            if (lineup[i] == -1) {
                calcAtk[i] = calcDef[i] = calcAgg[i] = 0;
                continue;
            }
            calcAgg[i] = players[lineup[i]].agg;
            calcAtk[i] = atkCoefficient[lineupIndexToPositionIndex[i]] * players[lineup[i]].atk;
            calcDef[i] = defCoefficient[lineupIndexToPositionIndex[i]] * players[lineup[i]].def;
        }

        int set = 0;
        for (int i = 0; i < lineup.length; i++) {
            if (lineup[i] == -1) {
                continue;
            }
            set |= (1 << lineup[i]);
        }

        for (int i = 0; i < numGroups; i++) {
            if ((groups[i].set & set) == groups[i].set) {
            } else {
                continue;
            }
            for (int j = 0; j < groups[i].players.size(); j++) {
                int p = lineupInverse[groups[i].players.get(j).intValue()];
                calcAgg[p] += groups[i].agg;
                calcAtk[p] += atkCoefficient[lineupIndexToPositionIndex[p]] * groups[i].atk;
                calcDef[p] += defCoefficient[lineupIndexToPositionIndex[p]] * groups[i].def;
            }
        }

        int totalAtk = 0;
        int totalDef = 0;
        for (int i = 0; i < 10; i++) {
            totalAtk += calcAtk[i];
            totalDef += calcDef[i];
        }
        return Math.min(totalAtk, totalDef);
    }

    private int createCurrentLineup(ArrayList in) {
        for (int i = 0; i < 10; i++) {
            if (lineup[i] > -1)
                continue;
            int index = lineupIndexToPositionIndex[i];
            ArrayList players = lineupIndexToPlayerIndexes[index];
            for (int j = 0; j < players.size(); j++) {
                if (!done[players.get(j).intValue()]) {
                    lineup[i] = players.get(j).intValue();
                    done[lineup[i]] = true;
                    lineupInverse[lineup[i]] = i;
                    in.add((i << 16) | (lineup[i]));
                    break;
                }
            }
        }

        for (int i = 0; i < 10; i++) {
            if (lineup[i] == -1) {
                calcAtk[i] = calcDef[i] = calcAgg[i] = 0;
                continue;
            }
            calcAgg[i] = players[lineup[i]].agg;
            calcAtk[i] = atkCoefficient[lineupIndexToPositionIndex[i]] * players[lineup[i]].atk;
            calcDef[i] = defCoefficient[lineupIndexToPositionIndex[i]] * players[lineup[i]].def;
        }

        int set = 0;
        for (int i = 0; i < lineup.length; i++) {
            if (lineup[i] == -1) {
                continue;
            }
            set |= (1 << lineup[i]);
        }

        for (int i = 0; i < numGroups; i++) {
            if ((groups[i].set & set) == groups[i].set) {
            } else {
                continue;
            }
            for (int j = 0; j < groups[i].players.size(); j++) {
                int p = lineupInverse[groups[i].players.get(j).intValue()];
                calcAgg[p] += groups[i].agg;
                calcAtk[p] += atkCoefficient[lineupIndexToPositionIndex[p]] * groups[i].atk;
                calcDef[p] += defCoefficient[lineupIndexToPositionIndex[p]] * groups[i].def;
            }
        }

        int totalAtk = 0;
        int totalDef = 0;
        for (int i = 0; i < 10; i++) {
            totalAtk += calcAtk[i];
            totalDef += calcDef[i];
        }
        return Math.min(totalAtk, totalDef);
    }

    private static final double injuryRate = 0.05;

    private int processLineup(ArrayList out) {
        int count = 0;
        for (int i = 0; i < 10; i++) {
            if (lineup[i] == -1)
                continue;
            if (rng.nextDouble() < injuryRate) {
                out.add((i << 16) | lineup[i]);
                lineup[i] = -1;
                count++;
                continue;
            }
            if ((int) (100 * rng.nextDouble()) < calcAgg[i]) {
                if (carded[lineup[i]]) {
                    out.add((i << 16) | lineup[i]);
                    lineup[i] = -1;
                    count++;
                } else {
                    carded[lineup[i]] = true;
                }
            }
        }
        return count;
    }

    private String[] makeSolution() {
        String[] res = new String[numLineups];
        for (int lineupIndex = 0; lineupIndex < numLineups; lineupIndex++) {
            StringBuilder sb = new StringBuilder();
            sb.append(positionNames[lineupIndexToPositionIndex[lineupIndex]] + " ");
            for (int i = 0; i < lineupIndexToPlayerIndexes[lineupIndexToPositionIndex[lineupIndex]].size(); i++) {
                if (i > 0) {
                    sb.append(",");
                }
                sb.append(lineupIndexToPlayerIndexes[lineupIndexToPositionIndex[lineupIndex]].get(i).intValue());
            }
            res[lineupIndex] = sb.toString();
        }
        return res;
    }

    private void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            for (int i = 0; i < numLineups; i++) {
                bestLineupIndexToPositionIndex[i] = lineupIndexToPositionIndex[i];
            }
            for (int i = 0; i < 3; i++) {
                bestLineupIndexToPlayerIndexes[i].clear();
                bestLineupIndexToPlayerIndexes[i].addAll(lineupIndexToPlayerIndexes[i]);
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int i = 0; i < numLineups; i++) {
            lineupIndexToPositionIndex[i] = bestLineupIndexToPositionIndex[i];
        }
        for (int i = 0; i < 3; i++) {
            lineupIndexToPlayerIndexes[i].clear();
            lineupIndexToPlayerIndexes[i].addAll(bestLineupIndexToPlayerIndexes[i]);
        }
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            String[] players = new String[Integer.parseInt(br.readLine())];
            for (int i = 0; i < players.length; ++i) {
                players[i] = br.readLine();
            }

            String[] groups = new String[Integer.parseInt(br.readLine())];
            for (int i = 0; i < groups.length; ++i) {
                groups[i] = br.readLine();
            }

            WorldCupLineup sol = new WorldCupLineup();
            String[] ret = sol.selectPositions(players, groups);

            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 Player {
    int atk;
    int def;
    int agg;

    public Player(int atk, int def, int agg) {
        super();
        this.atk = atk;
        this.def = def;
        this.agg = agg;
    }

}

class Group {
    int atk;
    int def;
    int agg;
    ArrayList players;
    int set;

    public Group(int atk, int def, int agg, ArrayList players, int set) {
        super();
        this.atk = atk;
        this.def = def;
        this.agg = agg;
        this.players = players;
        this.set = set;
    }
}

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);
    }

    public static final boolean isValid(int v, int min, int minUpper) {
        return v >= min && v < minUpper;
    }

}

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 long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

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

}

class SAState {
    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;

    public double startTemperature = 30;
    public double endTemperature = 0;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 31;
    public double endRange = 3;
    public double range = startRange;

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

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

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

        update();
        lastAcceptTemperature = inverseTemperature;
    }

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

    public void updateTemperature() {
        inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
    }

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

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

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

    public boolean accept(double deltaScore) {
        return acceptB(deltaScore);
    }

    public boolean acceptB(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 (WorldCupLineup.rng.nextDouble() < Math.exp(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 (WorldCupLineup.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

}




Approach

SAを使いました。

複数の点の位置を決める問題に+αした問題(最近だと CirclesMix, HHMM2nd, 山型足し算, stick_xor, ...)にもSAがよく使われます。上位の人たちでも点数に差がついて、いい問題であることが多いです。私もSAより貪欲法のほうが良くなったりして、力不足だと思わされるのもこのタイプの問題(CirclesMix等)です。


温度

10 から 1.25 に線形に減らす。


近傍

  • 物を置く
  • 物を移動する
  • 物を取り除く
  • Lantern を強制的に置く(競合している Lantern があったら取り除く)
    • 競合しているせいで、最適化出来てないことがあったので。
  • Incorrect な Crystal を選んで、余計な色の Lantern を取り除いて、必要な色の Lantern を置こうとする
    • 2色の Crystal は、1色だけ合ってる時は色無しの時よりスコアが悪いので、2色同時に揃えるようにすることで対策した。
      • ”Incorrect な Crystal を選んで、Lantern の位置を変えて、Correct になるまで”を1回の遷移とするSAも試したけど、調整不足だったのか、あまり Correct になってなかった。

高速化

tomerunさんの記事(北大日立新概念マラソンでやった高速化色々)がまとまってます。

  • 動的メモリは確保しない
    • 2倍高速化
    • 最初はメモリのことはあまり気にしなかったので、大変効果が有りました。
  • 除算・剰余算を取り除く
    • 観察する限り効果なし
  • スコア差分計算のために現在の値を保持
    • 試してないです
    • Crystal ごとに出来たかも
  • ビット並列化
    • 試してないです
  • メモリサイズを減らす
    • 試してないです
  • 座標を1次元に潰す
    • 20%高速化
  • 番兵で条件判定を取り除く
    • 観察する限り効果なし
  • 焼きなまし受理判定の枝刈り
    • 最初から使ってた
  • ループアンローリング
    • 試してないです
    • 4方向に ray を出してたので、使えました。
  • BFSで来た方向に戻る移動をしない
    • BFSを使っていない
  • 0〜N-1から異なる2つをランダムに選ぶときのテク
    • 異なる2つを選ぶ機会がなかった


source code

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

public class CrystalLighting {
private IntSet currentRays = new IntSet(128 * 128 * 16);

private static final int blue = 1;
private static final int yellow = 2;
private static final int red = 4;
private static final int obstacle = 7;
private static final int empty = 0;
private static final int mirror1 = 8;
private static final int mirror2 = 9;
private static final int wall = 10;

private int[] objects;
private IntList[] rays;
private IntList updateRays = new IntList(128 * 128 * 4);

private IntSet emptySet;
private IntSet objectSet;
private IntSet crystalSet;
private IntSet incorrectCrystalSet;

private IntList bestObjects;

private int H;
private int W;
private static final int maxW = 128;
private int[] board;
private int costLantern;
private int costMirror;
private int costObstacle;
private int maxMirrors;
private int maxObstacles;

private static final int[] dz = { -128, -1, 1, 128, };

private int usedLantern;
private int usedObstacles;
private int usedMirrors;

private int numCorrects1;
private int numCorrects2;
private int numIncorrects;

private IntList conflictPoints = new IntList(2);
private IntList availableDirections = new IntList(4);

private IntList removes;
private IntList adds;
private IntList points;

private int[] typeLanterns = new int[] { blue, yellow, red, };
private int[] typeNotLanterns = new int[] { obstacle, mirror1, mirror2, };
private int[] typeObstacles = new int[] { obstacle, };
private int[] typeNotObstacles = new int[] { blue, yellow, red, mirror1, mirror2, };
private int[] typeMirrors = new int[] { mirror1, mirror2, };
private int[] typeNotMirrors = new int[] { blue, yellow, red, obstacle, };
private int[] types = new int[] { blue, yellow, red, obstacle, mirror1, mirror2, };

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

public String[] placeItems(String[] targetBoard, int costLantern, int costMirror, int costObstacle, int maxMirrors, int maxObstacles) {
init(targetBoard, costLantern, costMirror, costObstacle, maxMirrors, maxObstacles);
solve();
return makeResult();
}

private void init(String[] targetBoard, int costLantern, int costMirror, int costObstacle, int maxMirrors, int maxObstacles) {
initBoard(targetBoard, costLantern, costMirror, costObstacle, maxMirrors, maxObstacles);
Utils.debug("init", "H", H, "W", W, "costLantern", costLantern, "costMirror", costMirror, "costObstacle", costObstacle, "maxMirrors", maxMirrors, "maxObstacles", maxObstacles, "time", watch.getSecondString());
}

private void solve() {
SA();
}

private void SA() {
score = getScore();
bestScore = 0;
saveBest();

sa.startTime = watch.getSecond();
sa.endTime = 9.5;
sa.init();
for (;; sa.numIterations++) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();

if (sa.isTLE()) {
loadBest();
break;
}
}

mutate();
}

Utils.debug("numIterations", sa.numIterations);
Utils.debug("SA", "time", watch.getSecondString());
printNumbers();
}

private void mutate() {
int random = (int) (6 * rng.nextDouble());
if (random < 1) {
remove();
} else if (random < 2) {
move();
} else if (random < 3) {
add();
} else if (random < 4) {
forceAdd();
} else if (random < 5) {
match3color();
} else if (random < 6) {
forceAdd();
}
}

private void add() {
if (emptySet.isEmpty()) {
return;
}

int z = emptySet.get((int) (emptySet.size() * rng.nextDouble()));
int type;
if (getRays(z).size() > 0) {
if (usedObstacles >= maxObstacles) {
if (usedMirrors >= maxMirrors) {
return;
} else {
type = typeMirrors[(int) (typeMirrors.length * rng.nextDouble())];
}
} else {
if (usedMirrors >= maxMirrors) {
type = typeObstacles[(int) (typeObstacles.length * rng.nextDouble())];
} else {
type = typeNotLanterns[(int) (typeNotLanterns.length * rng.nextDouble())];
}
}
} else {
type = typeLanterns[(int) (typeLanterns.length * rng.nextDouble())];
}

if (!canAdd(z, type)) {
return;
}

updateRays.clear();
double deltaScore = simulateAdd(z, type);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
add(z, type);
saveBest();
}
}

private void forceAdd() {
if (emptySet.isEmpty()) {
return;
}

int z = emptySet.get((int) (emptySet.size() * rng.nextDouble()));
assert getBoard(z) == empty && getObject(z) == empty;

if (getRays(z).size() == 0) {
int type = typeLanterns[(int) (typeLanterns.length * rng.nextDouble())];

if (!canAdd(z, type)) {
return;
}

updateRays.clear();
double deltaScore = simulateAdd(z, type);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
add(z, type);
saveBest();
}

return;
}

int type;
if (usedObstacles >= maxObstacles) {
if (usedMirrors >= maxMirrors) {
type = typeLanterns[(int) (typeLanterns.length * rng.nextDouble())];
} else {
type = typeNotObstacles[(int) (typeNotObstacles.length * rng.nextDouble())];
}
} else {
if (usedMirrors >= maxMirrors) {
type = typeNotMirrors[(int) (typeNotMirrors.length * rng.nextDouble())];
} else {
type = types[(int) (types.length * rng.nextDouble())];
}
}

if (type == blue || type == yellow || type == red) {
IntList conflicts = conflictPoints;
conflicts.clear();
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
int encode = encode(z(ray), getObject(z(ray)));
if (!conflicts.contains(encode)) {
conflicts.add(encode);
}
}

for (int i = 0; i < conflicts.size(); i++) {
int conflict = conflicts.get(i);
remove(z(conflict));
}

if (!canAdd(z, type)) {
for (int i = 0; i < conflicts.size(); i++) {
int conflict = conflicts.get(i);
add(z(conflict), typeOrDirection(conflict));
}
return;
}

double deltaScore0 = getScore() - score;

updateRays.clear();
double deltaScore = deltaScore0 + simulateAdd(z, type);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
add(z, type);
saveBest();
} else {
for (int i = 0; i < conflicts.size(); i++) {
int conflict = conflicts.get(i);
add(z(conflict), typeOrDirection(conflict));
}
}
} else {
if (!canAdd(z, type)) {
return;
}

updateRays.clear();
double deltaScore = simulateAdd(z, type);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
add(z, type);
saveBest();
}
}

}

private void match3color() {
if (incorrectCrystalSet.isEmpty()) {
return;
}
int z = incorrectCrystalSet.get((int) (incorrectCrystalSet.size() * rng.nextDouble()));
assert !isCorrect(z);

if (availableDirections(z) < Integer.bitCount(getBoard(z))) {
return;
}

int color = getColor(z);
int crystalColor = getBoard(z);

removes.clear();
adds.clear();

points.clear();
for (int d = 0; d < dz.length; d++) {
search(z, d, points);
}
if (points.size() == 0) {
return;
}

for (int diffColor = color ^ crystalColor; diffColor > 0; diffColor -= Integer.lowestOneBit(diffColor)) {
int lowestColor = Integer.lowestOneBit(diffColor);
if ((crystalColor & lowestColor) == 0) {
for (int i = 0; i < 4; i++) {
if (getRays(z).size() == 0) {
break;
}
int ray = getRays(z).get((int) (getRays(z).size() * rng.nextDouble()));
int z2 = z(ray);
if (getObject(z2) == lowestColor) {
if (canRemove(z2)) {
int type = remove(z2);
removes.add(encode(z2, type));
break;
}
}
}
} else {
for (int i = 0; i < 3; i++) {
int p = points.get((int) (points.size() * rng.nextDouble()));
int z2 = p;
if (canAdd(z2, lowestColor)) {
add(z2, lowestColor);
adds.add(encode(z2, lowestColor));
break;
}
}
}
}

if (adds.size() == 0 && removes.size() == 0) {
return;
}

double deltaScore = getScore() - score;

if (sa.accept(deltaScore)) {
score += deltaScore;
saveBest();
} else {
for (int i = 0; i < adds.size(); i++) {
int add = adds.get(i);
remove(z(add));
}
for (int i = 0; i < removes.size(); i++) {
int remove = removes.get(i);
add(z(remove), typeOrDirection(remove));
}
}

}

private int availableDirections(int z) {
int count = 0;
for (int d = 0; d < dz.length; d++) {
int nz = z + dz[d];
if (isWall(nz)) {
continue;
}

if (getBoard(nz) == empty) {
count++;
}
}
return count;
}

private void move() {
if (objectSet.isEmpty()) {
return;
}

int z = objectSet.get((int) (objectSet.size() * rng.nextDouble()));

availableDirections.clear();
for (int d = 0; d < dz.length; d++) {
int newZ = z + dz[d];
if (isWall(newZ)) {
continue;
}
if (getBoard(newZ) != empty) {
continue;
}
if (getObject(newZ) != empty) {
continue;
}
availableDirections.add(d);
}
if (availableDirections.isEmpty()) {
return;
}

if (!canRemove(z)) {
return;
}

int type = remove(z);
double deltaScore0 = getScore() - score;

int d = availableDirections.get((int) (availableDirections.size() * rng.nextDouble()));
int newZ = z + dz[d];
if (!canAdd(newZ, type)) {
add(z, type);
return;
}

updateRays.clear();
double deltaScore = deltaScore0 + simulateAdd(newZ, type);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
add(newZ, type);
saveBest();
} else {
add(z, type);
}
}

private void search(int z0, int d0, IntList points) {
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}

if (z == z0) {
break;
}
if (isLantern(z)) {
continue;
}
if (isCrystal(z)) {
break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
continue;
} else if (getObject(z) == mirror2) {
d ^= 2;
continue;
}

points.add(z);
}
}

private boolean isCorrect(int z) {
assert isCrystal(z);
return getColor(z) == getBoard(z);
}

private int getColor(int z) {
int color = 0;
for (int i = 0; i < getRays(z).size(); i++) {
color |= getObject(z(getRays(z).get(i)));
}
return color;
}

private void remove() {
if (objectSet.isEmpty()) {
return;
}

int z = objectSet.get((int) (objectSet.size() * rng.nextDouble()));

if (!canRemove(z)) {
return;
}

updateRays.clear();
double deltaScore = simulateRemove(z);
back();

if (sa.accept(deltaScore)) {
score += deltaScore;
remove(z);
saveBest();
}
}

private void back() {
for (int i = updateRays.size() - 1; i >= 0; i -= 3) {
int v3 = updateRays.get(i);
int v2 = updateRays.get(i - 1);
int v = updateRays.get(i - 2);
if (v > 0) {
getRays(v2).remove(getRays(v2).indexOf(v3));
} else {
getRays(v2).add(v3);
}
}
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
bestObjects.clear();
for (int i = 0; i < objectSet.size(); i++) {
int z = objectSet.get(i);
bestObjects.add(encode(z, getObject(z)));
}
}
}

private void loadBest() {
score = bestScore;

for (int i = objectSet.size() - 1; i >= 0; i--) {
int z = objectSet.get(i);
if (isLantern(z)) {
remove(z);
}
}
for (int i = objectSet.size() - 1; i >= 0; i--) {
int z = objectSet.get(i);
if (!isLantern(z)) {
remove(z);
}
}

for (int i = 0; i < bestObjects.size(); i++) {
int v = bestObjects.get(i);
int z = z(v);
int type = typeOrDirection(v);

if (type == blue || type == yellow || type == red) {
} else {
add(z, type);
}
}
for (int i = 0; i < bestObjects.size(); i++) {
int v = bestObjects.get(i);
int z = z(v);
int type = typeOrDirection(v);

if (type == blue || type == yellow || type == red) {
add(z, type);
} else {
}
}
}

private void initBoard(String[] targetBoard, int costLantern, int costMirror, int costObstacle, int maxMirrors, int maxObstacles) {
this.H = targetBoard.length;
this.W = targetBoard[0].length();
this.board = new int[(H + 2) * maxW];
Arrays.fill(this.board, wall);
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
char charAt = targetBoard[r].charAt(c);
int z = getZ(r + 1, c + 1);
if (charAt == '1') {
setBoard(z, blue);
} else if (charAt == '2') {
setBoard(z, yellow);
} else if (charAt == '3') {
setBoard(z, blue + yellow);
} else if (charAt == '4') {
setBoard(z, red);
} else if (charAt == '5') {
setBoard(z, blue + red);
} else if (charAt == '6') {
setBoard(z, yellow + red);
} else if (charAt == 'X') {
setBoard(z, obstacle);
} else if (charAt == '.') {
setBoard(z, empty);
}
}
}

objects = new int[(H + 2) * maxW];
rays = new IntList[(H + 2) * maxW];
for (int i = 0; i < rays.length; i++) {
rays[i] = new IntList(4);
}
this.costLantern = -costLantern;
this.costMirror = -costMirror;
this.costObstacle = -costObstacle;
this.maxMirrors = maxMirrors;
this.maxObstacles = maxObstacles;

emptySet = new IntSet((H + 2) * maxW);
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
int z = getZ(r + 1, c + 1);
if (getBoard(z) == empty) {
emptySet.add(z);
}
}
}

objectSet = new IntSet((H + 2) * maxW);

crystalSet = new IntSet((H + 2) * maxW);
incorrectCrystalSet = new IntSet((H + 2) * maxW);
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
int z = getZ(r + 1, c + 1);
if (isCrystal(z)) {
crystalSet.add(z);
incorrectCrystalSet.add(z);
}
}
}

bestObjects = new IntList((H + 2) * maxW);

removes = new IntList((H + 2) * maxW);
adds = new IntList((H + 2) * maxW);
points = new IntList((H + 2) * maxW);

}

private int getBoard(int z) {
return board[z];
}

private int setBoard(int z, int v) {
return board[z] = v;
}

private IntList getRays(int z) {
return rays[z];
}

private int getObject(int z) {
return objects[z];
}

private void setObject(int z, int v) {
objects[z] = v;
}

private int getScore() {
return numCorrects1 * 20 + numCorrects2 * 30 + numIncorrects * -10 + usedLantern * costLantern + usedObstacles * costObstacle + usedMirrors * costMirror;
}

private boolean canAdd(int z, int type) {
if (!(getBoard(z) == empty && getObject(z) == empty)) {
return false;
}
if (type == obstacle) {
if (usedObstacles >= maxObstacles) {
return false;
}
assert getObject(z) == empty;
setObject(z, type);
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
if (!isValidRay(z(ray), typeOrDirection(ray))) {
setObject(z, empty);
return false;
}
}
setObject(z, empty);
return true;
} else if (type == mirror1 || type == mirror2) {
if (usedMirrors >= maxMirrors) {
return false;
}
assert getObject(z) == empty;
setObject(z, type);
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
if (!isValidRay(z(ray), typeOrDirection(ray))) {
setObject(z, empty);
return false;
}
}
setObject(z, empty);
return true;
} else if (type == blue || type == yellow || type == red) {
if (getRays(z).size() > 0) {
return false;
}

assert getObject(z) == empty;
setObject(z, type);

for (int d = 0; d < dz.length; d++) {
if (!isValidRay(z, d)) {
setObject(z, empty);
return false;
}
}
setObject(z, empty);
return true;
}
throw new AssertionError();
}

private boolean canRemove(int z) throws AssertionError {
int type = getObject(z);
if (type == empty) {
return false;
}
if (type == blue || type == yellow || type == red) {
return true;
} else if (type == obstacle || type == mirror1 || type == mirror2) {
setObject(z, empty);
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
if (!isValidRay(z(ray), typeOrDirection(ray))) {
setObject(z, type);
return false;
}
}
setObject(z, type);
return true;
}
throw new AssertionError();
}

private void add(int z, int type) throws AssertionError {
if (type == blue || type == yellow || type == red) {
setObject(z, type);
emptySet.removeValue(z);
objectSet.add(z);
usedLantern++;

for (int d = 0; d < dz.length; d++) {
addRay(z, d);
}
} else if (type == obstacle || type == mirror1 || type == mirror2) {
currentRays.clear();
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
currentRays.add(ray);
}

for (int i = 0; i < currentRays.size(); i++) {
int ray = currentRays.get(i);
removeRay(z(ray), typeOrDirection(ray));
}

setObject(z, type);
emptySet.removeValue(z);
objectSet.add(z);
if (type == obstacle) {
usedObstacles++;
} else {
usedMirrors++;
}

for (; currentRays.size() > 0;) {
int ray = currentRays.get(0);
currentRays.remove(0);
addRay(z(ray), typeOrDirection(ray));
}
} else {
throw new AssertionError(Utils.toString("type", type));
}
}

private int remove(int z) throws AssertionError {
int type = getObject(z);
if (type == blue || type == yellow || type == red) {
for (int d = 0; d < dz.length; d++) {
removeRay(z, d);
}

setObject(z, empty);
emptySet.add(z);
objectSet.removeValue(z);
usedLantern--;
} else if (type == obstacle || type == mirror1 || type == mirror2) {
currentRays.clear();
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
currentRays.add(ray);
}

for (int i = 0; i < currentRays.size(); i++) {
int ray = currentRays.get(i);
removeRay(z(ray), typeOrDirection(ray));
}

setObject(z, empty);
emptySet.add(z);
objectSet.removeValue(z);
if (type == obstacle) {
usedObstacles--;
} else {
usedMirrors--;
}

for (; currentRays.size() > 0;) {
int ray = currentRays.get(0);
currentRays.remove(0);
addRay(z(ray), typeOrDirection(ray));
}

} else {
throw new AssertionError(Utils.toString("type", type));
}
return type;
}

private int simulateAdd(int z, int type) throws AssertionError {
if (type == blue || type == yellow || type == red) {
int deltaScore = 0;

assert getObject(z) == empty;

setObject(z, type);

deltaScore += costLantern;
for (int d = 0; d < dz.length; d++) {
deltaScore += simulateAddRay2(z, d);
}

setObject(z, empty);

return deltaScore;
} else if (type == obstacle || type == mirror1 || type == mirror2) {
int deltaScore = 0;

assert getObject(z) == empty;

currentRays.clear();
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
currentRays.add(ray);
}

for (int i = 0; i < currentRays.size(); i++) {
int ray = currentRays.get(i);
deltaScore += simulateRemoveRay2(z(ray), typeOrDirection(ray));
}

setObject(z, type);

if (type == obstacle) {
deltaScore += costObstacle;
} else {
deltaScore += costMirror;
}

for (; currentRays.size() > 0;) {
int ray = currentRays.get(0);
currentRays.remove(0);
deltaScore += simulateAddRay2(z(ray), typeOrDirection(ray));
}

setObject(z, empty);

return deltaScore;
} else {
throw new AssertionError(Utils.toString("type", type));
}
}

private int simulateRemove(int z) throws AssertionError {
int type = getObject(z);
if (type == blue || type == yellow || type == red) {
int deltaScore = 0;

for (int d = 0; d < dz.length; d++) {
deltaScore += simulateRemoveRay2(z, d);
}

deltaScore += -costLantern;

return deltaScore;
} else if (type == obstacle || type == mirror1 || type == mirror2) {
int deltaScore = 0;

currentRays.clear();
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
currentRays.add(ray);
}

for (int i = 0; i < currentRays.size(); i++) {
int ray = currentRays.get(i);
deltaScore += simulateRemoveRay2(z(ray), typeOrDirection(ray));
}

setObject(z, empty);

if (type == obstacle) {
deltaScore += -costObstacle;
} else {
deltaScore += -costMirror;
}

for (; currentRays.size() > 0;) {
int ray = currentRays.get(0);
currentRays.remove(0);
deltaScore += simulateAddRay2(z(ray), typeOrDirection(ray));
}

setObject(z, type);

return deltaScore;
} else {
throw new AssertionError(Utils.toString("type", type));
}
}

private boolean isValidRay(int z0, int d0) {
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}
if (z == z0) {
return false;
}
if (isLantern(z)) {
return false;
}
if (isCrystal(z)) {
break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
} else if (getObject(z) == mirror2) {
d ^= 2;
}
}
return true;
}

private void addRay(int z0, int d0) {
int value = encode(z0, d0);
assert value == encode(getR(z0), getC(z0), d0);
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}

assert !isLantern(z);

getRays(z).add(value);
if (isCrystal(z)) {
int color = 0;
for (int i = 0; i < getRays(z).size() - 1; i++) {
int ray = getRays(z).get(i);
color |= getObject(z(ray));
}

int bitCount = Integer.bitCount(getBoard(z));
if (color == getBoard(z)) {
if (bitCount == 1) {
numCorrects1--;
} else {
numCorrects2--;
}
} else {
if (color == 0) {
} else {
numIncorrects--;
}
}

{
int ray = getRays(z).get(getRays(z).size() - 1);
color |= getObject(z(ray));
}

if (color == getBoard(z)) {
if (bitCount == 1) {
numCorrects1++;
} else {
numCorrects2++;
}
incorrectCrystalSet.removeValue(z);
} else {
if (color == 0) {
} else {
numIncorrects++;
}
incorrectCrystalSet.add(z);
}
break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
} else if (getObject(z) == mirror2) {
d ^= 2;
}

}
}

private int simulateAddRay2(int z0, int d0) {
int deltaScore = 0;
int value = encode(z0, d0);
assert value == encode(getR(z0), getC(z0), d0);
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}

assert !isLantern(z);
if (isCrystal(z)) {
getRays(z).add(value);
updateRays.add(1);
updateRays.add(z);
updateRays.add(value);

int color = 0;
for (int i = 0; i < getRays(z).size() - 1; i++) {
int ray = getRays(z).get(i);
color |= getObject(z(ray));
}

int bitCount = Integer.bitCount(getBoard(z));
if (color == getBoard(z)) {
if (bitCount == 1) {
deltaScore += -20;
} else {
deltaScore += -30;
}
} else {
if (color == 0) {
} else {
deltaScore += 10;
}
}

{
assert z0 == z(value);
color |= getObject(z0);
}

if (color == getBoard(z)) {
if (bitCount == 1) {
deltaScore += 20;
} else {
deltaScore += 30;
}
} else {
if (color == 0) {
} else {
deltaScore += -10;
}
}

break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
} else if (getObject(z) == mirror2) {
d ^= 2;
}

}
return deltaScore;
}

private void removeRay(int z0, int d0) {
int value = encode(z0, d0);
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}

assert !isLantern(z) : Utils.toString("nr, nc", getR(z), getC(z));

int indexOf = getRays(z).indexOf(value);
getRays(z).removeFast(indexOf);
if (isCrystal(z)) {

int color = 0;
for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
color |= getObject(z(ray));
}

int bitCount = Integer.bitCount(getBoard(z));
if (color == getBoard(z)) {
if (bitCount == 1) {
numCorrects1++;
} else {
numCorrects2++;
}
incorrectCrystalSet.removeValue(z);
} else {
if (color == 0) {
} else {
numIncorrects++;
}
incorrectCrystalSet.add(z);
}

{
color |= getObject(z0);
}

if (color == getBoard(z)) {
if (bitCount == 1) {
numCorrects1--;
} else {
numCorrects2--;
}
} else {
if (color == 0) {
} else {
numIncorrects--;
}
}

break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
} else if (getObject(z) == mirror2) {
d ^= 2;
}

}
}

private int simulateRemoveRay2(int z0, int d0) {
int deltaScore = 0;
int value = encode(z0, d0);
int d = d0;
int z = z0;
for (;;) {
z += dz[d];
if (isWall(z)) {
break;
}

assert !isLantern(z) : Utils.toString("nr, nc", getR(z), getC(z));
if (isCrystal(z)) {
int indexOf = getRays(z).indexOf(value);
int removedRay = getRays(z).removeFast(indexOf);
updateRays.add(-1);
updateRays.add(z);
updateRays.add(removedRay);

int color = 0;

for (int i = 0; i < getRays(z).size(); i++) {
int ray = getRays(z).get(i);
color |= getObject(z(ray));
}

int bitCount = Integer.bitCount(getBoard(z));
if (color == getBoard(z)) {
if (bitCount == 1) {
deltaScore += 20;
} else {
deltaScore += 30;
}
} else {
if (color == 0) {
} else {
deltaScore += -10;
}
}

{
color |= getObject(z0);
}

if (color == getBoard(z)) {
if (bitCount == 1) {
deltaScore += -20;
} else {
deltaScore += -30;
}
} else {
if (color == 0) {
} else {
deltaScore += 10;
}
}

break;
}
if (isObstacle(z)) {
break;
}
if (getObject(z) == mirror1) {
d ^= 1;
} else if (getObject(z) == mirror2) {
d ^= 2;
}

}
return deltaScore;
}

private boolean isWall(int z) {
return getBoard(z) == wall;
}

private boolean isObstacle(int z) {
return getBoard(z) == obstacle || getObject(z) == obstacle;
}

private boolean isCrystal(int z) {
return getBoard(z) >= 1 && getBoard(z) <= 6;
}

private boolean isLantern(int z) {
return getObject(z) == blue || getObject(z) == yellow || getObject(z) == red;
}

private static final int getZ(int r, int c) {
return (r << 7) | c;
}

private static final int getR(int z) {
return z >>> 7;
}

private static final int getC(int z) {
return z & 127;
}

private static final int encode(int r, int c, int type) {
return (r << 11) | (c << 4) | (type);
}

private static final int encode(int z, int type) {
return (z << 4) | (type);
}

private static final int z(int v) {
return v >>> 4;
}

private static final int typeOrDirection(int v) {
return v & 15;
}

private void printNumbers() {
Utils.debug("score", getScore(), "Lan", usedLantern, "Obs", usedObstacles, "Mir", usedMirrors, "Co1", numCorrects1, "Co2", numCorrects2, "Inc", numIncorrects);
}

private String[] makeResult() {
ArrayList<String> res = new ArrayList<>();
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
int z = getZ(r + 1, c + 1);
if (getObject(z) != empty) {
char ch;
if (getObject(z) == blue || getObject(z) == yellow || getObject(z) == red) {
ch = (char) (getObject(z) + '0');
} else if (getObject(z) == obstacle) {
ch = 'X';
} else if (getObject(z) == mirror1) {
ch = '\\';
} else if (getObject(z) == mirror2) {
ch = '/';
} else {
throw new AssertionError();
}
res.add("" + r + " " + c + " " + ch);
}
}
}

return (String[]) res.toArray(new String[res.size()]);
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int H = Integer.parseInt(br.readLine());
String[] targetBoard = new String[H];
for (int i = 0; i < H; ++i) {
targetBoard[i] = br.readLine();
}
int costLantern = Integer.parseInt(br.readLine());
int costMirror = Integer.parseInt(br.readLine());
int costObstacle = Integer.parseInt(br.readLine());

int maxMirrors = Integer.parseInt(br.readLine());
int maxObstacles = Integer.parseInt(br.readLine());

CrystalLighting cl = new CrystalLighting();
String[] ret = cl.placeItems(targetBoard, costLantern, costMirror, costObstacle, maxMirrors, maxObstacles);
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 = 10;
public double endTemperature = 1.25;
public double inverseTemperature = 1.0 / startTemperature;
public double startRange = 31;
public double endRange = 3;
public double range = startRange;

public int numIterations;

public void init() {
numIterations = 0;
startTime = useTime ? CrystalLighting.watch.getSecond() : numIterations;

update();
}

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

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

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

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

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

public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}

public boolean acceptB(double deltaScore) {
if (deltaScore > -1e-9) {
return true;
}

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

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (CrystalLighting.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
if (deltaScore < 1e-9) {
return true;
}

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

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (CrystalLighting.rng.nextDouble() < Math.exp(-deltaScore * 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);
}

public static final boolean isValid(int v, int min, int minUpper) {
return v >= min && v < minUpper;
}

}

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 long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

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

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

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

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

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

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

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

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

}

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 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;
}

}


source code

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Collections;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class StickXorVis {

private static final int minL = 1;
private static final int maxL = 25;

private int N = 60;
private int K = 500;
private int[] L;

private SecureRandom rnd;

private int[][] A;

private long seed;
private int score;

private void generate(String seedStr) {
try {
rnd = SecureRandom.getInstance("SHA1PRNG");
seed = Long.parseLong(seedStr);
rnd.setSeed(seed);

L = new int[K];
for (int i = 0; i < L.length; i++) {
L[i] = rnd.nextInt(maxL - minL + 1) + minL;
}

A = new int[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
A[r][c] = rnd.nextDouble() < 0.5 ? 0 : 1;
}
}

} catch (Exception e) {
addFatalError("An exception occurred while generating test case.");
e.printStackTrace();
}
}

public double runTest(String seed) {
try {
generate(seed);

if (proc == null) {
return -1;
}

int[][] stickXor;
try {
stickXor = getSolution(N, K, L, A);
} catch (Exception e) {
addFatalError("Failed to get result from getSolution.");
return -1.0;
}

for (int i = 0; i < stickXor.length; i++) {
for (int j = 0; j < stickXor[i].length; j++) {
if (stickXor[i][j] < 0 || stickXor[i][j] >= N) {
addFatalError("You can only make stickXor inside the area.");
return -1.0;
}
}
if (!(stickXor[i][0] == stickXor[i][2] || stickXor[i][1] == stickXor[i][3])) {
addFatalError("stickXor is invalid shape.");
return -1.0;
}
}

int score0 = calculateScore();

score = calculateScore() - score0;

drawer = null;
if (vis) {
drawer = new Drawer();
}

ArrayList<Pair<Integer, Integer>> pairs = new ArrayList<>();
for (int k = 0; k < K; k++) {
pairs.add(new Pair<Integer, Integer>(L[k], k));
}
Collections.sort(pairs);

for (int k = 0; k < K; k++) {
int i = pairs.get(k).second.intValue();
flip(stickXor[i][0], stickXor[i][1], stickXor[i][2], stickXor[i][3]);

if (vis) {

score = calculateScore() - score0;

numSticks = k + 1;

drawer.repaint();
try {
Thread.sleep(100);
} catch (Exception e) {
}
}
}

score = calculateScore() - score0;

return score;

} catch (Exception e) {
addFatalError("An exception occurred while trying to get your program's results.");
e.printStackTrace();
return -1.0;
}
}

private int calculateScore() {
int score = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (A[r][c] == 0) {
score++;
}
}
}
return score;
}

private void flip(int startR, int startC, int endR, int endC) {
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
A[r][c] ^= 1;
}
}
}

private static String exec;
private static boolean vis, debug;
private static Process proc;
private InputStream is;
private OutputStream os;
private BufferedReader br;

private int[][] getSolution(int N, int K, int[] L, int[][] A) throws IOException {
StringBuffer sb = new StringBuffer();
sb.append(N).append(" ").append(K).append("\n");
for (int i = 0; i < L.length; ++i) {
sb.append(L[i]).append(" ");
}
sb.append("\n");
for (int i = 0; i < A.length; ++i) {
for (int j = 0; j < A[i].length; ++j) {
sb.append(A[i][j]);
}
sb.append("\n");
}
os.write(sb.toString().getBytes());
os.flush();

int[][] ret = new int[K][4];
for (int i = 0; i < K; i++) {
String[] split = br.readLine().split(" ");
for (int j = 0; j < 4; j++) {
ret[i][j] = Integer.parseInt(split[j]) - 1;
}
}
return ret;
}

public StickXorVis(String seed) {
try {
if (exec != null) {
try {
Runtime rt = Runtime.getRuntime();
proc = rt.exec(exec);
os = proc.getOutputStream();
is = proc.getInputStream();
br = new BufferedReader(new InputStreamReader(is));
new ErrorReader(proc.getErrorStream()).start();
} catch (Exception e) {
e.printStackTrace();
}
}
System.out.println("Score = " + runTest(seed));
stopSolution();
} catch (Exception e) {
e.printStackTrace();
}
}

private void stopSolution() {
if (proc != null) {
try {
proc.destroy();
} catch (Exception e) {
e.printStackTrace();
}
}
}

private Drawer drawer;
private int numSticks;

class Drawer extends JFrame {
public static final int EXTRA_WIDTH = 300;
public static final int EXTRA_HEIGHT = 30;

public DrawerPanel panel;

public int cellSize, boardSize;
public int width, height;

class DrawerPanel extends JPanel {

public void paint(Graphics g) {

BufferedImage bi = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
Graphics2D g2 = (Graphics2D) bi.getGraphics();
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

g2.setColor(Color.LIGHT_GRAY);
g2.fillRect(0, 0, width, height);

for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (A[r][c] == 0) {
g2.setColor(Color.WHITE);
} else {
g2.setColor(Color.BLACK);
}
g2.fillRect(15 + cellSize * c, 15 + cellSize * r, cellSize, cellSize);
}
}

g2.setColor(Color.BLUE);
for (int i = 0; i <= boardSize; i++) {
g2.drawLine(15 + i * cellSize, 15, 15 + i * cellSize, 15 + cellSize * boardSize);
g2.drawLine(15, 15 + i * cellSize, 15 + cellSize * boardSize, 15 + i * cellSize);
}

g2.setColor(Color.BLACK);
g2.setFont(new Font("Arial", Font.BOLD, 12));

int x = 40 + boardSize * cellSize;
int y = 30;

g2.drawString("Seed : " + seed, x, y += 15);
g2.drawString("numRectangles : " + (numSticks + "/" + 500), x, y += 15);
g2.drawString("Score : " + score, x, y += 15);

g.drawImage(bi, 0, 0, width, height, null);
}
}

class DrawerWindowListener extends WindowAdapter {
public void windowClosing(WindowEvent event) {
stopSolution();
System.exit(0);
}
}

public Drawer() {
super();

panel = new DrawerPanel();
getContentPane().add(panel);

addWindowListener(new DrawerWindowListener());

boardSize = N;
this.cellSize = 8;
width = cellSize * boardSize + EXTRA_WIDTH;
height = cellSize * boardSize + EXTRA_HEIGHT;
setSize(width, height);

setTitle("Visualizer tool for problem Stick Xor");

setResizable(false);
setVisible(true);
}
}

public static void main(String[] args) {
String seed = "1";
vis = true;
for (int i = 0; i < args.length; i++) {
if (args[i].equals("-seed"))
seed = args[++i];
if (args[i].equals("-exec"))
exec = args[++i];
if (args[i].equals("-novis"))
vis = false;
if (args[i].equals("-debug"))
debug = true;
}
new StickXorVis(seed);
}

void addFatalError(String message) {
System.out.println(message);
}
}

class ErrorReader extends Thread {
BufferedReader error;

public ErrorReader(InputStream is) {
error = new BufferedReader(new InputStreamReader(is));
}

public void run() {
try {
for (String s; (s = error.readLine()) != null;) {
System.err.println(s);
System.err.flush();
}
} catch (Exception e) {
e.getStackTrace();
}
}
}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}


このページのトップヘ