EvbCFfp1XB

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



Approach koyumeishi さんの IP Solver でこれScreenshot_2019-07-28 TopCoder Forums
が出来るようになったのでやってみた。もう1つは、2箇所変更して、有効な状態を見つけるまでを1回の遷移とするSimulated Annealingです。目安は1位のeldidouさんです。

NIP1時間(最適解)1位の eldidou さんSA
8212121
9262626
10333333
11393939
12464646
13535353
14636363
15717171
16818182
17919192
18103103103
19114114115
20127127128
21139139140
22153153155
23167167169
24182182184
25197197200
26213214217
27230231233
28247248251
29265266269
30284285287
31303304307
32323324329
33344350
34
366371
35386388393
36
411415
37431434440
38
458464
39479482489
40504508513
41
532538
42
559568
43
585596
44
613623
45
641650
46
670683
47
699711
48
730740
49
760773
50
791806
51
823838
52
855869
53
889904
54
922941
55
957976
56
9911006
57
10271044
58
10631083
59
10991120
60
11371155
61
11751198
62
12161233
63
12531278
64
12951320
65
13351357
66
13781401
67
14181443
68
14611489
69
15021529
70
15471580
71
15911622
72
16381673
73
16821716
74
17311762
75
17801810
76
18251858
77
18741912
78
19231960
79
19692008
80
20212060
81
20742111
82
21242167
83
21762211
84
22302272
85
22812322
86
23352386
87
23902438
88
24472490
89
25022550
90
25552608
91
26152662
92
26752724
93
27322780
94
27892848
95
28512911
96
29122961
97
29673029
98
30323098
99
30983158
100
31533222


source code (IP)

from __future__ import print_function
from ortools.linear_solver import pywraplp
from functools import reduce
import sys
import time
import codecs

class MovingNQueens:
    def find2(self, N):
        solver = pywraplp.Solver('SolveIntegerProblem',
            pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

        center = N//2
 
        dy = [  0, -1, -1, -1,  0, 1, 1,  1 ]
        dx = [ -1, -1,  0,  1,  1, 1, 0, -1 ]

        x = [solver.IntVar(0.0, 1.0, 'x_{}_{}'.format(i//N, i%N)) for i in range(N*N)]

        constraints = []
        for i in range(N):
            column = solver.Constraint(1, 1)
            for j in range(N):
                column.SetCoefficient(x[i * N + j], 1)
            constraints.append(column)

        for j in range(N):
            row = solver.Constraint(1, 1)
            for i in range(N):
                row.SetCoefficient(x[i * N + j], 1)
            constraints.append(row)

        for j in range(N):
            i = 0
            diagonal = solver.Constraint(0, 1)
            for l in range(N):
                ni = i + l
                nj = j + l
                if ni>=N or nj>=N:
                    break
                diagonal.SetCoefficient(x[ni * N + nj], 1)
            constraints.append(diagonal)
        for i in range(1,N):
            j = 0
            diagonal = solver.Constraint(0, 1)
            for l in range(N):
                ni = i + l
                nj = j + l
                if ni>=N or nj>=N:
                    break
                diagonal.SetCoefficient(x[ni * N + nj], 1)
            constraints.append(diagonal)

        for j in range(N):
            i = N-1
            diagonal = solver.Constraint(0, 1)
            for l in range(N):
                ni = i - l
                nj = j + l
                if ni<0  or nj>=N:
                    break
                diagonal.SetCoefficient(x[ni * N + nj], 1)
            constraints.append(diagonal)
        for i in range(N-1):
            j = 0
            diagonal = solver.Constraint(0, 1)
            for l in range(N):
                ni = i - l
                nj = j + l
                if ni<0  or nj>=N:
                    break
                diagonal.SetCoefficient(x[ni * N + nj], 1)
            constraints.append(diagonal)

        objective = solver.Objective()
        for i in range(N):
            for j in range(N):
                objective.SetCoefficient(x[i * N + j], max(abs(i - center), abs(j - center)) )

        objective.SetMinimization()

        solver.set_time_limit(60*60*1000)

        start_time = time.time();
        result_status = solver.Solve()
        end_time = time.time();

        if result_status == pywraplp.Solver.OPTIMAL:
            print("{} {}".format("optimal.", solver.Objective().Value()), file=sys.stderr)
        else:
            print("time out.", file=sys.stderr)

        print("time = {} [sec]".format(end_time - start_time), file=sys.stderr)

        row_column = "/* " + str(N) + " " + ("opt" if result_status == pywraplp.Solver.OPTIMAL else "") + " " + str(solver.Objective().Value()) + "*/ {"
        for i in range(N):
            for j in range(N):
                z = i * N + j;
                if x[z].solution_value() == 1:
                    row_column += str(j) + ","
        row_column += "}"
        print("{}".format(row_column), file=codecs.open('./debug.txt', 'a+', 'utf-8'))

mnq = MovingNQueens()
for i in range(8,101):
    ret = mnq.find2(i)



problem https://github.com/kosakkun/MM-Tester/tree/master/SlidingPuzzle

Approach  貪欲法を使いました。現在の状態から、できるだけ良さそうな状態を見つけるのに、 beam search を使いました。
  • 評価関数 : 複数のセルのマンハッタン距離の和 同じなら 全部のセルのマンハッタン距離の和
    • 選ぶ複数のセルの順番はこんな感じ。slidingpazzle
  • beam search
    • 深さ : 最大20
    • 幅 : 最大100
  • beam search とマンハッタン距離の組み合わせは、現在の状態より悪い状態にしてからより良い状態にしにくいので(悪い状態が beam 幅内から除かれる)、対策を考えたがあまりうまくいかなかった。
    • 対策1 : 評価関数を 3x3 のセルが何手で順番通りになるか(一番大きい数字が空と仮定)の和に変えたら、評価関数が0になっても全部正しい位置になってなかったw。
    • 対策2 : 現在の状態より良い状態のみ beam 幅内に含むようにしようとして、 beam search 中に beam search してみたけど、悪い状態が beam 幅内から除かれるのを、 beam search 中の beam search に先送りしただけだった。




seed目安my
1(4x4)3244
2(5x5)154102
3(6x6)256188
4(7x7)2597248
5(8x8)3862412
6(9x9)642
7(10x10)
888

source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class SlidingPuzzle {
    private int R;
    private int C;
    private int ignoreR;
    private int ignoreC;
    private int[][] board;
    private IntSet rxcToNumber;

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

    private static final int[] dr = new int[] { -1, 0, 0, 1, };
    private static final int[] dc = new int[] { 0, -1, 1, 0, };

    private int spaceR;
    private int spaceC;

    private int score;
    private int partScore;

    private int[] moveHistory = new int[1 << 20];
    private int turn;

    private HashSet used2 = new HashSet<>();
    private long[][][] hashes;
    private long hash;

    private boolean[] isTargetNumber;

    private LinkedList> targetNumbersList = new LinkedList<>();

    public static void main(String[] args) {
        new SlidingPuzzle().run();
    }

    private void run() {
        read();
        solve();
        write();
    }

    private void solve() {

        score = calculateScore();
        partScore = calculatePartScore();

        for (; watch.getSecond() < 9.5;) {

            if (partScore > 0) {
                ArrayList moves = beamsearch(20, 100, turn);
                if (moves == null) {
                    Utils.debug("moves == null");
                    continue;
                }
                for (State move : moves) {
                    next(move.r, move.c);
                }
            }

            if (partScore == 0) {
                updateIgnoreRC();

                List targetNumbers = targetNumbersList.pollFirst();
                if (targetNumbers == null) {
                    break;
                }
                for (Integer targetNumber : targetNumbers) {
                    isTargetNumber[targetNumber.intValue()] = true;
                }

                score = calculateScore();
                partScore = calculatePartScore();
                hash = 0;
            } else {
            }
        }
    }

    private void greedy() {
        for (;;) {
            boolean update = false;
            for (int d = 0; d < dr.length; d++) {
                for (int length = 1;; length++) {
                    int nr = spaceR + length * dr[d];
                    int nc = spaceC + length * dc[d];
                    if (nr <= ignoreR || nr >= R) {
                        break;
                    }
                    if (nc <= ignoreC || nc >= C) {
                        break;
                    }

                    int before = calculateScore();

                    next(nr, nc);

                    int after = calculateScore();

                    if (after < before) {
                        update = true;
                    } else {
                        previous();
                    }
                }
            }

            if (!update) {
                break;
            }
        }
    }

    private void updateIgnoreRC() {
        for (int r = ignoreR + 1; r < R - 2; r++) {
            boolean ok = true;
            for (int c = 0; c < C; c++) {
                if (!isTargetNumber[r * C + c]) {
                    ok = !true;
                }
            }
            if (ok) {
                ignoreR = r;
            }
        }
        for (int c = ignoreC + 1; c < C - 2; c++) {
            boolean ok = true;
            for (int r = 0; r < R; r++) {
                if (!isTargetNumber[r * C + c]) {
                    ok = !true;
                }
            }
            if (ok) {
                ignoreC = c;
            }
        }
    }

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth, int currentTurn) {
        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        State best = null;

        used2.clear();
        used2.add(hash);

        State state0 = new State(null, spaceR, spaceC, score, partScore, 0);
        currents.add(state0);

        depthLoop: for (int depth = 0; depth < maxDepth; depth++) {
            if (watch.getSecond() > 59.5) {
                Utils.debug("depth", depth);
                break;
            }
            if (currents.size() == 0) {
                break;
            }
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            Collections.sort(currents);
            for (int beam = 0; beam < beamWidth; beam++) {
                State currentState = currents.get(beam);

                if (currentState != state0) {
                    if (best == null || currentState.compareTo(best) < 0) {
                        best = currentState;
                    }
                    if (currentState.score < 1e-9) {
                        break depthLoop;
                    }
                }

                set(reverse(toList(currentState)), currentTurn);

                int r = currentState.r;
                int c = currentState.c;
                assert spaceR == r;
                assert spaceC == c;
                for (int d = 0; d < dr.length; d++) {
                    for (int length = 1;; length++) {
                        int nr = r + length * dr[d];
                        int nc = c + length * dc[d];
                        if (nr <= ignoreR || nr >= R) {
                            break;
                        }
                        if (nc <= ignoreC || nc >= C) {
                            break;
                        }

                        next(nr, nc);

                        if (used2.add(hash)) {
                            State e = new State(currentState, nr, nc, score, partScore, currentState.numMoves + 1);
                            nexts.add(e);
                        }

                        previous();
                    }
                }

            }
            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }

        for (; turn > currentTurn;) {
            previous();
        }

        if (best == null) {
            return null;
        }

        return reverse(toList(best));

    }

    public static final ArrayList toList(State state0) {
        ArrayList list = new ArrayList<>();
        for (State state = state0; state.parent != null; state = state.parent) {
            list.add(state);
        }
        return list;
    }

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

    private int calculateScore() {
        int score = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                score += calculateScore(r, c);
            }
        }
        return score;
    }

    private int calculatePartScore() {
        int score = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                score += calculatePartScore(r, c);
            }
        }
        return score;
    }

    private int calculateScore(int r, int c) {

        int number = getNumber(r, c);
        if (number == R * C - 1) {
            return 0;
        }
        int nr = number / C;
        int nc = number % C;
        int diff = Math.abs(r - nr) + Math.abs(c - nc);
        return diff;
    }

    private int calculatePartScore(int r, int c) {

        int number = getNumber(r, c);
        if (number == R * C - 1) {
            return 0;
        }
        if (!isTargetNumber[number]) {
            return 0;
        }
        int nr = number / C;
        int nc = number % C;
        int diff = Math.abs(r - nr) + Math.abs(c - nc);
        return diff;
    }

    private void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < turn; i++) {
            int v = moveHistory[startIndex + i];
            int r0 = (v >>> 8) & ((1 << 8) - 1);
            int c0 = (v >>> 0) & ((1 << 8) - 1);

            State state = list.get(i);
            if (state.r == r0 && state.c == c0) {
                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.r, state2.c);
        }
    }

    private void previous() {
        int v = moveHistory[--turn];
        int sr = (v >>> 24) & ((1 << 8) - 1);
        int sc = (v >>> 16) & ((1 << 8) - 1);
        int r0 = (v >>> 8) & ((1 << 8) - 1);
        int c0 = (v >>> 0) & ((1 << 8) - 1);
        move(sr, sc);

    }

    private void next(int r0, int c0) {
        assert r0 >= 0 && r0 < R;
        assert c0 >= 0 && c0 < C;
        moveHistory[turn++] = (spaceR << 24) | (spaceC << 16) | (r0 << 8) | (c0);
        move(r0, c0);
    }

    private void move(int r0, int c0) {
        if (c0 == spaceC && r0 != spaceR) {
            if (r0 < spaceR) {
                for (int r = spaceR; r > r0; r--) {
                    swap2(r, c0, r - 1, c0);
                }
            } else {
                for (int r = spaceR; r < r0; r++) {
                    swap2(r, c0, r + 1, c0);
                }
            }
            spaceR = r0;
            spaceC = c0;
        } else if (c0 != spaceC && r0 == spaceR) {
            if (c0 < spaceC) {
                for (int c = spaceC; c > c0; c--) {
                    swap2(r0, c, r0, c - 1);
                }
            } else {
                for (int c = spaceC; c < c0; c++) {
                    swap2(r0, c, r0, c + 1);
                }
            }
            spaceR = r0;
            spaceC = c0;
        } else {
            Utils.debug(r0, c0, spaceR, spaceC);
            throw new AssertionError();
        }
    }

    private void swap2(int r, int c, int r2, int c2) {
        score -= calculateScore(r, c);
        score -= calculateScore(r2, c2);
        partScore -= calculatePartScore(r, c);
        partScore -= calculatePartScore(r2, c2);
        if (isTargetNumber[getNumber(r, c)]) {
            hash ^= hashes[r][c][getNumber(r, c)];
        }
        if (isTargetNumber[getNumber(r2, c2)]) {
            hash ^= hashes[r2][c2][getNumber(r2, c2)];
        }
        swapRxc(r, c, r2, c2);

        if (isTargetNumber[getNumber(r, c)]) {
            hash ^= hashes[r][c][getNumber(r, c)];
        }
        if (isTargetNumber[getNumber(r2, c2)]) {
            hash ^= hashes[r2][c2][getNumber(r2, c2)];
        }

        score += calculateScore(r, c);
        score += calculateScore(r2, c2);
        partScore += calculatePartScore(r, c);
        partScore += calculatePartScore(r2, c2);
    }

    private void swap(int[][] board, int r0, int c0, int r2, int c2) {
        int swap = board[r0][c0];
        board[r0][c0] = board[r2][c2];
        board[r2][c2] = swap;
    }

    private void print() {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                System.err.format("%3d", 1 + getNumber(r, c));
            }
            System.err.println();
        }
        System.err.println();
    }

    private Point searchPoint() {
        for (int index = 0; index < Math.max(R, C); index++) {
            for (int r = index; r < R - 2; r++) {
                for (int c = 0; c < C; c++) {
                    if (board[r][c] != r * C + c) {
                        if (board[r][c] != R * C - 1) {
                            return new Point(r, c);
                        }
                    }
                }
            }
            for (int c = index; c < C - 2; c++) {
                for (int r = 0; r < R; r++) {
                    if (board[r][c] != r * C + c) {
                        if (board[r][c] != R * C - 1) {
                            return new Point(r, c);
                        }
                    }
                }
            }
        }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (board[r][c] != r * C + c) {
                    if (board[r][c] != R * C - 1) {
                        return new Point(r, c);
                    }
                }
            }
        }

        return null;
    }

    private void read() {
        try (Scanner sc = new Scanner(System.in)) {
            R = sc.nextInt();
            C = sc.nextInt();
            Utils.debug("R", R, "C", C);
            board = new int[R][C];
            rxcToNumber = new IntSet(R * C);
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    board[r][c] = sc.nextInt();
                    if (board[r][c] >= 0) {
                        board[r][c]--;
                    } else {
                        spaceR = r;
                        spaceC = c;
                        board[r][c] = R * C - 1;
                    }
                    rxcToNumber.add(board[r][c]);
                    assert r * C + c == rxcToNumber.indexOf(board[r][c]);
                }
            }
            for (int r = 0; r < R; r++) {
            }

            initHash();

            isTargetNumber = new boolean[R * C];

            for (int r = R - 1, c = C - 2, length = 1; r >= 0 || c >= 0; r--, c--, length++) {
                if (r >= 0) {
                    ArrayList targetNumbers = new ArrayList<>();
                    for (int i = 0, c2 = C - 1; c2 >= 0 && i < length; i++, c2--) {
                        targetNumbers.add(r * C + c2);
                    }
                    if (targetNumbers.size() >= 8) {
                        targetNumbersList.addFirst(targetNumbers.subList(targetNumbers.size() / 2, targetNumbers.size()));
                        targetNumbersList.addFirst(targetNumbers.subList(0, targetNumbers.size() / 2));
                    } else {
                        targetNumbersList.addFirst(targetNumbers);
                    }
                }
                if (c >= 0) {
                    ArrayList targetNumbers = new ArrayList<>();
                    for (int i = 0, r2 = R - 1; r2 >= 0 && i < length; i++, r2--) {
                        targetNumbers.add(r2 * C + c);
                    }
                    if (targetNumbers.size() >= 8) {
                        targetNumbersList.addFirst(targetNumbers.subList(targetNumbers.size() / 2, targetNumbers.size()));
                        targetNumbersList.addFirst(targetNumbers.subList(0, targetNumbers.size() / 2));
                    } else {
                        targetNumbersList.addFirst(targetNumbers);
                    }
                }
            }
            targetNumbersList.pollLast();
            isTargetNumber[R * C - 1] = true;

            List targetNumbers = targetNumbersList.pollFirst();
            for (Integer targetNumber : targetNumbers) {
                isTargetNumber[targetNumber.intValue()] = true;
            }

            ignoreR = -1;
            ignoreC = -1;

            score = calculateScore();

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void initHash() {
        hashes = new long[R][C][R * C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                for (int n = 0; n < R * C; n++) {
                    long l = (long) rng.nextInt();
                    long l2 = (long) rng.nextInt();
                    hashes[r][c][n] = (l << 32) | (l2);
                }
            }
        }
    }

    private void write() {

        System.out.println(turn);
        for (int t = 0; t < turn; t++) {
            int v = moveHistory[t];
            int r = (v >>> 8) & ((1 << 8) - 1);
            int c = (v >>> 0) & ((1 << 8) - 1);
            System.out.println(r + " " + c);
        }
        System.out.flush();
    }

    private int getNumber(int r, int c) {
        return rxcToNumber.get(r * C + c);
    }

    private int getRxc(int number) {
        return rxcToNumber.indexOf(number);
    }

    private void swapNumber(int number, int number2) {
        int rxc = getRxc(number);
        int rxc2 = getRxc(number2);
        rxcToNumber.swap(rxc, rxc2);
        assert rxc == getRxc(number2);
        assert rxc2 == getRxc(number);
    }

    private void swapRxc(int r, int c, int r2, int c2) {
        int rxc = r * C + c;
        int rxc2 = r2 * C + c2;
        int number = getNumber(r, c);
        int number2 = getNumber(r2, c2);
        rxcToNumber.swap(rxc, rxc2);
        assert number2 == getNumber(r, c);
        assert number == getNumber(r2, c2);
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

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

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

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

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

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

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

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

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

}

class Point {
    int r;
    int c;

    public Point(int r, int c) {
        super();
        this.r = r;
        this.c = c;
    }

}

class State implements Comparable {
    State parent;
    int r;
    int c;
    int partScore;
    int score;
    int numMoves;
    double random;

    public State(State parent, int r, int c, int score, int partScore, int numMoves) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.score = score;
        this.partScore = partScore;
        this.numMoves = numMoves;
        random = Math.random();
    }

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

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

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

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

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

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

        size--;
        return true;
    }

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

    public void swap(int index, int index2) {
        assert index < size;
        assert index2 < size;

        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[index2];
        indexToValue[index2] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[index2]] = index2;

    }

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

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

    public int size() {
        return size;
    }

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

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

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

}



problem https://github.com/kosakkun/Typical-MM/tree/master/RectilinearSteinerTree

Approach  山登り法を2種類使いました。

  • 最初の山登り法で、点を追加、削除、移動させる近傍で、シュタイナー木(最小全域木)の上限を抑えます。
  • 2回めの山登り法で、あるパスを削除して、別のパスを追加し直す近傍で、うまく経路を重複させます。
    • この後行われた、MM109のように、ある点を通るパスを全部削除して追加し直すともっと良くなると思います。
      • MM107の頃にやってました。
  • 高速化はしてないです。



seed目安my
1629538
2854780
3664603
4480430
5563498
6688601
7934830
8850759
9581517
10624556


source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

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

    final int[] dc = { 1, 0, -1, 0 };
    final int[] dr = { 0, 1, 0, -1 };
    final int size = 100;

    private int[] c;
    private int[] r;

    private int N;
    private int M;
    private boolean[][] used;
    private boolean[][] used2;

    public static void main(String[] args) {
        new RectilinearSteinerTree().run();
    }

    private void run() {
        read();
        solve();
        write();
    }

    ArrayList solution = new ArrayList<>();
    private long score;

    private void solve() {
        sa.endTime = 9.5 * 0.666;
        SAForMST();
        sa.endTime = 9.5;
        SAForScore();

        for (ArrayList path : pathList) {
            for (Node node : path) {
                int r = node.r;
                int c = node.c;

                if (used[r][c]) {
                    continue;
                }
                used[r][c] = true;
                solution.add(new State(c, r, 0));

            }
        }
//        ArrayList> listlist = new ArrayList<>();
//        for (int i = 0; i < N; i++) {
//            addPoint(0, i);
//        }

    }

    private ArrayList> pathList = new ArrayList<>();
    private ArrayList fromAndToList = new ArrayList<>();
    private MinimumSpanningTree mst;

    private void SAForScore() {
        Utils.debug("M", M);
        for (int i = N; i < N + M; i++) {
            used[r[i]][c[i]] = true;
            solution.add(new State(c[i], r[i], 0));
        }

        mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        mst.kruskal();

        UnionFind unionFind = new UnionFind();
        unionFind.init(N + M);

        score = M;
//        boolean[] used = new boolean[N];
        for (int from = 0; from < N + M; from++) {
//            used[from] = true;
            ArrayList edges = mst.G.get(from);
            for (Edge edge : edges) {
                int to = edge.to;
//                if (used[to]) {
//                    continue;
//                }
//                used[to] = true;

                if (unionFind.isSame(from, to)) {
                    continue;
                }
                unionFind.unite(from, to);

                ArrayList path = dijkstra(from, to);

                pathList.add(path);
                fromAndToList.add((from << 16) | to);

                for (Node node : path) {
                    int r = node.r;
                    int c = node.c;
                    if (used[r][c]) {
                        continue;
                    }
                    count[r][c]++;
                }

                score += path.get(path.size() - 1).numCells;

//                addPoint(from, to);
            }

        }

        double second = Math.ceil(watch.getSecond());

        sa.init();
        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 7) - 1)) == 0) {
                sa.update();

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

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

            mutate();
        }

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

    }

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

        score = calculateMST();

        sa.init();
        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 3) - 1)) == 0) {
                sa.update();

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

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

            mutateForMST();
        }

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

    private void mutateForMST() {
        double random = 3 * rng.nextDouble();
        if (random < 1) {
            addPoint(0);
        } else if (random < 2) {
            removePoint(1);
        } else if (random < 3) {
            movePoint(2);
        }

    }

    private void addPoint(int i) {
        int newR = (int) (size * rng.nextDouble());
        int newC = (int) (size * rng.nextDouble());
        while (used[newR][newC] || used2[newR][newC]) {
            newR = (int) (size * rng.nextDouble());
            newC = (int) (size * rng.nextDouble());
        }

        r[N + M] = newR;
        c[N + M] = newC;
        M++;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
            used2[newR][newC] = true;
        } else {
            M--;
        }
    }

    private void removePoint(int i) {
        if (M == 0) {
            return;
        }

        int m = (int) (M * rng.nextDouble());

        {
            int swap = r[N + m];
            r[N + m] = r[N + M - 1];
            r[N + M - 1] = swap;
        }
        {
            int swap = c[N + m];
            c[N + m] = c[N + M - 1];
            c[N + M - 1] = swap;
        }

        used2[r[N + M - 1]][c[N + M - 1]] = !true;
        M--;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
        } else {
            M++;
            used2[r[N + M - 1]][c[N + M - 1]] = true;
        }
    }

    private void movePoint(int i) {
        if (M == 0) {
            return;
        }

        int m = (int) (M * rng.nextDouble());

        int currentR = r[N + m];
        int currentC = c[N + m];

        int newR = r[N + m] - 1 + (int) (3 * rng.nextDouble());
        int newC = c[N + m] - 1 + (int) (3 * rng.nextDouble());
        newR = Math.min(size - 1, Math.max(0, newR));
        newC = Math.min(size - 1, Math.max(0, newC));
        if (used[newR][newC] || used2[newR][newC]) {
//            newR = newR - 1 + (int) (3 * rng.nextDouble());
//            newC = newC - 1 + (int) (3 * rng.nextDouble());
//            newR = Math.min(size - 1, Math.max(0, newR));
//            newC = Math.min(size - 1, Math.max(0, newC));
            return;
        }

        r[N + m] = newR;
        c[N + m] = newC;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
            used2[currentR][currentC] = !true;
            used2[newR][newC] = true;
        } else {
            r[N + m] = currentR;
            c[N + m] = currentC;
        }
    }

    private long calculateMST() {
        MinimumSpanningTree mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        return mst.kruskal();
    }

    private long calculateScore() {
        MinimumSpanningTree mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        return mst.kruskal();
    }

    private void addPoint2(int from, int to) {

        for (int c = this.c[from], r = this.r[from];;) {
            if (c == this.c[to] && r == this.r[to]) {
                break;
            }

            if (!used[r][c]) {
                used[r][c] = true;
                solution.add(new State(c, r, 0));
            }

            if (c != this.c[to]) {
                if (c < this.c[to]) {
                    c++;
                } else {
                    c--;
                }
            } else if (r != this.r[to]) {
                if (r < this.r[to]) {
                    r++;
                } else {
                    r--;
                }
            }
        }

    }

    int[][] count = new int[size][size];

    private void addPoint(int from, int to) {
        ArrayList path = dijkstra(from, to);
        addPath(path);
    }

    private ArrayList dijkstra(int from, int to) {
        Node toNode = null;
        {
            PriorityQueue queue = new PriorityQueue<>();
            int[][] used = new int[size][size];
            for (int r = 0; r < size; r++) {
                Arrays.fill(used[r], (int) 1e9);
            }

            {
                queue.add(new Node(null, r[from], c[from], 0));
                used[r[from]][c[from]] = 0;
//            count[r[from]][c[from]]++;
            }
            for (; !queue.isEmpty();) {
                Node node = queue.poll();
                int numCells = node.numCells;
                int r = node.r;
                int c = node.c;

                if (r == this.r[to] && c == this.c[to]) {
                    toNode = node;
                    break;
                }

                for (int d = 0; d < dr.length; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || nr >= size) {
                        continue;
                    }
                    if (nc < 0 || nc >= size) {
                        continue;
                    }

                    int nNumCells = numCells;
                    if (!this.used[nr][nc] && count[nr][nc] == 0) {
                        nNumCells++;
                    }

                    if (nNumCells >= used[nr][nc]) {
                        continue;
                    }
                    used[nr][nc] = nNumCells;
                    queue.add(new Node(node, nr, nc, nNumCells));
//                count[nr][nc]++;
                }

            }
        }

        if (toNode == null) {
            return null;
        }

        ArrayList path = reverse(toList(toNode));
        return path;
    }

    private void addPath(ArrayList list) {
        for (int i = 0; i < list.size(); i++) {
            Node n = list.get(i);
            int r = n.r;
            int c = n.c;
            count[r][c]++;
            if (used[r][c]) {
                continue;
            }
            if (used2[r][c]) {
                continue;
            }
            used2[r][c] = true;
            solution.add(new State(c, r, 0));
        }
    }

    private void removePath(ArrayList list) {
        for (int i = 0; i < list.size(); i++) {
            Node n = list.get(i);
            int r = n.r;
            int c = n.c;
//            if (!used2[r][c]) {
//                continue;
//            }
            used2[r][c] = !true;
            count[r][c]--;
            solution.remove(new State(c, r, 0));
        }
    }

    public static final ArrayList toList(Node node) {
        ArrayList list = new ArrayList<>();
        for (Node current = node; current != null; current = current.parent) {
            list.add(current);
        }
        return list;
    }

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

    private int manhattanDistance(int i, int j) {
        return Math.abs(c[i] - c[j]) + Math.abs(r[i] - r[j]);
    }

    private Point FermatPoint(int a, int b, int c) {
        double da = dist(b, c);
        double db = dist(a, c);
        double dc = dist(a, b);

        if (da * da >= db * db + dc * dc + db * dc)
            return null;
        if (db * db >= dc * dc + da * da + dc * da)
            return null;
        if (dc * dc >= da * da + db * db + da * db)
            return null;

        double A = Math.acos((db * db + dc * dc - da * da) / (2 * db * dc));
        double B = Math.acos((dc * dc + da * da - db * db) / (2 * dc * da));
        double C = Math.acos((da * da + db * db - dc * dc) / (2 * da * db));

        double ra = csc(A + Math.PI / 3);
        double rb = csc(B + Math.PI / 3);
        double rc = csc(C + Math.PI / 3);

        double wa = da * ra;
        double wb = db * rb;
        double wc = dc * rc;

        double wall = wa + wb + wc;

        double x = this.c[a] * wa + this.c[b] * wb + this.c[c] * wc;
        double y = this.r[a] * wa + this.r[b] * wb + this.r[c] * wc;
        return new Point((int) (0.5 + x / wall), (int) (0.5 + y / wall));
    }

    private double csc(double x) {
        return 1.0 / Math.sin(x);
    }

    private double dist(int a, int b) {
        int dx = c[a] - c[b];
        int dy = r[a] - r[b];
        return Math.sqrt(dx * dx + dy * dy);
    }

//    private void SA() {
//        double second = Math.ceil(watch.getSecond());
//
//        sa.init();
//        for (;; ++sa.numIterations) {
//            if ((sa.numIterations & ((1 << 7) - 1)) == 0) {
//                sa.update();
//
//                if (sa.isTLE()) {
//                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
//                    break;
//                }
//
//                if (sa.time > second) {
//                    second++;
//                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
//                }
//            }
//
//            mutate();
//        }
//
//        Utils.debug("SA", "time", watch.getSecondString());
//
//    }

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

    private void removeAndAdd(int index0) {
        int index = (int) (pathList.size() * rng.nextDouble());

//        Collections.swap(pathList, index, pathList.size() - 1);
//        Collections.swap(fromAndToList, index, fromAndToList.size() - 1);
//        index = pathList.size() - 1;

        ArrayList path = pathList.get(index);
//        int before = path.get(path.size() - 1).numCells;

        int before = 0;
        for (Node node : path) {
            int r = node.r;
            int c = node.c;
            if (used[r][c]) {
                continue;
            }
            count[r][c]--;
            if (count[r][c] == 0) {
                before++;
            }
        }

        int v = fromAndToList.get(index).intValue();
        int from = v >>> 16;
        int to = v & ((1 << 16) - 1);

        ArrayList newPath = rng.nextDouble() < 0.5 ? dijkstra(from, to) : dijkstra(to, from);

        int after = newPath.get(newPath.size() - 1).numCells;
//        int after  = 0;
//        for (Node node : path) {
//            int r = node.r;
//            int c = node.c;
//            if (used[r][c]) {
//                continue;
//            }
//            count[r][c]--;
//            if (count[r][c] == 0) {
//                before++;
//            }
//        }

        double deltaScore = after - before;

        if (sa.accept(deltaScore / Math.abs(score))) {
//            if (after != before) {
//                Utils.debug("after, before, path.size(), newPath.size()", after, before, path.size(), newPath.size());
//            }
            score += deltaScore;
            pathList.set(index, newPath);
            for (Node node : newPath) {
                int r = node.r;
                int c = node.c;
                if (used[r][c]) {
                    continue;
                }
                count[r][c]++;
            }
//            int score2 = M;
//            for (ArrayList path2 : pathList) {
//                score2 += path2.get(path2.size() - 1).numCells;
//            }
//            if (score2 != score) {
//                Utils.debug(score2, score);
//            }
        } else {
            for (Node node : path) {
                int r = node.r;
                int c = node.c;
                if (used[r][c]) {
                    continue;
                }
                count[r][c]++;
            }
//            int score2 = M;
//            for (ArrayList path2 : pathList) {
//                score2 += path2.get(path2.size() - 1).numCells;
//            }
//            if (score2 != score) {
//                Utils.debug(score2, score);
//            }
        }
    }

    private boolean isConnected(UnionFind unionFind) {
        for (int i = 0; i < N; i++) {
            if (unionFind.getRoot(r[0] * size + c[0]) != unionFind.getRoot(r[i] * size + c[i])) {
                return false;
            }
        }
        return true;
    }

    private void print(double[][] life) {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                System.err.format("%6.3f", life[r][c]);
            }
            System.err.println();
        }
    }

    private void print(boolean[][] b) {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                System.err.format("%s", used[c][r] ? "X" : b[c][r] ? "*" : " ");
            }
            System.err.println();
        }
        System.err.println();
    }

    private void read() {
        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            Utils.debug("N", N);
            used = new boolean[size][size];
            used2 = new boolean[size][size];
            c = new int[10 * N];
            r = new int[10 * N];
            for (int i = 0; i < N; i++) {
                c[i] = sc.nextInt();
                r[i] = sc.nextInt();
                used[r[i]][c[i]] = true;
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void write() {
//        System.out.println(size * size - N);
//        for (int x = 0; x < size; x++) {
//            for (int y = 0; y < size; y++) {
//                if (!used[x][y]) {
//                    System.out.println(x + " " + y);
//                }
//            }
//        }
//        System.out.flush();
        System.out.println(solution.size());
        for (State state : solution) {
            System.out.println(state.x + " " + state.y);
        }
        System.out.flush();
    }

}

class State implements Comparable {
    int x;
    int y;
    double life;

    public State(int x, int y, double life) {
        super();
        this.x = x;
        this.y = y;
        this.life = life;
    }

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

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

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

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

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

        startTime = useTime ? RectilinearSteinerTree.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 ? RectilinearSteinerTree.watch.getSecond() : numIterations;
    }

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

    public boolean accept(double deltaScore) {
        return acceptS(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 (RectilinearSteinerTree.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 (RectilinearSteinerTree.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 double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

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

}

class UnionFind {
    private int[] par;
    private int[] rank;

    public void init(int n) {
        par = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    public int getRoot(int x) {
        if (par[x] == x) {
            return x;
        } else {
            par[x] = getRoot(par[x]);
            return par[x];
        }
    }

    public void unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

    public boolean isSame(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}

class Edge {
    int to;
    int cost;

    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

class Edge2 {
    int from;
    int to;
    int cost;

    public Edge2(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

class MinimumSpanningTree {

    private static final int INF = (int) 1e9;
    ArrayList> G;
    private ArrayList edges;
    private int numVertexes;
    // private int[] dist;
    // private int[] prevv;
    // private int[] preve;

    public MinimumSpanningTree(int v) {
        clear(v);
    }

    public void clear(int v) {
        this.numVertexes = v;

        G = new ArrayList>();
        for (int i = 0; i < v; i++) {
            G.add(new ArrayList());
        }
        edges = new ArrayList();

        // dist = new int[v];
        // prevv = new int[v];
        // preve = new int[v];
    }

    public void addEdge(int from, int to, int cost) {
        assert cost >= 0;
        assert cost <= INF;

        // G.get(from).add(new Edge(to, cost));
        // G.get(to).add(new Edge(from, cost));

        edges.add(new Edge2(from, to, cost));
    }

    public int kruskal() {
        UnionFind unionFind = new UnionFind();
        unionFind.init(numVertexes);

        Collections.sort(edges, new Comparator() {
            @Override
            public int compare(Edge2 o1, Edge2 o2) {
                if (o1.cost < o2.cost) {
                    return -1;
                }
                if (o1.cost > o2.cost) {
                    return 1;
                }
                return 0;
            }
        });

        int cost = 0;
        int numEdges = 0;
        for (Edge2 edge2 : edges) {
            if (unionFind.isSame(edge2.from, edge2.to)) {
                continue;
            }
            unionFind.unite(edge2.from, edge2.to);

            G.get(edge2.from).add(new Edge(edge2.to, edge2.cost));
            G.get(edge2.to).add(new Edge(edge2.from, edge2.cost));

            cost += edge2.cost;
            numEdges++;
            if (numEdges >= numVertexes - 1) {
                break;
            }
        }
        return cost;
    }

    public int prim() {

        ArrayList> G = new ArrayList<>();
        for (int i = 0; i < numVertexes; i++) {
            G.add(new ArrayList<>());
        }
        for (Edge2 edge2 : edges) {
            G.get(edge2.from).add(new Edge2(edge2.from, edge2.to, edge2.cost));
            G.get(edge2.to).add(new Edge2(edge2.to, edge2.from, edge2.cost));
        }

        int cost = 0;
        int numEdges = 0;

        boolean[] used = new boolean[numVertexes];
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Edge2 o1, Edge2 o2) {
                if (o1.cost < o2.cost) {
                    return -1;
                }
                if (o1.cost > o2.cost) {
                    return 1;
                }
                return 0;
            }
        });
        {
            int vertex = (int) (numVertexes * Math.random());
            pq.add(new Edge2(vertex, vertex, 0));
        }
        for (; !pq.isEmpty();) {
            Edge2 current = pq.poll();

            if (used[current.to]) {
                continue;
            }

            used[current.to] = true;
            cost += current.cost;

            if (current.from != current.to) {
                numEdges++;
                if (numEdges == numVertexes - 1) {
                    break;
                }

                this.G.get(current.from).add(new Edge(current.to, current.cost));
                this.G.get(current.to).add(new Edge(current.from, current.cost));
            }

            for (Edge2 edge : G.get(current.to)) {
                if (used[edge.to]) {
                    continue;
                }
                pq.add(edge);
            }

        }

        return cost;
    }

}

class Point implements Comparable {

    public int x;
    public int y;

    public Point() {
        this(0, 0);
    }

    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    public Point add(Point point) {
        return new Point(x + point.x, y + point.y);
    }

    public Point subtract(Point point) {
        return new Point(x - point.x, y - point.y);
    }

    public Point multiply(int a) {
        return new Point(a * x, a * y);
    }

    public Point divide(int a) {
        // BigInteger.ONE.divide(val)(val)
        return new Point(x / a, y / a);
    }

    public int cross(Point point) {
        return x * point.y - y * point.x;
    }

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

    public Point operator(Point a) {
        return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
    }

    // public boolean operator<(const Point&p)const
    //
    // {
    // return !equals(x, p.x) ? x < p.x : (!equals(y, p.y) && y < p.y);
    // }
    @Override
    public int compareTo(Point o) {
        if (x == o.x) {
            if (y == o.y) {
                return 0;
            } else if (y < o.y) {
                return -1;
            } else {
                return 1;
            }
        } else if (x < o.x) {
            return -1;
        } else {
            return 1;
        }
    }

    // bool operator==(const Point&p)const
    //
    // {
    // return fabs(x - p.x) < EPSILON && fabs(y - p.y) < EPSILON;
    // }

    @Override
    public String toString() {
        // return "Point [x=" + x + ", y=" + y + "]";
        return "(" + x + "," + y + ")";
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + x;
            result = prime * result + y;
            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;
        Point other = (Point) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

}

class Node implements Comparable {
    Node parent;
    int numCells;
    int r;
    int c;
    double random;

    public Node(Node parent, int r, int c, int numCells) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.numCells = numCells;
        random = RectilinearSteinerTree.rng.nextDouble();
    }

    @Override
    public int compareTo(Node o) {
        if (numCells < o.numCells) {
            return -1;
        }
        if (numCells > o.numCells) {
            return 1;
        }
        if (random < o.random) {
            return -1;
        }
        if (random > o.random) {
            return 1;
        }
        return 0;
    }
}


このページのトップヘ