EvbCFfp1XB

problem and my answer.



Approach beam search を使いました。

  • ケーキを8個以下に切るときは、すべての切り方を試す。そうでないときは、長方形に切る。
  • beam width : 切り方により, 10〜数千まで変わる。
  • 評価関数 : 理想的な切り方ができたときのスコアにした。あと、親のスコアをちょっと足してみた、効果はなかった。
  • 切るケーキの選び方 : 小さいものを選んだ。スコアを早く確定するのが良いらしい。

難しかったところ
  • 高速化しても(beam width を増やしても)精度が良くならなかった。
  • 重複の除去もうまくいってなかった。
  • たまに、切れない形になって、0点を出す。

source code

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

public class CakeSharing {
    private static final double d = 0.01;
    private int count = 0;

    private int R;
    private int C;
    private int numCakes;

    private ArrayList pieces2;
    private ArrayList cuts2;

    public String[] cut(String[] roses, int NP) {
        init(roses, NP);
        solve();
        Utils.debug("count", count);
        return makeSolution();
    }

    TwoDimensionalCumulativeSum cumulativeSum;

    private void init(String[] roses, int NP) {
        Constants.watch.init();

        numCakes = NP;
        R = roses.length;
        H = R;
        C = roses[0].length();
        W = C;

        Utils.debug("R", R, "C", C, "NP", NP);
        this.roses = new char[R][C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                char charAt = roses[r].charAt(c);
                this.roses[r][c] = charAt;
            }
        }

        {
            int[][] values = new int[R][C];
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    values[r][c] = this.roses[r][c] == 'R' ? 1 : 0;
                }
            }
            cumulativeSum = new TwoDimensionalCumulativeSum(values);
        }

        pieces2 = new ArrayList<>();
        cuts2 = new ArrayList<>();

        ArrayList convexHull = new ArrayList<>();
        convexHull.add(new Point(0, 0));
        convexHull.add(new Point(0, R));
        convexHull.add(new Point(C, R));
        convexHull.add(new Point(C, 0));
        pieces2.add(new Piece(convexHull, true));
    }

    private void solve() {
        ArrayList beamsearch = beamsearch(numCakes - 1, 20);
        set(beamsearch, 0);
    }

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth) {
        double meanArea = R * C / (double) numCakes;
        maxBeamWidth = 10000;
        MeanHelper widthHelper = new MeanHelper();
        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        currents.add(new State());

        double[] timeLimits = getTimeLimits(maxDepth);

        for (int depth = 0; depth < maxDepth; depth++) {
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            Collections.sort(currents);
            widthLoop: for (int width = 0;; width++) {
                if (width >= beamWidth) {
                    widthHelper.add(width);
                    break;
                }

                State currentState = currents.get(width);

                if (depth % 10 == 0) {
                    if (width == 0) {
                        if (currentState != null) {
                            Utils.debug("depth", depth, "score", currentState.score, "currents.size()", currents.size());
                        }
                    }
                }
                set(reverse(toList(currentState)), 0);
                int maxIndex = getPieceIndex();
                Piece piece = pieces2.get(maxIndex);
                int numCakes0 = (int) Math.round(piece.getPieceArea() / meanArea);

                MeanHelper areaHelper = new MeanHelper();
                MeanHelper roseHelper = new MeanHelper();
                for (Piece piece2 : pieces2) {
                    if (piece2 == piece) {
                        continue;
                    }
                    double area = piece2.getPieceArea();
                    int numCakes3 = (int) (Math.round(area / meanArea));
                    minAreaSD(area, numCakes3);
                    areaHelper.add(this.area[0], number[0]);
                    areaHelper.add(this.area[1], number[1]);

                    int rose = piece2.countRose();
                    minRoseSD(rose, numCakes3);
                    roseHelper.add(this.area[0], number[0]);
                    roseHelper.add(this.area[1], number[1]);
                }
                if (numCakes0 > 8 && piece.isRectangle) {
                    int maxX = (int) -1e9;
                    int minX = (int) 1e9;
                    int maxY = (int) -1e9;
                    int minY = (int) 1e9;
                    for (int i = 0; i < piece.convexHull.size(); i++) {
                        Point point = piece.convexHull.get(i);
                        maxX = Math.max(maxX, point.x);
                        minX = Math.min(minX, point.x);
                        maxY = Math.max(maxY, point.y);
                        minY = Math.min(minY, point.y);
                    }

                    for (int r = minY + 1; r < maxY; r++) {
                        Point p1 = new Point(minX, r);
                        Point p2 = new Point(maxX, r);
                        simulateCut(maxIndex, p1, p2);
                        if (areaAndRose[0] == -1) {
                            continue;
                        }

                        if (pruning(meanArea, areaHelper)) {
                            continue;
                        }

                        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                        double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                        setNext(nexts, currentState, piece, p1, p2, expectedScore);
                        if (Constants.watch.getSecond() > timeLimits[depth]) {
                            widthHelper.add(width);
                            break widthLoop;
                        }
                    }
                    for (int c = minX + 1; c < maxX; c++) {
                        Point p1 = new Point(c, minY);
                        Point p2 = new Point(c, maxY);
                        simulateCut(maxIndex, p1, p2);
                        if (areaAndRose[0] == -1) {
                            continue;
                        }

                        if (pruning(meanArea, areaHelper)) {
                            continue;
                        }

                        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                        double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                        setNext(nexts, currentState, piece, p1, p2, expectedScore);
                        if (Constants.watch.getSecond() > timeLimits[depth]) {
                            widthHelper.add(width);
                            break widthLoop;
                        }
                    }
                } else {
                    for (int i = 0; i < piece.pointSize(); i++) {
                        Point p1 = piece.getPoint(i);
                        for (int j = i + 1; j < piece.pointSize(); j++) {
                            Point p2 = piece.getPoint(j);
                            if (numCakes0 > 8) {
                                if (p2.x != p1.x && p2.y != p1.y) {
                                    continue;
                                }
                            }
                            simulateCut(maxIndex, p1, p2);
                            if (areaAndRose[0] == -1) {
                                continue;
                            }

                            if (pruning(meanArea, areaHelper)) {
                                continue;
                            }

                            int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));
                            int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));

                            double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2);

                            setNext(nexts, currentState, piece, p1, p2, expectedScore);
                            if (Constants.watch.getSecond() > timeLimits[depth]) {
                                widthHelper.add(width);
                                break widthLoop;
                            }
                        }
                    }
                }

            }

            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }
        Utils.debug("mean width", widthHelper.mean());

        Collections.sort(currents);
        State best = currents.get(0);

        Utils.debug("time", Constants.watch.getSecondString(), "score", best.score);

        return reverse(toList(best));
    }

    private boolean pruning(double meanArea, MeanHelper areaHelper) {
        int numCakes1p = (int) (Math.round(d + areaAndRose[0] / meanArea));
        int numCakes1m = (int) (Math.round(-d + areaAndRose[0] / meanArea));
        if (numCakes1p != numCakes1m) {
            count++;
            return true;
        }
        int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea));

        int numCakes2p = (int) (Math.round(d + areaAndRose[2] / meanArea));
        int numCakes2m = (int) (Math.round(-d + areaAndRose[2] / meanArea));
        if (numCakes2p != numCakes2m) {
            count++;
            return true;
        }
        int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea));
        if (areaHelper.count() + numCakes1 + numCakes2 != numCakes) {
            return true;
        }
        if (numCakes1 < 1) {
            return true;
        }
        if (numCakes2 < 1) {
            return true;
        }
        return false;
    }

    private double calculateExpectedScore(MeanHelper areaHelper, MeanHelper roseHelper, int numCakes1, int numCakes2) {
        double expectedScore = 0;
        {
            minAreaSD(areaAndRose[0], numCakes1);
            areaHelper.add(this.area[0], number[0]);
            areaHelper.add(this.area[1], number[1]);
            minAreaSD(areaAndRose[2], numCakes2);
            areaHelper.add(this.area[0], number[0]);
            areaHelper.add(this.area[1], number[1]);
            double sdArea = areaHelper.standardDeviation(1e9);
            areaHelper.add(this.area[0], -number[0]);
            areaHelper.add(this.area[1], -number[1]);
            minAreaSD(areaAndRose[0], numCakes1);
            areaHelper.add(this.area[0], -number[0]);
            areaHelper.add(this.area[1], -number[1]);
            minRoseSD((int) areaAndRose[1], numCakes1);
            roseHelper.add(this.area[0], number[0]);
            roseHelper.add(this.area[1], number[1]);
            minRoseSD((int) areaAndRose[3], numCakes2);
            roseHelper.add(this.area[0], number[0]);
            roseHelper.add(this.area[1], number[1]);
            double sdRose = roseHelper.standardDeviation(1e9);
            roseHelper.add(this.area[0], -number[0]);
            roseHelper.add(this.area[1], -number[1]);
            minRoseSD((int) areaAndRose[1], numCakes1);
            roseHelper.add(this.area[0], -number[0]);
            roseHelper.add(this.area[1], -number[1]);
            expectedScore = (1.0 + sdArea) * (1.0 + sdRose);
            if (Double.isNaN(expectedScore)) {
                expectedScore = 1e9;
            }
        }
        return expectedScore;
    }

    private void setNext(ArrayList nexts, State currentState, Piece piece, Point p1, Point p2, double expectedScore) {
        {
            State nextState = new State();
            nextState.parent = currentState;
            nextState.piece = piece;
            nextState.cut = new Cut(p1, p2);
            nextState.score = 0.9 * expectedScore + 0.1 * currentState.score;
            nexts.add(nextState);
        }
    }

    private double[] area = new double[2];
    private int[] number = new int[2];

    private void minAreaSD(double area, int numCakes) {
        double meanArea = area / (double) numCakes;
        double less = 0.5 * ((int) (2 * meanArea));
        double more = Math.abs(less - meanArea) < 1e-5 ? less : (less + 0.5);

        int numMore = (int) (1e-9 + (area - less * numCakes) / 0.5);
        int numLess = numCakes - numMore;
        this.area[0] = less;
        this.area[1] = more;
        number[0] = numLess;
        number[1] = numMore;
        assert Math.abs(area - (less * numLess + more * numMore)) < 1e-5;
    }

    private void minRoseSD(int rose, int numCakes) {
        double meanRose = rose / (double) numCakes;
        double less = Math.floor(1e-9 + meanRose);
        double more = Math.ceil(-1e-9 + meanRose);

        int numMore = (int) (1e-9 + (rose - less * numCakes));
        int numLess = numCakes - numMore;
        this.area[0] = less;
        this.area[1] = more;
        number[0] = numLess;
        number[1] = numMore;
        assert Math.abs(rose - (less * numLess + more * numMore)) < 1e-5;
    }

    private double[] getTimeLimits(int maxDepth) {
        double[] timeLimits = new double[maxDepth];
        double end = 9.5;
        double start = Constants.watch.getSecond();
        for (int i = 0; i < maxDepth; i++) {
            timeLimits[i] = start + (end - start) * ((i + 1.0) / maxDepth);
        }
        return timeLimits;
    }

    private Piece getMaxAreaPiece() {
        Piece piece = null;
        for (int i = 0; i < pieces2.size(); i++) {
            Piece piece2 = pieces2.get(i);
            if (piece == null || piece2.getPieceArea() > piece.getPieceArea()) {
                piece = piece2;
            }
        }
        return piece;
    }

    private int getMaxAreaPieceIndex() {
        int maxIndex = 0;
        for (int i = 0; i < pieces2.size(); i++) {
            if (pieces2.get(i).getPieceArea() > pieces2.get(maxIndex).getPieceArea()) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    private int getMinAreaPieceIndex() {
        double meanArea = R * C / (double) numCakes;
        int minIndex = -1;
        for (int i = 0; i < pieces2.size(); i++) {
            if (pieces2.get(i).getPieceArea() / meanArea < 1.5) {
                continue;
            }
            if (minIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(minIndex).getPieceArea()) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    private int getPieceIndex() {
        double meanArea = R * C / (double) numCakes;
        int bestIndex = -1;
        double bestZ = (int) 1e9;
        for (int i = 0; i < pieces2.size(); i++) {
            Piece piece = pieces2.get(i);
            if (piece.getPieceArea() / meanArea < 1.5) {
                continue;
            }

            int minZ = (int) 1e9;
            int sumZ = 0;
            for (int j = 0; j < piece.convexHull.size(); j++) {
                Point point = piece.convexHull.get(j);
                int z = point.y + point.x;
                minZ = Math.min(minZ, z);
                sumZ += z;
            }
            double meanZ = sumZ / (double) piece.convexHull.size();

            if (bestIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(bestIndex).getPieceArea()) {
                bestIndex = i;
                bestZ = meanZ;
            } else if (Math.abs(pieces2.get(i).getPieceArea() - pieces2.get(bestIndex).getPieceArea()) < 1e-5 && meanZ < bestZ) {
                bestIndex = i;
                bestZ = meanZ;
            }
        }
        return bestIndex;
    }

    private double[] areaAndRose = new double[4];

    private void simulateCut(int ind, Point p1, Point p2) {
        if (p1.equals(p2)) {
            areaAndRose[0] = -1;
            return;
        }
        if (!isInside(p1) || !isInside(p2)) {
            areaAndRose[0] = -1;
            return;
        }

        int i1 = -1, i2 = -1;
        Piece piece = pieces2.get(ind);
        i1 = piece.isOnPieceEdge(p1);
        i2 = piece.isOnPieceEdge(p2);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }
        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
            if (index >= i2) {
                break;
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        double aold = piece.getPieceArea() - newPiece.getPieceArea();
        if (aold < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        ArrayList pold_updated = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index < i1) {
                pold_updated.add(point);
            } else {
                break;
            }
        }
        pold_updated.add(p1);
        pold_updated.add(p2);
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i2) {
                pold_updated.add(point);
            }
        }
        Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        areaAndRose[0] = newPiece.getPieceArea();
        areaAndRose[1] = newPiece.countRose();
        areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea();
        areaAndRose[3] = newPiece2.countRose();
    }

    private void simulateCutFast(int ind, Point p1, Point p2) {
        if (p1.equals(p2)) {
            areaAndRose[0] = -1;
            return;
        }
        if (!isInside(p1) || !isInside(p2)) {
            areaAndRose[0] = -1;
            return;
        }

        int i1 = -1, i2 = -1;
        Piece piece = pieces2.get(ind);
        i1 = piece.isOnPieceEdge(p1);
        i2 = piece.isOnPieceEdge(p2);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }
        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        double aold = piece.getPieceArea() - newPiece.getPieceArea();
        if (aold < 0.25) {
            areaAndRose[0] = -1;
            return;
        }

        areaAndRose[0] = newPiece.getPieceArea();
        areaAndRose[1] = newPiece.countRose();
        areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea();
        areaAndRose[3] = piece.countRose() - newPiece.countRose();
    }

    private int turn = 0;

    private void next(Cut cut) {
        makeCut(cut.start, cut.end);
        turn++;
    }

    private void previous() {
        turn--;
        pieces2.set(indHistory[turn], pieceHistory[turn]);
        pieces2.remove(pieces2.size() - 1);
        cuts2.remove(cuts2.size() - 1);
    }

    private void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;

        for (int i = 0; i < list.size() && startIndex + i < cuts2.size(); i++) {
            State state = list.get(i);
            if (state.cut.equals(cuts2.get(startIndex + i))) {
                startIndexMinus1 = startIndex + i;
                continue;
            }
            break;
        }

        for (; turn > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.cut);
        }
    }

    private ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private ArrayList toList(State state2) {
        ArrayList res = new ArrayList<>();
        for (State current = state2; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private static int cross(int x, int y, int x2, int y2) {
        return x * y2 - y * x2;
    }

    private String[] makeSolution() {
        ArrayList res = new ArrayList<>();
        for (int i = 0; i < cuts2.size(); i++) {
            Cut cut = cuts2.get(i);
            res.add(cut.start.x + " " + cut.start.y + " " + cut.end.x + " " + cut.end.y);
        }
        return (String[]) res.toArray(new String[res.size()]);
    }

    private int H, W;
    private char[][] roses;
    private Piece[] pieceHistory = new Piece[321];
    private int[] indHistory = new int[321];

    private boolean isInside(Point p) {
        return (p.y >= 0 && p.y <= H && p.x >= 0 && p.x <= W);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private String makeCut(Point p1, Point p2) {
        if (p1.equals(p2)) {
            Utils.debug("A");
            return "The cut must have non-zero length.";
        }
        if (!isInside(p1) || !isInside(p2)) {
            Utils.debug("B");
            return "The cut can not start or end outside the cake.";
        }
        int ind = -1, i1 = -1, i2 = -1;
        for (int i = 0; i < pieces2.size(); ++i) {
            Piece piece = pieces2.get(i);
            i1 = piece.isOnPieceEdge(p1);
            if (i1 == -1)
                continue;
            i2 = piece.isOnPieceEdge(p2);
            if (i2 == -1) {
                i1 = -1;
                continue;
            }
            ind = i;
            break;
        }
        if (ind == -1) {
            Utils.debug("C");
            return "The cut must divide one piece in two pieces.";
        }
        Piece piece = pieces2.get(ind);
        if (i1 > i2) {
            int t = i2;
            i2 = i1;
            i1 = t;
            Point tmp = p2;
            p2 = p1;
            p1 = tmp;
        }

        ArrayList pnew = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i1 && index < i2) {
                pnew.add(point);
            }
            if (index >= i2) {
                break;
            }
        }
        pnew.add(p2);
        pnew.add(p1);
        Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double anew = newPiece.getPieceArea();
        if (anew < 0.25) {
            return "The pieces produced by the cut must have non-zero area.";
        }

        ArrayList pold_updated = new ArrayList();
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index < i1) {
                pold_updated.add(point);
            } else {
                break;
            }
        }
        pold_updated.add(p1);
        pold_updated.add(p2);
        for (int i = 0; i < piece.convexHull.size(); i++) {
            Point point = piece.convexHull.get(i);
            int index = piece.points.indexOf(z(point.y, point.x));
            if (index > i2) {
                pold_updated.add(point);
            }
        }
        Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y));

        double aold = newPiece2.getPieceArea();
        if (aold < 0.25) {
            return "The pieces produced by the cut must have non-zero area.";
        }

        indHistory[turn] = ind;
        pieceHistory[turn] = pieces2.set(ind, newPiece);
        pieces2.add(newPiece2);
        cuts2.add(new Cut(p1, p2));
        return "";
    }

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

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

            int NP = Integer.parseInt(br.readLine());

            CakeSharing cs = new CakeSharing();
            String[] ret = cs.cut(roses, NP);

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

    class Piece {
        ArrayList convexHull;
        IntSet points;
        boolean isRectangle;

        public Piece(ArrayList convexHull, boolean isRectangle) {
            super();
            this.convexHull = convexHull;
            this.isRectangle = isRectangle;
        }

        @Override
        public String toString() {
            return convexHull.toString();
        }

        public boolean isConvexHull(Point point) {
            for (int i = 0; i < convexHull.size(); i++) {
                if (convexHull.get(i).equals(point)) {
                    return true;
                }
            }
            return false;
        }

        public int pointSize() {
            if (points == null) {
                initPoints();
            }
            return points.size();
        }

        public Point getPoint(int i) {
            if (points == null) {
                initPoints();
            }
            int z = points.get(i);
            return new Point(c(z), r(z));
        }

        private int isOnPieceEdge(Point p) {
            if (points == null) {
                initPoints();
            }
            return points.indexOf(z(p.y, p.x));
        }

        private void initPoints() {
            points = new IntSet((R + 1) * (C + 1));
            for (int i = 0; i < convexHull.size(); i++) {
                int j = (i + 1) % convexHull.size();
                Point p1 = convexHull.get(i);
                Point p2 = convexHull.get(j);
                addPointsOnCut(p1, p2);
            }
        }

        private void addPointsOnCut(Point p1, Point p2) {
            assert p1.x != p2.x || p1.y != p2.y : Utils.toString("p1.x", p1.x, "p2.x", p2.x, "p1.y", p1.y, "p2.y", p2.y);
            int dx = p2.x - p1.x, dy = p2.y - p1.y;
            int g = Math.abs(gcd(dx, dy));
            for (int i = 0; i <= g; ++i) {
                int x = p1.x + (dx / g) * i;
                int y = p1.y + (dy / g) * i;
                points.add(z(y, x));
            }
        }

        private double area = -1;

        private double getPieceArea() {
            if (area < 0) {
                area = 0;
                for (int i = 0; i < convexHull.size(); ++i) {
                    Point p1 = convexHull.get(i);
                    Point p2 = convexHull.get((i + 1) % convexHull.size());
                    area += cross(p1.x, p1.y, p2.x, p2.y);
                }
                area = 0.5 * Math.abs(area);
            }
            return area;
        }

        private int countRose = -1;

        private int countRose() {
            if (countRose < 0) {
                int maxX = (int) -1e9;
                int minX = (int) 1e9;
                int maxY = (int) -1e9;
                int minY = (int) 1e9;
                for (int i = 0; i < convexHull.size(); i++) {
                    Point point = convexHull.get(i);
                    maxX = Math.max(maxX, point.x);
                    minX = Math.min(minX, point.x);
                    maxY = Math.max(maxY, point.y);
                    minY = Math.min(minY, point.y);
                }

                if (isRectangle) {
                    countRose = cumulativeSum.cumulativeSum(minY, minX, maxY, maxX);
                } else {
                    int n = 0;
                    for (int r = minY; r < maxY; ++r)
                        for (int c = minX; c < maxX; ++c) {
                            if (roses[r][c] != 'R') {
                                continue;
                            }

                            if (isRoseInsidePiece(new Point(2 * c + 1, 2 * r + 1))) {
                                n++;
                            }
                        }
                    countRose = n;
                }
            }
            return countRose;
        }

        private boolean isRoseInsidePiece(Point point) {
            for (int i = 0; i < convexHull.size(); i++) {
                Point p = convexHull.get(i);
                Point p2 = convexHull.get((i + 1) % convexHull.size());
                if (cross(2 * (p2.x - p.x), 2 * (p2.y - p.y), point.x - 2 * p.x, point.y - 2 * p.y) >= 0) {
                    return false;
                }
            }
            return true;
        }

    }

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

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

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

    class State implements Comparable {
        State parent;
        Piece piece;
        Cut cut;
        double score;

        @Override
        public int compareTo(State o) {
            if (score < o.score) {
                return -1;
            }
            if (score > o.score) {
                return 1;
            }
            return 0;
        }

    }

}

class Constants {
    public static final XorShift rng = new XorShift(System.nanoTime());
    public static final Watch watch = new Watch();
}

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) {
        assert value < valueToIndex.length : Utils.toString("value", value, "valueToIndex.length", valueToIndex.length);
        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;
    }

}

class Point {
    public int x, y;

    public Point(int px, int py) {
        x = px;
        y = py;
    }

    public boolean equals(Point p) {
        return x == p.x && y == p.y;
    }

    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

class Cut {
    public Point start, end;

    public Cut(Point s, Point e) {
        start = s;
        end = e;
    }

    public Cut(int x1, int y1, int x2, int y2) {
        start = new Point(x1, y1);
        end = new Point(x2, y2);
    }

    public boolean equals(Cut obj) {
        return (start.equals(obj.start) && end.equals(obj.end)) || (start.equals(obj.end) && end.equals(obj.start));
    }

    public String toString() {
        return start + " - " + end;
    }
}

class Pair, S> implements Comparable> {
    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 other = (Pair) 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 o) {
        return first.compareTo(o.first);
    }
}

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

    public MeanHelper() {
        clear();
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

    public double standardDeviation(double defaultValue) {
        double variance = variance(defaultValue);
        if (Math.abs(variance) < 1e-9) {
            return 0;
        }
        return Math.sqrt(variance);
    }

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

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

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

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

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

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

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

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

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class TwoDimensionalCumulativeSum {
    private int[][] sum;

    public TwoDimensionalCumulativeSum(int[][] values) {
        int R = values.length;
        int C = values[0].length;
        sum = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                sum[r + 1][c + 1] = sum[r + 1][c] + sum[r][c + 1] - sum[r][c] + values[r][c];
            }
        }
    }

    public int cumulativeSum(int startRInclusive, int startCInclusive, int endRExclusive, int endCExclusive) {
        return sum[startRInclusive][startCInclusive] - sum[endRExclusive][startCInclusive] - sum[startRInclusive][endCExclusive] + sum[endRExclusive][endCExclusive];
    }
}



確か12位か13位。


Approach beam search を使いました。

  • beam width 800 で9秒
  • ある状態から生成する子の状態は、最大100(カメレオン10 * 色最大10)有る内の3つだけに絞った。カメレオンは後ろの方の3匹だけ。色はカメレオンごとに最も前に移動できる色を選ぶ。
評価関数

  • カメレオンの位置の和
    • この評価関数では、beam width を2000〜3000にしてもスコアは40000にぎりぎり届くくらいだった。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

public class Main {

    private int numStripePatterns;
    private int backpackColors;
    private int numColors;
    private int handColors;
    private int numChameleons;
    private int[] stripPattern;
    private int[] backpack;
    private int[] distances;
    private int[] hand;
    private String[] solution;

    private Watch watch = new Watch();
    private XorShift rng = new XorShift(System.nanoTime());
    private long[] hashes;
    private InitializedBooleanArray position;
    private int[][] nextPosition;

    private String[] run(int N, int S, int C, int H, int U, String stripPattern, String backpack) {
        init(N, S, C, H, U, stripPattern, backpack);
        solve();
        return makeSolution();
    }

    private void init(int N, int S, int C, int H, int U, String stripPattern, String backpack) {
        this.numStripePatterns = N;
        this.backpackColors = S;
        this.numColors = C;
        this.handColors = H;
        this.numChameleons = U;

        this.stripPattern = new int[numStripePatterns];
        for (int i = 0; i < numStripePatterns; i++) {
            this.stripPattern[i] = stripPattern.charAt(i) - 'A';
        }
        this.hand = new int[handColors];
        for (int i = 0; i < H; i++) {
            this.hand[i] = backpack.charAt(i) - 'A';
        }
        this.backpack = new int[backpackColors + 1];
        for (int i = 0; i < backpackColors; i++) {
            this.backpack[i] = backpack.charAt(handColors + i) - 'A';
        }

        this.distances = new int[numChameleons];
        for (int i = 0; i < numChameleons; i++) {
            distances[i] = i;
        }

        this.solution = new String[backpackColors];
        hashes = new long[numStripePatterns];
        for (int i = 0; i < numStripePatterns; i++) {
            hashes[i] = rng.nextLong();
        }
        position = new InitializedBooleanArray();
        position.init(false, numStripePatterns);

        nextPosition = new int[numColors][numStripePatterns];
        for (int color = 0; color < numColors; color++) {
            int next = -1;
            for (int distance = numStripePatterns - 1; distance >= 0; distance--) {
                nextPosition[color][distance] = next;
                if (this.stripPattern[distance] == color) {
                    next = distance;
                }
            }
        }
    }

    private void solve() {
        ArrayList beamsearch = beamsearch(backpackColors, 800);
        for (int i = 0; i < beamsearch.size(); i++) {
            updateState(i, beamsearch.get(i).chameleonIndex, beamsearch.get(i).hi);
        }
    }

    private ArrayList distanceAndIndexPairs = new ArrayList<>();

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth) {
        int K = 3;
        int[] index = new int[K];

        InitializedBooleanArray usedColors = new InitializedBooleanArray();
        usedColors.init(false, numColors);

        int size = 1 << 15;

        for (int i = 0; i < numChameleons; i++) {
            distanceAndIndexPairs.add(new PairIntInt(0, 0));
        }

        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 used = new RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(16, 1 << 16);
        setCurrent(currents);

        double startTime = watch.getSecond();
        for (int depth = 0; depth < maxDepth; depth++) {
            used.clear();
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
            for (int width = 0; width < beamWidth; width++) {
                State currentState = currents.get(width);
                if (depth % 1000 == 999) {
                    if (width == 0) {
                        if (currentState != null) {
                            Utils.debug(depth, currentState.score(), (int) (currentState.score() * 10000 / (depth + 1)), "exp time", (int) ((watch.getSecond() - startTime) * 10000 / (depth + 1)));
                        }
                    }
                }
                position.clear();
                for (int i = 0; i < numChameleons; i++) {
                    position.set(currentState.getDistance(i), true);
                }
                int min1 = (int) 1e9;
                int min2 = (int) 1e9;
                int min3 = (int) 1e9;
                for (int i = 0; i < numChameleons; i++) {
                    int v = currentState.getDistance(i);
                    if (v < min1) {
                        min3 = min2;
                        min2 = min1;
                        min1 = v;
                        index[2] = index[1];
                        index[1] = index[0];
                        index[0] = i;
                    } else if (v < min2) {
                        min3 = min2;
                        min2 = v;
                        index[2] = index[1];
                        index[1] = i;
                    } else if (v < min3) {
                        min3 = v;
                        index[2] = i;
                    }
                }
                for (int k = 0; k < K; k++) {
                    int chameleonIndex = index[k];
                    int bestHi = -1;
                    int maxDistance = -1;
                    usedColors.clear();
                    for (int hi = 0; hi < handColors; hi++) {
                        int hand2 = currentState.getHand(hi);
                        if (usedColors.get(hand2)) {
                            continue;
                        }
                        usedColors.set(hand2, true);
                        int distance = distance(chameleonIndex, hand2, currentState);
                        if (distance > maxDistance) {
                            maxDistance = distance;
                            bestHi = hi;
                        }
                    }
                    int hi = bestHi;
                    int distance = maxDistance;
                    {
                        long nextHash = currentState.hash;
                        nextHash ^= hashes[currentState.getDistance(chameleonIndex)];
                        nextHash ^= hashes[distance];
                        nextHash ^= hashes[currentState.getHand(hi)];
                        nextHash ^= hashes[backpack[currentState.turn]];
                        boolean add = used.add(nextHash);
                        if (!add) {
                            continue;
                        }
                        State next = new State();
                        next.parent = currentState;
                        next.turn = currentState.turn + 1;
                        next.distances[0] = currentState.distances[0];
                        next.distances[1] = currentState.distances[1];
                        next.distances[2] = currentState.distances[2];
                        next.setDistance(chameleonIndex, distance);

                        next.hand = currentState.hand;
                        next.setHand(hi, backpack[currentState.turn]);
                        next.sum = currentState.sum;
                        next.sum -= currentState.getDistance(chameleonIndex);
                        next.sum += distance;
                        next.hash = nextHash;

                        next.chameleonIndex = chameleonIndex;

                        next.hi = hi;
                        nexts.add(next);
                    }

                }
            }
            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }
        Collections.sort(currents);
        State best = currents.get(0);

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

        return reverse(toList(best));
    }

    private void setCurrent(ArrayList currents) {
        boolean setCurrent = !true;
        if (setCurrent) {

        } else {
            State s = new State();
            s.parent = null;
            s.hi = -1;
            s.chameleonIndex = -1;
            s.sum = 45;
            s.turn = 0;
            s.hash = 0L;
            for (int i = 0; i < numChameleons; i++) {
                s.setDistance(i, i);
            }
            for (int i = 0; i < handColors; i++) {
                s.setHand(i, hand[i]);
            }
            currents.add(s);
        }
    }

    private ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private ArrayList toList(State state2) {
        ArrayList res = new ArrayList<>();
        for (State current = state2; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private void updateState(int s, int di, int hi) {
        distances[di] = distance(di, hand[hi]);
        solution[s] = "" + di + " " + (char) ('A' + hand[hi]);
        hand[hi] = backpack[s];
    }

    private int distance(int chameleonIndex, int color) {
        for (int i = nextPosition[color][distances[chameleonIndex]];; i = nextPosition[color][i]) {
            if (isThereAChameleon(i)) {
                continue;
            }

            return i;
        }
    }

    private int distance(int chameleonIndex, int color, State state) {
        for (int i = nextPosition[color][state.getDistance(chameleonIndex)];; i = nextPosition[color][i]) {
            assert stripPattern[i % stripPattern.length] == color;
            if (isThereAChameleon(i, state)) {
                continue;
            }

            return i;
        }
    }

    private boolean isThereAChameleon(int distance) {
        for (int i = 0; i < distances.length; i++) {
            if (distances[i] == distance) {
                return true;
            }
        }
        return false;
    }

    private boolean isThereAChameleon(int distance, State state) {
        return position.get(distance);
    }

    private String[] makeSolution() {
        return solution;
    }

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

            String[] split = br.readLine().trim().split(" ");
            int N = Integer.parseInt(split[0]);
            int S = Integer.parseInt(split[1]);
            int C = Integer.parseInt(split[2]);
            int H = Integer.parseInt(split[3]);
            int U = Integer.parseInt(split[4]);

            String stripPattern = br.readLine();
            String backpack = br.readLine();

            Main main = new Main();
            String[] res = main.run(N, S, C, H, U, stripPattern, backpack);
            for (int i = 0; i < res.length; ++i) {
                System.out.println(res[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

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 CollectionsUtils {
    private CollectionsUtils() {
    }

    public static final  void shuffle(ArrayList list, Random rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void shuffle(ArrayList list, XorShift rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void select0(ArrayList a, int l, int r, int k, Comparator comparator) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r, comparator);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final  void select(ArrayList a, int startInclusive, int endExclusive, int k, Comparator comparator) {
        select0(a, startInclusive, endExclusive - 1, k, comparator);
    }

    public static final > void select0(ArrayList a, int l, int r, int k) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k) {
        select0(a, startInclusive, endExclusive - 1, k);
    }

    public static final  void swap(ArrayList a, int i, int j) {
        T swap = a.set(i, a.get(j));
        a.set(j, swap);
    }

    public static final  void sort3(ArrayList a, int i, int j, int k, Comparator comparator) {
        if (comparator.compare(a.get(i), a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (comparator.compare(a.get(i), a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (comparator.compare(a.get(j), a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final > void sort3(ArrayList a, int i, int j, int k) {
        if (a.get(i).compareTo(a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (a.get(i).compareTo(a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (a.get(j).compareTo(a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final  int partition3(ArrayList a, int l, int r, Comparator comparator) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r, comparator);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; comparator.compare(a.get(++i), v) < 0;) {
            }
            for (; comparator.compare(a.get(--j), v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition3(ArrayList a, int l, int r) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; a.get(++i).compareTo(v) < 0;) {
            }
            for (; a.get(--j).compareTo(v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition(ArrayList a, int l, int r) {
        int i = l - 1, j = r;
        T v = a.get(r);
        for (;;) {
            while (a.get(++i).compareTo(v) < 0)
                ;
            while (v.compareTo(a.get(--j)) < 0)
                if (j == l)
                    break;
            if (i >= j)
                break;
            swap(a, i, j);
        }
        swap(a, i, r);
        return i;
    }

    public static final  void sort(ArrayList a, int lInclusive, int rInclusive, Comparator comparator) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive, comparator);
        sort(a, lInclusive, k - 1, comparator);
        sort(a, k + 1, rInclusive, comparator);
    }

    public static final > void sort(ArrayList a, int lInclusive, int rInclusive) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive);
        sort(a, lInclusive, k - 1);
        sort(a, k + 1, rInclusive);
    }

    public static final  ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    public static final  ArrayList newReverse(ArrayList list) {
        ArrayList res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

}

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 Pair, S> implements Comparable> {
    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 other = (Pair) 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 o) {
        return first.compareTo(o.first);
    }
}

class PairIntInt implements Comparable {
    public int first;
    public int second;

    public PairIntInt(int t, int s) {
        this.first = t;
        this.second = s;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + first;
        result = prime * result + second;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        PairIntInt other = (PairIntInt) obj;
        if (first != other.first)
            return false;
        if (second != other.second)
            return false;
        return true;
    }

    @Override
    public int compareTo(PairIntInt o) {
        return Integer.compare(first, o.first);
    }
}

class InitializedBooleanArray {
    private boolean[] values;
    private boolean[] initial_values;
    private int[] epoch;
    private int current_epoch;

    public void init(boolean[] initial_values) {
        current_epoch = 0;
        this.initial_values = Arrays.copyOf(initial_values, initial_values.length);
        values = Arrays.copyOf(initial_values, initial_values.length);
        epoch = new int[values.length];
    }

    public void init(boolean initial_value, int size) {
        current_epoch = 0;
        initial_values = new boolean[size];
        Arrays.fill(initial_values, initial_value);

        this.values = Arrays.copyOf(initial_values, initial_values.length);
        epoch = new int[values.length];
    }

    public void clear() {
        current_epoch++;
    }

    public boolean get(int at) {
        assert (at < values.length);
        if (epoch[at] != current_epoch) {
            epoch[at] = current_epoch;
            values[at] = initial_values[at];
        }
        return values[at];
    }

    public void set(int at, boolean value) {
        assert (at < values.length);
        epoch[at] = current_epoch;
        values[at] = value;
    }
}

class RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 {
    private long mask;
    private long[] used;
    private IntArray indexes;
    private long mask2 = ((1L << 16) - 1L) << 48;

    public RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(int numBits, int capacity) {
        mask = (1L << numBits) - 1L;
        used = new long[1 << numBits];
        indexes = new IntArray(capacity);
    }

    public boolean add(long hash) {
        int index = (int) (hash & mask);
        long value = hash & mask2;

        if ((used[index] & mask2) == value) {
            return false;
        }
        if (((used[index] << 16) & mask2) == value) {
            return false;
        }
        if (((used[index] << 32) & mask2) == value) {
            return false;
        }
        if (((used[index] << 48) & mask2) == value) {
            return false;
        }

        used[index] = (used[index] >>> 16) | value;
        indexes.add(index);

        return true;
    }

    public void clear() {
        for (int i = 0; i < indexes.length; i++) {
            used[indexes.values[i]] = 0;
        }
        indexes.clear();
    }
}

class IntArray {
    public int[] values;
    public int length;

    public IntArray() {
        this(new int[4], 0);
    }

    public IntArray(int capacity) {
        this(new int[capacity], 0);
    }

    public IntArray(int[] values) {
        this(values, values.length);
    }

    public IntArray(int[] values, int length) {
        this.values = values;
        this.length = length;
    }

    public void add(int value) {
        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        values[length++] = value;
    }

    public int remove() {
        return values[--length];
    }

    public boolean contains(int value) {
        for (int i = 0; i < length; i++) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        length = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < length; i++) {
            sb.append(values[i] + ",");
        }
        sb.append("}");
        return sb.toString();
    }

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

    public int remove(int index) {
        if (index >= length) {
            throw new AssertionError();
        }

        if (index == length - 1) {
            return remove();
        }

        int res = values[index];
        System.arraycopy(values, index + 1, values, index, length - (index + 1));
        length--;

        return res;
    }

    public void set(int index, int value) {
        if (index == length) {
            add(value);
            return;
        }

        if (index >= length) {
            throw new AssertionError();
        }

        if (length >= values.length - 1) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        System.arraycopy(values, index, values, index + 1, length - index);
        length++;

        values[index] = value;
    }

    public IntArray copy() {
        return new IntArray(Arrays.copyOf(values, length), length);
    }

    public int[] toArray() {
        return Arrays.copyOf(values, length);
    }

}

class State implements Comparable {

    public State parent;
    public int hi;
    public int chameleonIndex;
    public int sum;
    public int turn;
    public long hash;
    public long[] distances = new long[3];
    public long hand;

    public int getHand(int handIndex) {
        return (int) ((hand >>> (handIndex << 2)) & 15);
    }

    public void setHand(int handIndex, long value) {
        hand &= -1L ^ (15L << (handIndex << 2));
        hand |= (value << (handIndex << 2));
    }

    public int getDistance(int index) {
        int arrayIndex = index >>> 2;
        int c = index & 3;
        return (int) ((distances[arrayIndex] >>> (c << 4)) & ((1 << 16) - 1));
    }

    public void setDistance(int index, long value) {
        int arrayIndex = index >>> 2;
        int c = index & 3;
        distances[arrayIndex] &= -1L ^ (((1L << 16) - 1) << (c << 4));
        distances[arrayIndex] |= (value << (c << 4));
    }

    public int score() {
        int min = (int) 1e9;
        for (int i = 0; i < 10; i++) {
            min = Math.min(min, getDistance(i));
        }
        return min;
    }

    @Override
    public int compareTo(State o) {

        if (sum > o.sum) {
            return -1;
        }
        if (sum < o.sum) {
            return 1;
        }

        return 0;
    }

}




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

}


このページのトップヘ