EvbCFfp1XB

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

July 2018



Approach simulated annealing を使いました。1億から4億イテレーション。

スコア

  • knight の数 - 2 * 無効な knightの数


近傍
  • ランダムな pawn でない点を選んで、フリップする。
    • 攻撃されている数が2より多い点も含む。
      • 含めたほうがいいかどうかは確認していない。
  • 無効な knight が有れば、
    • この knight を取り除く。確率10%。
    • この knight  を攻撃している数が2より多いとき、攻撃している knight を1つ取り除く。2より少ないとき、攻撃している数が増えるように knight を置く。確率90%。
高速化

  • 次の状態にするときのスコアの差を事前に計算しておく。
  • 1次元の配列を使う。

SAの受理判定

  • KnightsAttacks の wleite さんの受理判定を使ったら、ローカルでは5%くらいスコアが上がったけど、提出したら変わらなかった。(謎)


atsさんのマネ

  • 無効な knight の保持は例の挿入、削除、ランダム取得がO(1)のsetを使った。

初期解

  • knight を置いていない状態から始めました。
  • initialSolution
    こういう状態から始めたほうが、スコアが上がる場合が多かったが、最終的に無効な knight が残って0点になるのを避けられなくて、使えなかった。


source code

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

public class KnightsAndPawns {
    private static final int EMPTY = 0;
    private static final int PAWN = 1;
    private static final int KNIGHT = 2;
    private static final int[] dr = { -2, -2, -1, 1, 2, 2, 1, -1, };
    private static final int[] dc = { -1, 1, 2, 2, 1, -1, -2, -2, };
    private static final int[] dz = { -2, -2, -1, 1, 2, 2, 1, -1, };
    private static final int[] dr2 = { 2, 0, -2, -1, -3, 3, 1, -4, 0, 4, -1, -3, 3, 1, -4, 0, -2, 2, 4, -3, -1, 1, 3, -4, 0, 4, -3, -1, 1, 3, -2, 0, 2, };
    private static final int[] dc2 = { -4, -4, -4, -3, -3, -3, -3, -2, -2, -2, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, };
    static final XorShift rng = new XorShift(System.nanoTime());
    static final Watch watch = new Watch();
    private SAState sa = new SAState();

    private int R;
    private int C;

    private int[] board;

    private int[] attacks;
    private int numKnights;

    private IntSet invalidSet;

    private double score;
    private boolean[] solution;

    private double bestScore;
    private boolean[] bestSolution;

    private int[] deltaScores;

    private IntSet[] directionSet;
    private int RC;

    public String[] placeKnights(String[] board) {
        init(board);
        solve();
        return makeSolution();
    }

    private void init(String[] board) {
        this.R = board.length;
        this.C = board[0].length();
        RC = R * C;
        for (int i = 0; i < dz.length; i++) {
            dz[i] = z(dr[i], dc[i]);
        }
        this.board = new int[RC];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                char charAt = board[r].charAt(c);
                if (charAt == '.') {
                    this.board[z(r, c)] = EMPTY;
                } else if (charAt == 'P') {
                    this.board[z(r, c)] = PAWN;
                }
            }
        }

        attacks = new int[RC];
        for (int z = 0; z < RC; z++) {
            attacks[z] = calculateAttacks(z);
        }

        this.solution = new boolean[RC];
        this.bestSolution = new boolean[RC];
        score = 0;
        bestScore = 0;

        invalidSet = new IntSet(RC);

        directionSet = new IntSet[RC];
        for (int z = 0; z < RC; z++) {
            directionSet[z] = new IntSet(8);
        }

        int numPawns = 0;
        for (int z = 0; z < RC; z++) {
            if (this.board[z] == PAWN) {
                numPawns++;
            }
        }

        Utils.debug("R", R, "C", C, "numPawns", numPawns, String.format("%.1f%%", numPawns * 100.0 / (R * C)));
    }

    private int calculateAttacks(int z) {
        int count = 0;
        for (int d = 0; d < dr.length; d++) {
            int r2 = r(z) + dr[d];
            int c2 = c(z) + dc[d];
            if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) {
                continue;
            }
            int z2 = z(r2, c2);
            if (board[z2] != EMPTY) {
                count++;
            }
        }
        return count;
    }

    private int z(int r, int c) {
        return r * C + c;
    }

    private int r(int z) {
        return z / C;
    }

    private int c(int z) {
        return z % C;
    }

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

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

    private void initDeltaScores() {
        if (deltaScores == null) {
            deltaScores = new int[RC];
        }
        for (int z = 0; z < RC; z++) {
            if (board[z] == PAWN) {
                continue;
            }
            updateDeltaScore(z);
        }
    }

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

        sa.init();
        for (;; sa.numIterations++) {
            if ((sa.numIterations & ((1 << 10) - 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 (invalidSet.size() > 0) {
            reduceInvalidKnight();
            return;
        }
        flip();
    }

    private void flip() {
        int z = (int) (RC * rng.nextDouble());
        while (board[z] == PAWN) {
            z = (int) (RC * rng.nextDouble());
        }
        if (sa.accept(deltaScores[z])) {
            score += deltaScores[z];
            if (solution[z]) {
                removeKnight(z);
            } else {
                putKnight(z);
            }
            updateDeltaScores(z);
            saveBest();
            assert score == calculateScore() : Utils.toString(sa.numIterations, sa.acceptIterations, score, calculateScore(), numKnights, invalidSet.size());
        }

    }

    private boolean check() {
        assert invalidSet.size() == 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                int z = z(r, c);
                assert calculateAttacks(z) == attacks[z];
                if (solution[z]) {
                    assert attacks[z] == 2;
                }
            }
        }
        return true;
    }

    private void reduceInvalidKnight() {
        int z = invalidSet.get((int) (invalidSet.size() * rng.nextDouble()));
        boolean removeMe = rng.nextDouble() < 0.1;
        if (removeMe) {
            if (sa.accept(deltaScores[z])) {
                score += deltaScores[z];
                removeKnight(z);
                updateDeltaScores(z);
                saveBest();
            }
        } else {
            if (attacks[z] > 2) {
                int d = (int) (dr.length * rng.nextDouble());
                int r2 = r(z) + dr[d];
                int c2 = c(z) + dc[d];
                int z2 = z(r2, c2);
                if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) {
                    d = (int) (dr.length * rng.nextDouble());
                    r2 = r(z) + dr[d];
                    c2 = c(z) + dc[d];
                    z2 = z(r2, c2);
                    if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) {
                        d = (int) (dr.length * rng.nextDouble());
                        r2 = r(z) + dr[d];
                        c2 = c(z) + dc[d];
                        z2 = z(r2, c2);
                        if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) {
                            d = (int) (dr.length * rng.nextDouble());
                            r2 = r(z) + dr[d];
                            c2 = c(z) + dc[d];
                            z2 = z(r2, c2);
                            if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) {
                                return;
                            }
                        }
                    }
                }
                if (sa.accept(deltaScores[z2])) {
                    score += deltaScores[z2];
                    removeKnight(z2);
                    updateDeltaScores(z2);
                    saveBest();
                }
            } else {
                int d = (int) (dr.length * rng.nextDouble());
                int r2 = r(z) + dr[d];
                int c2 = c(z) + dc[d];
                int z2 = z(r2, c2);
                if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) {
                    d = (int) (dr.length * rng.nextDouble());
                    r2 = r(z) + dr[d];
                    c2 = c(z) + dc[d];
                    z2 = z(r2, c2);
                    if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) {
                        d = (int) (dr.length * rng.nextDouble());
                        r2 = r(z) + dr[d];
                        c2 = c(z) + dc[d];
                        z2 = z(r2, c2);
                        if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) {
                            d = (int) (dr.length * rng.nextDouble());
                            r2 = r(z) + dr[d];
                            c2 = c(z) + dc[d];
                            z2 = z(r2, c2);
                            if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) {
                                return;
                            }
                        }
                    }
                }
                if (sa.accept(deltaScores[z2])) {
                    score += deltaScores[z2];
                    putKnight(z2);
                    updateDeltaScores(z2);
                    saveBest();
                }
            }
        }
    }

    private void updateDeltaScores(int z) {
        for (int d = 0; d < dr.length; d++) {
            int r2 = r(z) + dr[d];
            int c2 = c(z) + dc[d];
            int z2 = z(r2, c2);
            if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] == PAWN) {
                continue;
            }
            updateDeltaScore(z2);
        }

        for (int d = 0; d < dr2.length; d++) {
            int r2 = r(z) + dr2[d];
            int c2 = c(z) + dc2[d];
            int z2 = z(r2, c2);
            if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] == PAWN) {
                continue;
            }
            updateDeltaScore(z2);
        }
    }

    private void updateDeltaScore(int z) {
        if (solution[z]) {
            deltaScores[z] = (int) (calculateScoreRemove(z) - score);
        } else {
            deltaScores[z] = (int) (calculateScorePut(z) - score);
        }
    }

    private void putKnight(int z) {
        solution[z] = true;
        board[z] = KNIGHT;
        numKnights++;
        for (int d = 0; d < dr.length; d++) {
            int r2 = r(z) + dr[d];
            int c2 = c(z) + dc[d];
            if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) {
                continue;
            }
            int z2 = z(r2, c2);
            attacks[z2]++;

            if (solution[z2]) {
                if (attacks[z2] == 2) {
                    invalidSet.removeValue(z2);
                } else {
                    invalidSet.add(z2);
                }
            }

            directionSet[z2].add((d + 4) % dr.length);

        }

        if (attacks[z] == 2) {
            invalidSet.removeValue(z);
        } else {
            invalidSet.add(z);
        }
    }

    private void removeKnight(int z) {
        solution[z] = false;
        board[z] = EMPTY;
        numKnights--;
        for (int d = 0; d < dr.length; d++) {
            int r2 = r(z) + dr[d];
            int c2 = c(z) + dc[d];
            if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) {
                continue;
            }
            int z2 = z(r2, c2);
            attacks[z2]--;

            if (solution[z2]) {
                if (attacks[z2] == 2) {
                    invalidSet.removeValue(z2);
                } else {
                    invalidSet.add(z2);
                }
            }

            directionSet[z2].removeValue((d + 4) % dr.length);

        }
        invalidSet.removeValue(z);
    }

    private double calculateScore() {
        return numKnights - 2 * invalidSet.size();
    }

    private double calculateScorePut(int z) {
        int numInvalids = invalidSet.size();
        for (int i = 0; i < directionSet[z].size(); i++) {
            int d = directionSet[z].get(i);
            int z2 = z + dz[d];
            if (attacks[z2] == 1) {
                numInvalids--;
            } else if (attacks[z2] == 2) {
                numInvalids++;
            }
        }
        if (attacks[z] != 2) {
            numInvalids++;
        }
        return (numKnights + 1) - 2 * numInvalids;
    }

    private double calculateScoreRemove(int z) {
        int numInvalids = invalidSet.size();
        for (int i = 0; i < directionSet[z].size(); i++) {
            int d = directionSet[z].get(i);
            int z2 = z + dz[d];
            if (attacks[z2] == 3) {
                numInvalids--;
            } else if (attacks[z2] == 2) {
                numInvalids++;

            }
        }
        if (attacks[z] != 2) {
            numInvalids--;
        }
        return (numKnights - 1) - 2 * numInvalids;
    }

    private String[] makeSolution() {
        String[] res = new String[R];
        for (int r = 0; r < R; r++) {
            StringBuilder line = new StringBuilder();
            for (int c = 0; c < C; c++) {
                line.append(solution[z(r, c)] ? 'K' : '.');
            }
            res[r] = line.toString();
        }
        return res;
    }

    private void saveBest() {
        if (invalidSet.size() > 0) {
            return;
        }
        if (score > bestScore) {
            bestScore = score;
            for (int i = 0; i < RC; i++) {
                bestSolution[i] = solution[i];
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int i = 0; i < RC; i++) {
            solution[i] = bestSolution[i];
        }
    }

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

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

            KnightsAndPawns kap = new KnightsAndPawns();
            String[] ret = kap.placeKnights(board);

            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 = 0.4;
    public double endTemperature = 0.1;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

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

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

    private int lastAcceptIterations;

    final int[] log = new int[32768];
    int remain;

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

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

        update();
        lastAcceptTemperature = inverseTemperature;

        double start = KnightsAndPawns.watch.getSecond();
        double m = -0.6 / (endTime - start) * (1 << 28);
        for (int i = 0; i < log.length; i++) {
            log[i] = (int) (m * Math.log((i + 0.5) / log.length));
        }
        remain = (int) (endTime - start);
    }

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

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

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

    public void updateTime() {
        time = useTime ? KnightsAndPawns.watch.getSecond() : numIterations;
        remain = (int) (endTime - time);
    }

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

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

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

        if (deltaScore > -1e-9) {
            acceptIterations++;
            lastAcceptIterations = numIterations;
            return true;
        }
        if ((deltaScore > -6 && (-deltaScore << 28) <= log[KnightsAndPawns.rng.nextInt(log.length)] * remain)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

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

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

        if (KnightsAndPawns.rng.nextDouble() < Math.exp(-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 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;
        }
        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) {
        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;
    }

}




Approach
  • 各Expert のこれまで Round の予想と結果のデータから、Random Forest で、各Expert の今の Round の結果を予想する。
  • Random Forest は事前に学習したもの。
  • 予想の値が正で大きい方から、賭けれるだけお金をかける。
  • データを取るために毎 Round、すべての Expert に少なくとも 100 は賭ける。


Random Forest

  • 1 ケースごとに平均約1500のデータが集まる。300ケース分約45万のデータで学習した。
  • 学習に使った特徴は、今の Round数, 予想,  予想と結果の差の絶対値の最小値、平均、最大値、標準偏差、歪度、尖度、和、sum of squared error, 25パーセンタイル, 50パーセンタイル, 75パーセンタイル。
  • 重要な方から、予想, 予想と結果の差の絶対値の平均、予想と結果の差の絶対値の最大値, ... 。
  • 決定木の数 : 32
  • 決定木の深さ : 10


Source code

埋め込んだ Random Forest のせいで、文字数制限を超過したため省略。


Score 201225


Approach SAを使いました。L字型の経路を最大9個使いました。

L字型の経路は次のような感じで、
class L {
int r;
int c;
boolean rFirst;
}
目的地の"行"と"列"と"先にどちらの方向に進むか"を持つ。


近傍

  • L字型の経路の追加(画面端のランダムな点まで)
  • L字型の経路の追加(ランダムな点まで)
  • L字型の経路の追加(次のL字型の経路が作る長方形内のランダムな点まで)
  • L字型の経路の削除
  • L字型の経路の変更(ランダムな点まで)
  • L字型の経路の変更(現在の点の隣の点まで)
  • L字型の経路の交換

source code



Visualizer



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

}


↑このページのトップヘ