結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2025-07-26 16:51:00 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,918 ms / 2,000 ms |
| コード長 | 16,352 bytes |
| コンパイル時間 | 3,163 ms |
| コンパイル使用メモリ | 104,888 KB |
| 実行使用メモリ | 65,116 KB |
| スコア | 4,844,436,367 |
| 最終ジャッジ日時 | 2025-07-26 16:52:54 |
| 合計ジャッジ時間 | 101,385 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
enum Move {
U, D, L, R, W, C,;
}
private static Watch2 watch;
private static final PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());
public static void main(final String[] args) {
try (final Scanner sc = new Scanner(System.in)) {
final int N = sc.nextInt();
watch = new Watch2();
final int T = sc.nextInt();
final int[][] A = new int[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
A[r][c] = sc.nextInt();
}
}
final int[][] copyA = new int[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
ArrayList<Move> solution = greedy(N, T, copyA);
{
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
int score = calculateScore(N, T, copyA, 0, 0, 0, solution);
Utils.debug("score", score);
}
sa(N, T, A, copyA, solution);
{
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
int score = calculateScore(N, T, copyA, 0, 0, 0, solution);
Utils.debug("score", score);
}
System.out.println(solution.stream().map(move -> move.name())
.reduce("", (sum, move) -> sum + move + "\n"));
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
private static ArrayList<Move> greedy(final int N, final int T, int[][] A)
throws AssertionError {
ArrayList<Move> solution = new ArrayList<>();
{
int r0 = 0;
int c0 = 0;
int v = 0;
for (int shift = 19; shift >= 0; shift--) {
final int mask = 1 << shift;
if (solution.size() >= T) {
break;
}
int bestR = -1;
int bestC = -1;
int bestR2 = -1;
int bestC2 = -1;
int bestR3 = -1;
int bestC3 = -1;
int bestR4 = -1;
int bestC4 = -1;
int bestDistance = (int) 1e9;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (((v ^ A[r][c]) & mask) != 0) {
int distance = distance(r, c, r0, c0);
if (distance < bestDistance) {
bestR = r;
bestC = c;
bestR2 = -1;
bestC2 = -1;
bestR3 = -1;
bestC3 = -1;
bestR4 = -1;
bestC4 = -1;
bestDistance = distance;
}
}
for (int r2 = 0; r2 < N; r2++) {
for (int c2 = 0; c2 < N; c2++) {
if (((v ^ A[r][c] ^ A[r2][c2]) & mask) != 0) {
int distance = distance(r, c, r0, c0)
+ distance(r, c, r2, c2);
if (distance < bestDistance) {
bestR = r;
bestC = c;
bestR2 = r2;
bestC2 = c2;
bestR3 = -1;
bestC3 = -1;
bestR4 = -1;
bestC4 = -1;
bestDistance = distance;
}
}
for (int r3 = 0; r3 < N; r3++) {
for (int c3 = 0; c3 < N; c3++) {
if (((v ^ A[r][c] ^ A[r2][c2]
^ A[r3][c3]) & mask) != 0) {
int distance = distance(r, c, r0,
c0) + distance(r, c, r2, c2)
+ distance(r2, c2, r3, c3);
if (distance < bestDistance) {
bestR = r;
bestC = c;
bestR2 = r2;
bestC2 = c2;
bestR3 = r3;
bestC3 = c3;
bestR4 = -1;
bestC4 = -1;
bestDistance = distance;
}
}
}
}
}
}
}
}
if (bestR < 0) {
break;
}
move(r0, c0, bestR, bestC, solution);
r0 = bestR;
c0 = bestC;
if (bestR2 >= 0) {
move(r0, c0, bestR2, bestC2, solution);
r0 = bestR2;
c0 = bestC2;
if (bestR3 >= 0) {
move(r0, c0, bestR3, bestC3, solution);
r0 = bestR3;
c0 = bestC3;
if (bestR4 >= 0) {
move(r0, c0, bestR4, bestC4, solution);
r0 = bestR4;
c0 = bestC4;
}
}
}
v = copy(r0, c0, v, A, solution);
move(r0, c0, 0, 0, solution);
r0 = 0;
c0 = 0;
for (int r = 0; r < N; r++) {
if (r % 2 == 0) {
for (int c = 0; c < N; c++) {
if ((A[r][c] & mask) == 0) {
move(r0, c0, r, c, solution);
r0 = r;
c0 = c;
write(r, c, v, A, solution);
}
}
} else {
for (int c = N - 1; c >= 0; c--) {
if ((A[r][c] & mask) == 0) {
move(r0, c0, r, c, solution);
r0 = r;
c0 = c;
write(r, c, v, A, solution);
}
}
}
}
}
}
while (solution.size() > T) {
solution.remove(solution.size() - 1);
}
return solution;
}
private static void write(int r, int c, int v, int[][] A,
ArrayList<Move> solution) {
solution.add(Move.W);
A[r][c] = v ^ A[r][c];
}
private static int copy(int r, int c, int v, int[][] A,
ArrayList<Move> solution) {
solution.add(Move.C);
return v ^ A[r][c];
}
private static void move(int r0, int c0, int r, int c,
ArrayList<Move> solution) {
while (r0 < r) {
r0++;
solution.add(Move.D);
}
while (r0 > r) {
r0--;
solution.add(Move.U);
}
while (c0 < c) {
c0++;
solution.add(Move.R);
}
while (c0 > c) {
c0--;
solution.add(Move.L);
}
}
private static int distance(int r, int c, int r0, int c0) {
return Math.abs(r - r0) + Math.abs(c - c0);
}
private static void sa(int N, int T, int[][] A, int[][] copyA,
ArrayList<Move> solution) {
final double startTemperature = 1e4;
final double endTemperature = 1e1;
double temperature = startTemperature;
final double startTime = watch.elapsedSecond();
final double endTime = 1.75;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
int score = calculateScore(N, T, copyA, 0, 0, 0, solution);
final int mask = (1 << 7) - 1;
for (int iteration = 0;; iteration++) {
if ((iteration & mask) == mask) {
final double time = watch.elapsedSecond();
if (time > endTime) {
System.err.println(
"Iteration: " + iteration + ", Temperature: "
+ temperature + ", score: " + score);
break;
}
temperature = startTemperature
+ (endTemperature - startTemperature)
* ((time - startTime) / (endTime - startTime));
System.err.println("Iteration: " + iteration + ", Temperature: "
+ temperature + ", score: " + score);
}
final double random = 2 * rng.nextDouble();
if (random < 1) {
final int i = rng.nextInt(solution.size());
int j = rng.nextInt(solution.size() - 1);
if (j >= i) {
j++;
}
if (i < j) {
for (int k = i; k < j; k++) {
solution.set(k, solution.set(k + 1, solution.get(k)));
}
} else {
for (int k = i; k > j; k--) {
solution.set(k, solution.set(k - 1, solution.get(k)));
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
int deltaScore = calculateScore(N, T, copyA, 0, 0, 0, solution)
- score;
if (accept(temperature, deltaScore)) {
score += deltaScore;
} else {
if (i < j) {
for (int k = j; k > i; k--) {
solution.set(k,
solution.set(k - 1, solution.get(k)));
}
} else {
for (int k = j; k < i; k++) {
solution.set(k,
solution.set(k + 1, solution.get(k)));
}
}
}
} else if (random < 2) {
int i = rng.nextInt(solution.size());
Move current = solution.get(i);
solution.set(i,
Move.values()[rng.nextInt(Move.values().length)]);
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
copyA[r][c] = A[r][c];
}
}
int deltaScore = calculateScore(N, T, copyA, 0, 0, 0, solution)
- score;
if (accept(temperature, deltaScore)) {
score += deltaScore;
} else {
solution.set(i, current);
}
}
}
}
private static boolean accept(double temperature, int deltaScore) {
return deltaScore >= 0
|| rng.nextDouble() < Math.exp(deltaScore / temperature);
}
private static int calculateScore(int N, int T, int[][] A, int r, int c,
int v, ArrayList<Move> solution) {
for (Move op : solution) {
switch (op) {
case U: {
r--;
if (r < 0) {
return (int) -1e9;
}
break;
}
case D: {
r++;
if (r >= N) {
return (int) -1e9;
}
break;
}
case L: {
c--;
if (c < 0) {
return (int) -1e9;
}
break;
}
case R: {
c++;
if (c >= N) {
return (int) -1e9;
}
break;
}
case W: {
A[r][c] ^= v;
break;
}
case C: {
v ^= A[r][c];
break;
}
default:
return (int) -1e9;
}
}
return calculateScore(N, A);
}
private static int calculateScore(int N, int[][] A) {
int score = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
score += A[r][c];
}
}
return score;
}
}
class PCG_XSH_RR {
private long state = 5342;
public PCG_XSH_RR(final long state) {
this.state = state;
}
public int nextInt() {
final long oldstate = state;
state = oldstate * 6364136223846793005L + 521L;
final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);
final int rotation = (int) (oldstate >>> 59);
return (xorshift >>> rotation) | (xorshift << (-rotation & 31));
}
public int nextInt(int n) {
return (int) (n * nextDouble());
}
public int nextInt2(int n) {
final int k = 16;
final int x = (nextInt() & ((1 << k) - 1));
return (x * n) >>> k;
}
public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}
}
class Watch2 {
private final long start;
public Watch2() {
start = System.nanoTime();
}
public double elapsedSecond() {
return (System.nanoTime() - start) * 1e-9;
}
@Override
public String toString() {
final long elapsedSecond = (long) (1e3 * elapsedSecond());
return formatElapsedTimeWithUnits(elapsedSecond);
}
public static String formatElapsedTimeWithUnits(final long elapsedMillis) {
final Duration duration = Duration.ofMillis(elapsedMillis);
final long hours = duration.toHours();
final long minutes = duration.toMinutesPart();
final long seconds = duration.toSecondsPart();
final long millis = duration.toMillisPart();
final StringBuilder sb = new StringBuilder();
if (hours > 0) {
sb.append(hours).append("h");
}
if (minutes > 0 || hours > 0) {
sb.append(minutes).append("m");
}
sb.append(seconds);
if (minutes > 0 || hours > 0) {
} else {
sb.append(".").append(String.format("%03d", millis));
}
sb.append("s");
return sb.toString().trim();
}
}
class Utils {
private Utils() {
}
public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}
public static final String toString(Object... o) {
return Arrays.deepToString(o);
}
public static boolean isValid(int v, int min, int minUpper) {
return v >= min && v < minUpper;
}
}