Example scores:
0) 12.0
1) 14673.0
2) 727.0
3) 27.0
4) 4162.0
5) 465.0
6) 7921.0
7) 6024.0
8) 49.0
9) 2874.0
Approach
- N<=10 : ビームサーチを1回使いました。
- 10<N<=40 : 深さ20のビームサーチを9秒間使い続けた解と、すべての数のマンハッタン距離が6以下の状態まで戻して、貪欲に端からそろえる解の良い方を返しました。
- 子の生成 :
- 2x2と3x3だけ
- R,Lを1回
- Rotationせずにシミュレーションすることで、2倍くらい高速化できました。
- N<=10のときは全部の位置からRotationする
- 10<N<=40のときは、1つ数を選んで、その数が2x2または3x3に含まれる位置のもう1つ外側からRotationする
- 盤面重複の除去 : Zobrist Hashing
- 評価関数 : 4*この問題のスコア + max(abs(r1-r2),abs(c1-c2)) * (abs(r1-r2)+abs(c1-c2))
- その他の工夫 : 中途半端にいい位置にすると、位置のペナルティを0にしたときのスコアの改善量よりRotationのペナルティの方が大きくなって、位置のペナルティが0にならなくなるので、5x5の範囲がP*5*5以下のペナルティになったときは、ビーム幅を2倍、Rotationする位置ももう1つじゃなくて2つ外側の位置からに増やして、ペナルティを0にしやすくした。
感想 ちゃんと差がつくいい問題だった。 ただ基本的に、まわしてそろえるなので、去年参加した人は強そうだな~と思った。 kosakkunさんのところにも似たようなのがあって、やったことある人は強そうだな~と思った。
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.HashSet; import java.util.PriorityQueue; import java.util.Random; class Solver { private final int N; private final int P; private final int[][] rxcToNumber; private final int[] numberToR; private final int[] numberToC; private final ArrayListmoves = new ArrayList<>(); private final int[] rotatePenalties; private int sumRotatePenalty; private final long[][][] hashes; private long hash; private int[][][] evaluations; private final XorShift rng = new XorShift(System.nanoTime()); private final Watch watch = new Watch(); private Comparator comparator = new Comparator () { @Override public int compare(State o1, State o2) { if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) { return -1; } if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) { return 1; } int coef = 10; if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) { return -1; } if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) { return 1; } return 0; } }; private Comparator comparator2 = new Comparator () { @Override public int compare(State o1, State o2) { int coef = 4; if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) { return -1; } if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) { return 1; } return 0; } }; private Comparator comparator6 = new Comparator () { @Override public int compare(State2 o1, State2 o2) { if (o1.gridPenalty2 < o2.gridPenalty2) { return -1; } if (o1.gridPenalty2 > o2.gridPenalty2) { return 1; } if (o1.distance < o2.distance) { return -1; } if (o1.distance > o2.distance) { return 1; } if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) { return -1; } if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) { return 1; } return 0; } }; private int baseDepth6 = -1; private ArrayList moveHistory6 = new ArrayList (); private ArrayList moveHistoryGreedy = new ArrayList (); public Solver(int N, int P, int[][] grid) { this.N = N; this.P = P; rxcToNumber = grid; numberToR = new int[N * N]; numberToC = new int[N * N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { grid[r][c]--; numberToR[grid[r][c]] = r; numberToC[grid[r][c]] = c; } } rotatePenalties = new int[N + 1]; for (int n = 2; n <= N; n++) { rotatePenalties[n] = (int) (1e-9 + Math.pow(n - 1, 1.5)); } hashes = new long[N][N][N * N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { for (int number = 0; number < N * N; number++) { hashes[r][c][number] = rng.nextLong(); } } } hash = 0; evaluations = new int[N][N][N * N]; Utils.debug("N", N, "P", P); } public void solve() { if (N <= 10) { solveOneBeam(); } else if (N <= 40) { solveBeam2(); ArrayList bestMoveHistory = new ArrayList (); for (int i = 0; i < moveHistory.size(); i++) { Move move = moveHistory.get(i); bestMoveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); } int bestScore = calculateGridPenalty() + sumRotatePenalty; Utils.debug("bestScore", bestScore, calculateGridPenalty(), sumRotatePenalty); for (; moveHistory.size() > 0;) { sumRotatePenalty -= rotatePenalties[moveHistory.get(moveHistory.size() - 1).size]; previous(); } for (int i = 0; i < moveHistory6.size(); i++) { Move move = moveHistory6.get(i); for (int j = 0; j < move.numRotations; j++) { sumRotatePenalty += rotatePenalties[move.size]; } next(move.r, move.c, move.size, move.dir, move.numRotations); } Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty); greedy(); int score = calculateGridPenalty() + sumRotatePenalty; Utils.debug("score", score, calculateGridPenalty(), sumRotatePenalty); if (score < bestScore) { moves.clear(); for (int i = 0; i < moveHistory6.size(); i++) { Move move = moveHistory6.get(i); moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); } for (int i = 0; i < moveHistoryGreedy.size(); i++) { Move move = moveHistoryGreedy.get(i); moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); } } else { moves.clear(); for (int i = 0; i < bestMoveHistory.size(); i++) { Move move = bestMoveHistory.get(i); moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); } } } } private void greedy() { int[] numbers = new int[N * N]; { boolean[][] used = new boolean[N][N]; int index = 0; for (int i = 0; i < N; i++) { { int r = i; for (int c = 0; c < N; c++) { if (used[r][c]) { continue; } used[r][c] = true; numbers[index] = r * N + c; index++; } } { int c = i; for (int r = 0; r < N; r++) { if (used[r][c]) { continue; } used[r][c] = true; numbers[index] = r * N + c; index++; } } } } for (int index = 0; index < N * N; index++) { if (index >= N * N - 16) { ArrayList moves = beamsearch4x4(20, 1000); for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); sumRotatePenalty += rotatePenalties[move.size]; rotate(move.r, move.c, move.size, move.dir); } } break; } int number = numbers[index]; if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) { evaluations[numberToR[number]][numberToC[number]][number] = -1; continue; } ArrayList moves = dijkstra(number); for (int i = 0; i < moves.size(); i++) { State2 move = moves.get(i); this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); sumRotatePenalty += rotatePenalties[move.size]; rotate(move.r, move.c, move.size, move.dir); } } if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) { evaluations[numberToR[number]][numberToC[number]][number] = -1; continue; } if (getTargetRow(number) < N - 1 && getTargetColumn(number) < N - 1) { for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { System.err.format("%3d", rxcToNumber[r][c]); } System.err.println(); } assert false; } { if (numberToC[number] == N - 1) { this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1)); this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number] - 1, numberToC[number] - 2, 2, 'L'); this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1)); this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'L'); this.moveHistoryGreedy.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1)); this.moves.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number], numberToC[number] - 2, 2, 'R'); if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) { evaluations[numberToR[number]][numberToC[number]][number] = -1; continue; } } if (numberToR[number] == N - 1) { this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1)); this.moves.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number] - 2, numberToC[number] - 1, 2, 'R'); this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1)); this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'R'); this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1)); this.moves.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1)); sumRotatePenalty += rotatePenalties[2]; rotate(numberToR[number] - 2, numberToC[number], 2, 'L'); if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) { evaluations[numberToR[number]][numberToC[number]][number] = -1; continue; } } assert false; } } int score = calculateGridPenalty() + sumRotatePenalty; Utils.debug("greedy", "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString()); } private ArrayList dijkstra(int number) { int baseDepth = moveHistory.size(); int goalR = getTargetRow(number); int goalC = getTargetColumn(number); if (goalC == N - 1) { goalR++; } else if (goalR == N - 1) { goalC++; } HashSet usedHash = new HashSet (); boolean[][] used = new boolean[N][N]; PriorityQueue pq = new PriorityQueue<>(comparator6); State2 best = null; final int calculateGridPenalty3 = calculateGridPenalty3(); { State2 e = new State2(null, -1, -1, -1, 'L', 1, calculateGridPenalty(), sumRotatePenalty, calculateGridPenalty3, manhattanDistance(goalR, goalC, numberToR[number], numberToC[number]), 1000000); pq.add(e); usedHash.add(hash); best = e; } int numPolls = 0; for (; !pq.isEmpty();) { State2 currentState = pq.poll(); numPolls++; ArrayList moves2 = reverse2(toList(currentState)); set2(moves2, baseDepth); final int r0 = numberToR[number]; final int c0 = numberToC[number]; used[r0][c0] = true; if (currentState.distance == 0) { best = currentState; break; } int margin = 0; for (int size = 2; size <= 2; size++) { int startR = Math.max(0, r0 - (size - 1) - margin); int endR = Math.min(N - 1, r0 + margin); int startC = Math.max(0, c0 - (size - 1) - margin); int endC = Math.min(N - 1, c0 + margin); for (int r = startR; r <= endR; r++) { for (int c = startC; c <= endC; c++) { if (!canRotate(r, c, size)) { continue; } int currentGridPenalty = calculateGridPenalty(r, c, size); int currentGridPenalty3 = calculateGridPenalty3(r, c, size); long currentHash = calculateHash(r, c, size); { int i = 1; long e = hash ^ currentHash ^ calculateHashR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyR(r, c, size); int gridPenalty3 = calculateGridPenalty3R(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size; int nextR = isOut ? r0 : calculateNextR_R(r, c, size, r0 - r, c0 - c); int nextC = isOut ? c0 : calculateNextC_R(r, c, size, r0 - r, c0 - c); int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3; if (nextPenalty3 <= calculateGridPenalty3) { pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0)); } } } { int i = 3; long e = hash ^ currentHash ^ calculateHashRRR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyRRR(r, c, size); int gridPenalty3 = calculateGridPenalty3RRR(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size; int nextR = isOut ? r0 : calculateNextR_RRR(r, c, size, r0 - r, c0 - c); int nextC = isOut ? c0 : calculateNextC_RRR(r, c, size, r0 - r, c0 - c); int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3; if (nextPenalty3 <= calculateGridPenalty3) { pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0)); } } } } } } } for (; moveHistory.size() > baseDepth;) { previous(); } return reverse2(toList(best)); } private void solveBeam() { int bestScore = (int) 1e9; int numBeams = 0; int numMoves0 = 0; int numMovesNot0AndNotUpdateBest = 0; for (; watch.getSecond() < 9.5; numBeams++) { if (numBeams % 50 == 0) { Utils.debug("numBeams", numBeams, "bestScore", bestScore); } int worstNumber = -1; int worst = -1; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c])); if (distance <= 0) { continue; } distance = distance * 1000 + (int) (5000 * rng.nextDouble()); if (distance > worst) { worst = distance; worstNumber = rxcToNumber[r][c]; } } } if (worstNumber == -1) { break; } int maxDepth = 10; int maxWidth = 10; if (N == 8) { maxDepth = 20; maxWidth = 100; } else if (N == 9) { maxDepth = 20; maxWidth = 100; } else if (N == 10) { maxDepth = 10; maxWidth = 300; } else if (N >= 10 && N < 15) { maxDepth = 10; maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N)); } else if (N == 15) { maxDepth = 10; maxWidth = 125; } else if (N >= 15 && N < 20) { maxDepth = 10; maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N)); } else if (N == 20) { maxDepth = 10; maxWidth = 50; } else if (N >= 20 && N < 25) { maxDepth = 10; maxWidth = (int) (26 + 4.8 * (25 - N)); } else if (N == 25) { maxDepth = 10; maxWidth = 26; } else if (N >= 25 && N < 30) { maxDepth = 10; maxWidth = (int) (16 + 2 * (30 - N)); } else if (N == 30) { maxDepth = 10; maxWidth = 16; } else if (N >= 30 && N <= 40) { maxDepth = 10; maxWidth = 6 + 40 - N; } else if (N == 40) { maxDepth = 10; maxWidth = 6; } maxDepth = 20; ArrayList moves = null; if (useOtherBeam(worstNumber)) { moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth); } else { moves = beamsearch(worstNumber, maxDepth, maxWidth); } if (moves.size() == 0) { numMoves0++; continue; } int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty; if (score < bestScore) { bestScore = score; for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); rotate(move.r, move.c, move.size, move.dir); sumRotatePenalty += rotatePenalties[move.size]; } } assert score == calculateGridPenalty() + sumRotatePenalty; } else { numMovesNot0AndNotUpdateBest++; for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); rotate(move.r, move.c, move.size, move.dir); sumRotatePenalty += rotatePenalties[move.size]; } } } } int score = calculateGridPenalty() + sumRotatePenalty; Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString()); Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest); } private void solveBeam2() { int bestScore = (int) 1e9; int numBeams = 0; int numMoves0 = 0; int numMovesNot0AndNotUpdateBest = 0; for (; watch.getSecond() < 9.0; numBeams++) { if (numBeams % 50 == 0) { Utils.debug("numBeams", numBeams, "bestScore", bestScore); } int worstNumber = -1; int worst = -1; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c])); if (distance <= 6) { continue; } distance = distance * 1000 + (int) (5000 * rng.nextDouble()); if (distance > worst) { worst = distance; worstNumber = rxcToNumber[r][c]; } } } if (worstNumber == -1) { if (baseDepth6 == -1) { baseDepth6 = moveHistory.size(); for (int i = 0; i < moveHistory.size(); i++) { Move move = moveHistory.get(i); moveHistory6.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); } Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty); } for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c])); if (distance <= 0) { continue; } distance = distance * 1000 + (int) (5000 * rng.nextDouble()); if (distance > worst) { worst = distance; worstNumber = rxcToNumber[r][c]; } } } if (worstNumber == -1) { break; } } int maxDepth = 10; int maxWidth = 10; if (N == 8) { maxDepth = 20; maxWidth = 100; } else if (N == 9) { maxDepth = 20; maxWidth = 100; } else if (N == 10) { maxDepth = 10; maxWidth = 300; } else if (N >= 10 && N < 15) { maxDepth = 10; maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N)); } else if (N == 15) { maxDepth = 10; maxWidth = 125; } else if (N >= 15 && N < 20) { maxDepth = 10; maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N)); } else if (N == 20) { maxDepth = 10; maxWidth = 50; } else if (N >= 20 && N < 25) { maxDepth = 10; maxWidth = (int) (26 + 4.8 * (25 - N)); } else if (N == 25) { maxDepth = 10; maxWidth = 26; } else if (N >= 25 && N < 30) { maxDepth = 10; maxWidth = (int) (16 + 2 * (30 - N)); } else if (N == 30) { maxDepth = 10; maxWidth = 16; } else if (N >= 30 && N <= 40) { maxDepth = 10; maxWidth = 6 + 40 - N; } else if (N == 40) { maxDepth = 10; maxWidth = 6; } maxDepth = 20; ArrayList moves = null; if (useOtherBeam(worstNumber)) { moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth); } else { moves = beamsearch(worstNumber, maxDepth, maxWidth); } if (moves.size() == 0) { numMoves0++; continue; } int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty; if (score < bestScore) { bestScore = score; for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); rotate(move.r, move.c, move.size, move.dir); sumRotatePenalty += rotatePenalties[move.size]; } } assert score == calculateGridPenalty() + sumRotatePenalty; } else { numMovesNot0AndNotUpdateBest++; for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations)); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); rotate(move.r, move.c, move.size, move.dir); sumRotatePenalty += rotatePenalties[move.size]; } } } } int score = calculateGridPenalty() + sumRotatePenalty; Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString()); Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest); } private boolean useOtherBeam(int number) { int r = numberToR[number]; int c = numberToC[number]; r = Math.max(2, Math.min(N - 3, r)); c = Math.max(2, Math.min(N - 3, c)); int startR = r - 2; int startC = c - 2; int endR = r + 3; int endC = c + 3; return calculateGridPenalty(startR, startC, Math.min(endR - startR, endC - startC)) <= P * (endR - startR) * (endC - startC); } private void solveOneBeam() { int bestScore = (int) 1e9; int numBeams = 0; { int maxDepth = 1000; int maxWidth = 10; if (N == 4) { maxDepth = 25; maxWidth = 18000; } else if (N == 5) { maxDepth = 40; maxWidth = 6000; } else if (N == 6) { maxDepth = 60; maxWidth = 2500; } else if (N == 7) { maxDepth = 100; maxWidth = 1100; } else if (N == 8) { maxDepth = 150; maxWidth = 550; } else if (N == 9) { maxDepth = 220; maxWidth = 280; } else if (N == 10) { maxDepth = 320; maxWidth = 150; } ArrayList moves = beamsearch(maxDepth, maxWidth); int[] counts = new int[30]; int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty; if (score < bestScore) { bestScore = score; for (int i = 0; i < moves.size(); i++) { State move = moves.get(i); for (int j = 0; j < move.numRotations; j++) { this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1)); rotate(move.r, move.c, move.size, move.dir); sumRotatePenalty += rotatePenalties[move.size]; counts[move.size]++; } } assert score == calculateGridPenalty() + sumRotatePenalty : Utils.toString(moves.get(moves.size() - 1).gridPenalty, moves.get(moves.size() - 1).sumRotatePenalty, calculateGridPenalty(), sumRotatePenalty); } Utils.debug("counts", counts); } int score = calculateGridPenalty() + sumRotatePenalty; Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString()); } private boolean canRotate(int r, int c, int size) { return r >= 0 && c >= 0 && r + size <= N && c + size <= N; } private void rotate(int r0, int c0, int n, char dir0) { hash ^= calculateHash(r0, c0, n); if (dir0 == 'R') { for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) { for (int c = 0; c <= halfN2; c++) { int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c]; rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + m - c][c0 + 0 + r]; rxcToNumber[r0 + m - c][c0 + 0 + r] = rxcToNumber[r0 + m - r][c0 + m - c]; rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + 0 + c][c0 + m - r]; rxcToNumber[r0 + 0 + c][c0 + m - r] = swapppppppppppppppppppppppppppp; } } } else { for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) { for (int c = 0; c <= halfN2; c++) { int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c]; rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + 0 + c][c0 + m - r]; rxcToNumber[r0 + 0 + c][c0 + m - r] = rxcToNumber[r0 + m - r][c0 + m - c]; rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + m - c][c0 + 0 + r]; rxcToNumber[r0 + m - c][c0 + 0 + r] = swapppppppppppppppppppppppppppp; } } } hash ^= calculateHash(r0, c0, n); updateNumberToRxc(r0, c0, n); } private int calculateNextR_R(int r0, int c0, int size0, int r, int c) { return r0 + 0 + c; } private int calculateNextR_RR(int r0, int c0, int size0, int r, int c) { return r0 + (size0 - 1) - r; } private int calculateNextR_RRR(int r0, int c0, int size0, int r, int c) { return r0 + (size0 - 1) - c; } private int calculateNextC_R(int r0, int c0, int size0, int r, int c) { return c0 + (size0 - 1) - r; } private int calculateNextC_RR(int r0, int c0, int size0, int r, int c) { return c0 + (size0 - 1) - c; } private int calculateNextC_RRR(int r0, int c0, int size0, int r, int c) { return c0 + 0 + r; } private int calculateGridPenaltyR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - c][c0 + 0 + r]; penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenaltyRR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - r][c0 + m - c]; penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenaltyRRR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + 0 + c][c0 + m - r]; penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty(int r0, int c0, int size0) { int penalty = 0; for (int r = r0; r < r0 + size0; r++) { for (int c = c0; c < c0 + size0; c++) { int number = rxcToNumber[r][c]; penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty() { int penalty = 0; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int number = rxcToNumber[r][c]; penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty3R(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - c][c0 + 0 + r]; penalty += evaluations[r0 + r][c0 + c][number]; } } return penalty; } private int calculateGridPenalty3RR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - r][c0 + m - c]; penalty += evaluations[r0 + r][c0 + c][number]; } } return penalty; } private int calculateGridPenalty3RRR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + 0 + c][c0 + m - r]; penalty += evaluations[r0 + r][c0 + c][number]; } } return penalty; } private int calculateGridPenalty3(int r0, int c0, int size0) { int penalty = 0; for (int r = 0; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + r][c0 + c]; penalty += evaluations[r0 + r][c0 + c][number]; } } return penalty; } private int calculateGridPenalty3() { int penalty = 0; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int number = rxcToNumber[r][c]; penalty += evaluations[r][c][number]; } } return penalty; } private int calculateGridPenalty2R(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - c][c0 + 0 + r]; penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty2RR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - r][c0 + m - c]; penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty2RRR(int r0, int c0, int size0) { int penalty = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + 0 + c][c0 + m - r]; penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty2(int r0, int c0, int size0) { int penalty = 0; for (int r = r0; r < r0 + size0; r++) { for (int c = c0; c < c0 + size0; c++) { int number = rxcToNumber[r][c]; penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } private int calculateGridPenalty2() { int penalty = 0; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { int number = rxcToNumber[r][c]; penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number)); } } return P * penalty; } public String[] makeSolution() { String[] res = new String[moves.size()]; for (int i = 0; i < res.length; i++) { res[i] = "" + moves.get(i).r + " " + moves.get(i).c + " " + moves.get(i).size + " " + moves.get(i).dir; } return res; } private int getTargetColumn(int number) { return number % N; } private int getTargetRow(int number) { return number / N; } private static int manhattanDistance2(int r, int c, int r2, int c2) { int absR = Math.abs(r - r2); int absC = Math.abs(c - c2); return Math.max(absR, absC) * (absR + absC); } private static int manhattanDistance(int r, int c, int r2, int c2) { int absR = Math.abs(r - r2); int absC = Math.abs(c - c2); return (absR + absC); } private ArrayList beamsearch4x4(int maxDepth, int maxWidth) { final int baseDepth = moveHistory.size(); HashSet usedHash = new HashSet (); ArrayList [] states = new ArrayList[1 << 5]; for (int i = 0; i < states.length; i++) { states[i] = new ArrayList (); } State best = null; { int gridPenalty = calculateGridPenalty(); int gridPenalty2 = calculateGridPenalty2(); State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2); states[0].add(e); usedHash.add(hash); best = e; } int sumWidth = 0; for (int depth = 0; depth < maxDepth; depth++) { if (states[0].size() == 0) { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); continue; } int beamWidth = Math.min(maxWidth, states[0].size()); CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2); for (int width = 0; width < beamWidth; width++) { State currentState = states[0].get(width); if (comparator.compare(currentState, best) < 0) { best = currentState; } if (Integer.bitCount(depth) == 1) { if (width == 0) { Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty); } } set(reverse2(toList(currentState)), baseDepth); for (int size = 2; size <= 3; size++) { for (int r = N - 4; r < N; r++) { for (int c = N - 4; c < N; c++) { if (!canRotate(r, c, size)) { continue; } int currentGridPenalty = calculateGridPenalty(r, c, size); int currentGridPenalty2 = calculateGridPenalty2(r, c, size); long currentHash = calculateHash(r, c, size); { int i = 1; long e = hash ^ currentHash ^ calculateHashR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyR(r, c, size); int gridPenalty2 = calculateGridPenalty2R(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } { int i = 3; long e = hash ^ currentHash ^ calculateHashRRR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyRRR(r, c, size); int gridPenalty2 = calculateGridPenalty2RRR(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } } } } } { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); } } for (; moveHistory.size() > baseDepth;) { previous(); } if (states[0].size() > 0) { Collections.sort(states[0]); if (comparator.compare(states[0].get(0), best) < 0) { best = states[0].get(0); } } return reverse2(toList(best)); } private ArrayList beamsearch(int maxDepth, int maxWidth) { final int baseDepth = moveHistory.size(); HashSet usedHash = new HashSet (); ArrayList [] states = new ArrayList[1 << 5]; for (int i = 0; i < states.length; i++) { states[i] = new ArrayList (); } State best = null; { int gridPenalty = calculateGridPenalty(); int gridPenalty2 = calculateGridPenalty2(); State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2); states[0].add(e); usedHash.add(hash); best = e; } int sumWidth = 0; for (int depth = 0; depth < maxDepth; depth++) { if (states[0].size() == 0) { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); continue; } if (depth % 4 == 0) { usedHash.clear(); } int beamWidth = Math.min(maxWidth, states[0].size()); CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2); for (int width = 0; width < beamWidth; width++) { State currentState = states[0].get(width); if (comparator.compare(currentState, best) < 0) { best = currentState; } if (Integer.bitCount(depth) == 1) { if (width == 0) { Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty); } } set(reverse2(toList(currentState)), baseDepth); for (int size = 2; size <= 3; size++) { for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (!canRotate(r, c, size)) { continue; } int currentGridPenalty = calculateGridPenalty(r, c, size); int currentGridPenalty2 = calculateGridPenalty2(r, c, size); long currentHash = calculateHash(r, c, size); { int i = 1; long e = hash ^ currentHash ^ calculateHashR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyR(r, c, size); int gridPenalty2 = calculateGridPenalty2R(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } { int i = 3; long e = hash ^ currentHash ^ calculateHashRRR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyRRR(r, c, size); int gridPenalty2 = calculateGridPenalty2RRR(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } } } } } { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); } } for (; moveHistory.size() > baseDepth;) { previous(); } if (states[0].size() > 0) { Collections.sort(states[0]); if (comparator.compare(states[0].get(0), best) < 0) { best = states[0].get(0); } } Utils.debug("mean width", sumWidth / (double) maxDepth); return reverse2(toList(best)); } private ArrayList beamsearch(int number, int maxDepth, int maxWidth) { final int baseDepth = moveHistory.size(); HashSet usedHash = new HashSet (); ArrayList [] states = new ArrayList[1 << 5]; for (int i = 0; i < states.length; i++) { states[i] = new ArrayList (); } State best = null; { int gridPenalty = calculateGridPenalty(); int gridPenalty2 = calculateGridPenalty2(); State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2); states[0].add(e); usedHash.add(hash); best = e; } for (int depth = 0; depth < maxDepth; depth++) { if (states[0].size() == 0) { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); continue; } int beamWidth = Math.min(maxWidth, states[0].size()); CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2); for (int width = 0; width < beamWidth; width++) { State currentState = states[0].get(width); if (comparator2.compare(currentState, best) < 0) { best = currentState; } set(reverse2(toList(currentState)), baseDepth); int targetR = numberToR[number]; int targetC = numberToC[number]; int margin = 1; for (int size = 2; size <= 3; size++) { int startR = Math.max(0, targetR - (size - 1) - margin); int endR = Math.min(N - 1, targetR + margin); int startC = Math.max(0, targetC - (size - 1) - margin); int endC = Math.min(N - 1, targetC + margin); for (int r = startR; r <= endR; r++) { for (int c = startC; c <= endC; c++) { if (!canRotate(r, c, size)) { continue; } int currentGridPenalty = calculateGridPenalty(r, c, size); int currentGridPenalty2 = calculateGridPenalty2(r, c, size); long currentHash = calculateHash(r, c, size); { int i = 1; long e = hash ^ currentHash ^ calculateHashR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyR(r, c, size); int gridPenalty2 = calculateGridPenalty2R(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } { int i = 3; long e = hash ^ currentHash ^ calculateHashRRR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyRRR(r, c, size); int gridPenalty2 = calculateGridPenalty2RRR(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } } } } } { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); } } for (; moveHistory.size() > baseDepth;) { previous(); } if (states[0].size() > 0) { Collections.sort(states[0]); if (comparator2.compare(states[0].get(0), best) < 0) { best = states[0].get(0); } } return reverse2(toList(best)); } private ArrayList beamsearchMargin2(int number, int maxDepth, int maxWidth) { final int baseDepth = moveHistory.size(); HashSet usedHash = new HashSet (); ArrayList [] states = new ArrayList[1 << 5]; for (int i = 0; i < states.length; i++) { states[i] = new ArrayList (); } State best = null; { int gridPenalty = calculateGridPenalty(); int gridPenalty2 = calculateGridPenalty2(); State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2); states[0].add(e); usedHash.add(hash); best = e; } for (int depth = 0; depth < maxDepth; depth++) { if (states[0].size() == 0) { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); continue; } int beamWidth = Math.min(maxWidth, states[0].size()); CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2); for (int width = 0; width < beamWidth; width++) { State currentState = states[0].get(width); if (comparator2.compare(currentState, best) < 0) { best = currentState; } set(reverse2(toList(currentState)), baseDepth); int targetR = numberToR[number]; int targetC = numberToC[number]; int margin = 2; for (int size = 2; size <= 3; size++) { int startR = Math.max(0, targetR - (size - 1) - margin); int endR = Math.min(N - 1, targetR + margin); int startC = Math.max(0, targetC - (size - 1) - margin); int endC = Math.min(N - 1, targetC + margin); for (int r = startR; r <= endR; r++) { for (int c = startC; c <= endC; c++) { if (!canRotate(r, c, size)) { continue; } int currentGridPenalty = calculateGridPenalty(r, c, size); int currentGridPenalty2 = calculateGridPenalty2(r, c, size); long currentHash = calculateHash(r, c, size); { int i = 1; long e = hash ^ currentHash ^ calculateHashR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyR(r, c, size); int gridPenalty2 = calculateGridPenalty2R(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } { int i = 3; long e = hash ^ currentHash ^ calculateHashRRR(r, c, size); if (usedHash.add(e)) { int gridPenalty = calculateGridPenaltyRRR(r, c, size); int gridPenalty2 = calculateGridPenalty2RRR(r, c, size); int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size]; states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2)); } } } } } } { ArrayList swap = states[0]; for (int i = 1; i < states.length; i++) { states[i - 1] = states[i]; } states[states.length - 1] = swap; states[states.length - 1].clear(); } } for (; moveHistory.size() > baseDepth;) { previous(); } if (states[0].size() > 0) { Collections.sort(states[0]); if (comparator2.compare(states[0].get(0), best) < 0) { best = states[0].get(0); } } return reverse2(toList(best)); } private long calculateHashR(int r0, int c0, int size0) { long hash = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - c][c0 + 0 + r]; hash ^= hashes[r0 + r][c0 + c][number]; } } return hash; } private long calculateHashRR(int r0, int c0, int size0) { long hash = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + m - r][c0 + m - c]; hash ^= hashes[r0 + r][c0 + c][number]; } } return hash; } private long calculateHashRRR(int r0, int c0, int size0) { long hash = 0; for (int r = 0, m = size0 - 1; r < size0; r++) { for (int c = 0; c < size0; c++) { int number = rxcToNumber[r0 + 0 + c][c0 + m - r]; hash ^= hashes[r0 + r][c0 + c][number]; } } return hash; } private long calculateHash(int r0, int c0, int size0) { long hash = 0; for (int r = r0; r < r0 + size0; r++) { for (int c = c0; c < c0 + size0; c++) { int number = rxcToNumber[r][c]; hash ^= hashes[r][c][number]; } } return hash; } private void updateNumberToRxc(int r0, int c0, int size0) { for (int r = r0; r < r0 + size0; r++) { for (int c = c0; c < c0 + size0; c++) { numberToR[rxcToNumber[r][c]] = r; numberToC[rxcToNumber[r][c]] = c; } } } public void set(ArrayList list, int startIndex) { int startIndexMinus1 = startIndex - 1; for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) { if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) { break; } startIndexMinus1 = startIndex + i; } for (; moveHistory.size() > startIndexMinus1 + 1;) { previous(); } for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) { State state2 = list.get(i); next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations); } } private boolean isSameMove(Move move, State state) { if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) { return false; } return true; } public void set2(ArrayList list, int startIndex) { int startIndexMinus1 = startIndex - 1; for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) { if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) { break; } startIndexMinus1 = startIndex + i; } for (; moveHistory.size() > startIndexMinus1 + 1;) { previous(); } for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) { State2 state2 = list.get(i); next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations); } } private boolean isSameMove(Move move, State2 state) { if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) { return false; } return true; } private ArrayList moveHistory = new ArrayList<>(); public void next(int r, int c, int size, char dir, int numRotations) { moveHistory.add(new Move(r, c, size, dir, numRotations)); for (int i = 0; i < numRotations; i++) { rotate(r, c, size, dir); } } public void previous() { Move lastMove = moveHistory.remove(moveHistory.size() - 1); int r = lastMove.r; int c = lastMove.c; int size = lastMove.size; char dir = lastMove.dir == 'L' ? 'R' : 'L'; for (int i = 0; i < lastMove.numRotations; i++) { rotate(r, c, size, dir); } } private ArrayList reverse2(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 state0) { ArrayList res = new ArrayList<>(); for (State current = state0; current.parent != null; current = current.parent) { res.add(current); } return res; } private ArrayList toList(State2 state0) { ArrayList res = new ArrayList<>(); for (State2 current = state0; current.parent != null; current = current.parent) { res.add(current); } return res; } } class State implements Comparable { State parent; int r; int c; int size; char dir; int numRotations; int gridPenalty; int gridPenalty2; int sumRotatePenalty; public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty) { super(); this.parent = parent; this.r = r; this.c = c; this.size = size; this.dir = dir; this.numRotations = numRotations; this.gridPenalty = gridPenalty; this.sumRotatePenalty = sumRotatePenalty; } public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2) { super(); this.parent = parent; this.r = r; this.c = c; this.size = size; this.dir = dir; this.numRotations = numRotations; this.gridPenalty = gridPenalty; this.gridPenalty2 = gridPenalty2; this.sumRotatePenalty = sumRotatePenalty; } @Override public int compareTo(State o) { if (gridPenalty < o.gridPenalty) { return -1; } if (gridPenalty > o.gridPenalty) { return 1; } return 0; } } class State2 { State2 parent; int r; int c; int size; char dir; int numRotations; int gridPenalty; int gridPenalty2; int sumRotatePenalty; int distance; int c2; public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int r2, int c2) { super(); this.parent = parent; this.r = r; this.c = c; this.size = size; this.dir = dir; this.numRotations = numRotations; this.gridPenalty = gridPenalty; this.sumRotatePenalty = sumRotatePenalty; this.distance = r2; this.c2 = c2; } public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2, int r2, int c2) { super(); this.parent = parent; this.r = r; this.c = c; this.size = size; this.dir = dir; this.numRotations = numRotations; this.gridPenalty = gridPenalty; this.gridPenalty2 = gridPenalty2; this.sumRotatePenalty = sumRotatePenalty; this.distance = r2; this.c2 = c2; } } class Move { int r; int c; int size; char dir; int numRotations; public Move(int r, int c, int size, char dir, int numRotations) { super(); this.r = r; this.c = c; this.size = size; this.dir = dir; this.numRotations = numRotations; } } public class RotatingNumbers { public String[] findSolution(int N, int P, int[][] grid) { Solver solver = new Solver(N, P, grid); solver.solve(); return solver.makeSolution(); } public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int N = Integer.parseInt(br.readLine()); int P = Integer.parseInt(br.readLine()); int[][] grid = new int[N][N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { grid[r][c] = Integer.parseInt(br.readLine()); } } RotatingNumbers prog = new RotatingNumbers(); String[] ret = prog.findSolution(N, P, grid); System.out.println(ret.length); for (int i = 0; i < ret.length; i++) { System.out.println(ret[i]); } System.out.flush(); } catch (Exception e) { e.printStackTrace(); } } } class 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; } } 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()); } }
コメント