結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2026-05-17 10:44:13 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 1,917 ms / 2,000 ms |
| コード長 | 27,144 bytes |
| 記録 | |
| コンパイル時間 | 6,048 ms |
| コンパイル使用メモリ | 102,536 KB |
| 実行使用メモリ | 63,588 KB |
| スコア | 2,258,521 |
| 最終ジャッジ日時 | 2026-05-17 10:45:58 |
| 合計ジャッジ時間 | 104,317 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
private static final double timeLimitSecond = 1.8;
private static final int[] dr = { -1, 0, 0, 1, };
private static final int[] dc = { 0, -1, 1, 0, };
private static int N;
private static int T;
private static int[][] A;
private static PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());
private static Watch2 watch;
private static Path solution;
private static Path bestSolution;
private static Params params;
private static Point[][] P;
public static void main(String[] args) {
Utils.debug("args", args);
try {
read();
init();
solve();
write();
Utils.debug("score", bestScore, "time", watch.toString());
} catch (Exception e) {
e.printStackTrace();
}
}
private static void read() {
try (Scanner in = new Scanner(System.in)) {
N = in.nextInt();
watch = new Watch2();
T = in.nextInt();
System.err.println("[DATA] N = " + N);
System.err.println("[DATA] T = " + T);
System.err.flush();
A = new int[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
A[r][c] = in.nextInt();
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
private static void init() {
params = Params.fromProps();
P = new Point[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
P[r][c] = new Point(r, c);
}
}
solution = new Path(new ArrayList<>(), new boolean[N][N], 0);
bestScore = 0;
bestSolution = new Path(new ArrayList<>(), new boolean[N][N], 0);
}
private static void write() {
StringBuilder sb = new StringBuilder();
sb.append(bestSolution.size()).append("\n");
for (int i = 0; i < bestSolution.size(); i++) {
Point p = bestSolution.get(i);
sb.append(p.r).append(" ").append(p.c).append("\n");
}
System.out.println(sb.toString().trim());
System.out.flush();
}
private static void solve() {
greedy();
multiSA();
}
private static void greedy() {
ArrayList<Point> current = new ArrayList<>();
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
solution.clear();
Point p = P[r][c];
current.clear();
current.add(p);
ArrayList<Point> newPath = solution.dfs(Math.min(T, params.depth), p, null, current);
if (newPath.isEmpty()) {
continue;
}
for (int i = 0; i < newPath.size(); i++) {
solution.add(newPath.get(i));
}
newPath.clear();
score = solution.score();
saveBest();
}
}
loadBest();
Utils.debug("greedy", "score", score, "time", watch.elapsedSecond());
}
private static double temperature;
private static double score;
private static double bestScore;
private static int[] countAC = new int[30];
private static long iterations = 0;
private static long validIterations = 0;
private static long acIterations = 0;
private static void multiSA() {
int numRestart = params.numRestart;
double startTime = watch.elapsedSecond();
double endTime = timeLimitSecond;
double remainTime = endTime - startTime;
double startStartTemperature = params.startTemp;
double endStartTemperature = params.endTemp;
for (double restart = 0; restart < numRestart; restart++) {
double startTime2 = startTime + remainTime * restart / numRestart;
double endTime2 = startTime + remainTime * (restart + 1) / numRestart;
double startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);
double endTemperature = params.endTemp;
SA(startTime2, endTime2, startTemperature, endTemperature);
loadBest();
}
Utils.debug("multiSA", "score", score, "time", watch.elapsedSecond());
}
private static void SA(double startTime, double endTime, double startTemperature, double endTemperature) {
temperature = startTemperature;
while (true) {
iterations++;
if ((iterations & ((1 << 5) - 1)) == 0) {
final double timeRatio01 = (watch.elapsedSecond() - startTime) / (endTime - startTime);
temperature = startTemperature + (endTemperature - startTemperature) * timeRatio01;
if (timeRatio01 >= 1.0) {
Utils.debug("iters", iterations, "valid", String.format("%.2f%%", validIterations * 100.0 / iterations), "ac", String.format("%.2f%%", acIterations * 100.0 / iterations), "score", score, "best", bestScore, "T", String.format("%.3f", temperature), "time", String.format("%.2f", watch.elapsedSecond()), "st", startTime, "et", endTime, "sTemp", startTemperature, "eTemp", endTemperature, "countAC", countAC);
break;
}
}
if (solution.size() == 0) {
loadBest();
}
mutate();
}
}
private static void mutate() {
double random = (params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3) * rng.nextDouble();
if (random < params.mutate0) {
removeAndAdd();
} else if (random < params.mutate0 + params.mutate1) {
trim();
} else if (random < params.mutate0 + params.mutate1 + params.mutate2) {
removeAndAddFirst();
} else if (random < params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3) {
move1();
}
}
private static ArrayList<Point> removes = new ArrayList<>();
private static final int[] indexes = new int[] { 0, 1, 2, 3, };
private static void move1() {
final boolean reverse = rng.nextInt(2) == 0;
if (reverse) {
final Point tail = solution.get(0);
int d = -1;
for (int d2 = 0; d2 < dr.length; d2++) {
int d3 = d2 + rng.nextInt(dr.length - d2);
swap(indexes, d2, d3);
int nr = tail.r + dr[indexes[d2]];
int nc = tail.c + dc[indexes[d2]];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (solution.used[nr][nc]) {
int index = solution.points.indexOf(P[nr][nc]);
if (index - 1 == 0) {
continue;
}
for (int l = 0, r = index - 1; l < r; l++, r--) {
Collections.swap(solution.points, l, r);
}
return;
}
d = d2;
break;
}
int nr = tail.r + dr[indexes[d]];
int nc = tail.c + dc[indexes[d]];
double deltaScore = A[nr][nc];
if (solution.size() == T) {
final Point head = solution.get(solution.size() - 1);
deltaScore -= A[head.r][head.c];
}
if (accept(deltaScore)) {
score += deltaScore;
if (solution.size() == T) {
solution.remove(solution.size() - 1);
}
solution.reverse();
solution.add(P[nr][nc]);
saveBest();
}
} else {
final Point tail = solution.get(solution.size() - 1);
int d = -1;
for (int d2 = 0; d2 < dr.length; d2++) {
int d3 = d2 + rng.nextInt(dr.length - d2);
swap(indexes, d2, d3);
int nr = tail.r + dr[indexes[d2]];
int nc = tail.c + dc[indexes[d2]];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (solution.used[nr][nc]) {
int index = solution.points.lastIndexOf(P[nr][nc]);
if (index + 1 == solution.size() - 1) {
continue;
}
for (int l = index + 1, r = solution.size() - 1; l < r; l++, r--) {
Collections.swap(solution.points, l, r);
}
return;
}
d = d2;
break;
}
int nr = tail.r + dr[indexes[d]];
int nc = tail.c + dc[indexes[d]];
double deltaScore = A[nr][nc];
if (solution.size() == T) {
Point head = solution.get(0);
deltaScore -= A[head.r][head.c];
}
if (accept(deltaScore)) {
score += deltaScore;
if (solution.size() == T) {
solution.remove(0);
}
solution.add(P[nr][nc]);
saveBest();
}
}
}
private static void trim() {
final int threshold = params.initA + rng.nextInt(params.randomA);
for (int i = solution.size() - 1; i >= 0; i--) {
Point p = solution.get(i);
if (A[p.r][p.c] >= threshold) {
break;
}
solution.remove(i);
removes.add(p);
}
int size = removes.size();
solution.reverse();
for (int i = solution.size() - 1; i >= 0; i--) {
Point p = solution.get(i);
if (A[p.r][p.c] >= threshold) {
break;
}
solution.remove(i);
removes.add(p);
}
double deltaScore = solution.score() - score;
if (accept(deltaScore)) {
score += deltaScore;
saveBest();
removes.clear();
} else {
while (removes.size() > size) {
Point p = removes.remove(removes.size() - 1);
solution.add(p);
}
solution.reverse();
while (removes.size() > 0) {
Point p = removes.remove(removes.size() - 1);
solution.add(p);
}
}
}
private static void removeAndAdd() {
if (solution.size() == 0) {
return;
}
final int index = rng.nextInt(Math.max(1, solution.size() - params.initSize - rng.nextInt(params.randomSize)));
final int length = params.initLength + rng.nextInt(params.randomLength);
if (index + length >= solution.size()) {
solution.reverse();
}
Point last = null;
for (int i = 0; i < length; i++) {
if (index >= solution.size()) {
last = null;
break;
}
Point p = solution.remove(index);
removes.add(p);
last = p;
}
final int length2 = Math.min(T - solution.size(), length + rng.nextInt(params.randomLength2));
ArrayList<Point> newPath = solution.dfs(length2, removes.get(0), last, removes);
if (newPath.isEmpty()) {
assert newPath.size() == 0;
for (int i = removes.size() - 1; i >= 0; i--) {
Point p = removes.remove(i);
solution.add(index, p);
}
return;
}
for (int i = 0; i < newPath.size(); i++) {
Point p = newPath.get(i);
solution.add(index + i, p);
}
double deltaScore = solution.score() - score;
if (accept(deltaScore)) {
score += deltaScore;
saveBest();
removes.clear();
newPath.clear();
} else {
for (int i = newPath.size() - 1; i >= 0; i--) {
newPath.remove(i);
solution.remove(index);
}
for (int i = removes.size() - 1; i >= 0; i--) {
Point p = removes.remove(i);
solution.add(index, p);
}
}
}
private static void removeAndAddFirst() {
if (solution.size() == 0) {
return;
}
final int index = rng.nextInt(Math.max(1, solution.size() - params.initSize - rng.nextInt(params.randomSize)));
final int length = params.initLength + rng.nextInt(params.randomLength);
if (index + length >= solution.size()) {
solution.reverse();
}
Point last = null;
for (int i = 0; i < length; i++) {
if (index >= solution.size()) {
last = null;
break;
}
Point p = solution.remove(index);
removes.add(p);
last = p;
}
final int length2 = Math.min(T - solution.size(), length + rng.nextInt(params.randomLength2));
ArrayList<Point> newPath = solution.dfsFirst(length2, removes.get(0), last, removes);
if (newPath.isEmpty()) {
assert newPath.size() == 0;
for (int i = removes.size() - 1; i >= 0; i--) {
Point p = removes.remove(i);
solution.add(index, p);
}
return;
}
for (int i = 0; i < newPath.size(); i++) {
Point p = newPath.get(i);
solution.add(index + i, p);
}
double deltaScore = solution.score() - score;
if (accept(deltaScore)) {
score += deltaScore;
saveBest();
removes.clear();
newPath.clear();
} else {
for (int i = newPath.size() - 1; i >= 0; i--) {
newPath.remove(i);
solution.remove(index);
}
for (int i = removes.size() - 1; i >= 0; i--) {
Point p = removes.remove(i);
solution.add(index, p);
}
}
}
private static void saveBest() {
if (score > bestScore) {
bestScore = score;
bestSolution.clear();
bestSolution.addAll(solution);
}
}
private static void loadBest() {
score = bestScore;
solution.clear();
solution.addAll(bestSolution);
}
private static boolean accept(double delta) {
validIterations++;
if (delta >= 0) {
acIterations++;
return true;
}
double deltaPerTemperature = delta / temperature;
if (deltaPerTemperature < -10.0) {
return false;
}
boolean ac = rng.nextDouble() < Math.exp(deltaPerTemperature);
if (ac) {
acIterations++;
}
return ac;
}
static class Params {
double mutate0 = 1.0;
double mutate1 = 0.14643137864681252;
double mutate2 = 0.04845559300914911;
double mutate3 = 92.9093898531278;
double startTemp = 301.2062111018557;
double endTemp = 0.012970778719855585;
int depth = 7;
int numRestart = 37;
int initA = 113;
int randomA = 242;
int initSize = 2;
int randomSize = 5;
int initLength = 4;
int randomLength = 6;
int randomLength2 = 5;
static Params fromProps() {
Params p = new Params();
p.mutate0 = getD("mutate0", p.mutate0);
p.mutate1 = getD("mutate1", p.mutate1);
p.mutate2 = getD("mutate2", p.mutate2);
p.mutate3 = getD("mutate3", p.mutate3);
p.startTemp = getD("startTemp", p.startTemp);
p.endTemp = getD("endTemp", p.endTemp);
p.depth = getI("depth", p.depth);
p.numRestart = getI("numRestart", p.numRestart);
p.initA = getI("initA", p.initA);
p.randomA = getI("randomA", p.randomA);
p.initSize = getI("initSize", p.initSize);
p.randomSize = getI("randomSize", p.randomSize);
p.initLength = getI("initLength", p.initLength);
p.randomLength = getI("randomLength", p.randomLength);
p.randomLength2 = getI("randomLength2", p.randomLength2);
return p;
}
static double getD(String k, double def) {
String s = System.getProperty(k);
if (s == null)
return def;
try {
return Double.parseDouble(s);
} catch (Exception e) {
return def;
}
}
static int getI(String k, int def) {
String s = System.getProperty(k);
if (s == null)
return def;
try {
return Integer.parseInt(s);
} catch (Exception e) {
return def;
}
}
}
static class Point {
int r;
int c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
public boolean equals(Point other) {
if (other == null)
return false;
return c == other.c && r == other.r;
}
@Override
public String toString() {
return "(" + r + "," + c + ")";
}
}
static class Path {
ArrayList<Point> points;
boolean[][] used;
int score;
public Path(ArrayList<Point> points, boolean[][] used, int score) {
this.points = points;
this.used = used;
this.score = score;
}
public void reverse() {
Collections.reverse(points);
}
public double score() {
return score;
}
public Point get(int i) {
return points.get(i);
}
public int size() {
return points.size();
}
public void add(int index, Point p) {
points.add(index, p);
assert !used[p.r][p.c];
used[p.r][p.c] = true;
score += A[p.r][p.c];
}
public void add(Point p) {
add(points.size(), p);
}
public Point remove(int index) {
Point p = points.remove(index);
assert used[p.r][p.c];
used[p.r][p.c] = false;
score -= A[p.r][p.c];
return p;
}
public void clear() {
for (int i = size() - 1; i >= 0; i--) {
remove(i);
}
}
public void addAll(Path other) {
for (int i = 0; i < other.size(); i++) {
add(other.get(i));
}
}
private int bestScoreDfs;
private ArrayList<Point> bestScoreDfsSolution = new ArrayList<>();
private ArrayList<Point> temp = new ArrayList<>();
private ArrayList<Point> dfs(int length, Point start, Point end, ArrayList<Point> current) {
bestScoreDfs = 0;
assert bestScoreDfsSolution.isEmpty() : Utils.toString("bestScoreDfsSolution", bestScoreDfsSolution);
assert temp.isEmpty() : Utils.toString("temp", temp);
temp.add(start);
assert !used[start.r][start.c];
used[start.r][start.c] = true;
dfs(temp, 0, length, end, 0, current);
temp.remove(temp.size() - 1);
assert temp.isEmpty() : Utils.toString("temp", temp);
assert used[start.r][start.c];
used[start.r][start.c] = false;
return bestScoreDfsSolution;
}
private void dfs(ArrayList<Point> temp, int i, int length, Point end, int scoreDfs, ArrayList<Point> current) {
if (i >= length) {
return;
}
Point last = temp.get(temp.size() - 1);
if (end != null) {
if (i + Math.abs(last.r - end.r) + Math.abs(last.c - end.c) >= length) {
return;
}
}
if (end == null || last.equals(end)) {
if (!equals(temp, current)) {
if (scoreDfs > bestScoreDfs) {
bestScoreDfs = scoreDfs;
bestScoreDfsSolution.clear();
for (int j = 0; j < temp.size(); j++) {
bestScoreDfsSolution.add(temp.get(j));
}
}
}
if (last.equals(end)) {
return;
}
}
for (int d = 0; d < dr.length; d++) {
int nr = temp.get(i).r + dr[d];
int nc = temp.get(i).c + dc[d];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (used[nr][nc]) {
continue;
}
used[nr][nc] = true;
temp.add(P[nr][nc]);
dfs(temp, i + 1, length, end, scoreDfs + A[nr][nc], current);
used[nr][nc] = false;
temp.remove(temp.size() - 1);
}
}
private ArrayList<Point> dfsFirst(int length, Point start, Point end, ArrayList<Point> current) {
bestScoreDfs = 0;
assert bestScoreDfsSolution.isEmpty() : Utils.toString("bestScoreDfsSolution", bestScoreDfsSolution);
assert temp.isEmpty() : Utils.toString("temp", temp);
temp.add(start);
assert !used[start.r][start.c];
used[start.r][start.c] = true;
dfsFirst(temp, 0, length, end, 0, current);
temp.remove(temp.size() - 1);
assert temp.isEmpty() : Utils.toString("temp", temp);
assert used[start.r][start.c];
used[start.r][start.c] = false;
return bestScoreDfsSolution;
}
private void dfsFirst(ArrayList<Point> temp, int i, int length, Point end, int scoreDfs, ArrayList<Point> current) {
if (bestScoreDfs != 0) {
return;
}
if (i >= length) {
return;
}
Point last = temp.get(temp.size() - 1);
if (end != null) {
if (i + Math.abs(last.r - end.r) + Math.abs(last.c - end.c) >= length) {
return;
}
}
if (end == null || last.equals(end)) {
if (!equals(temp, current)) {
if (scoreDfs > bestScoreDfs) {
bestScoreDfs = scoreDfs;
bestScoreDfsSolution.clear();
for (int j = 0; j < temp.size(); j++) {
bestScoreDfsSolution.add(temp.get(j));
}
}
}
if (last.equals(end)) {
return;
}
}
int[] index = new int[] { 0, 1, 2, 3, };
shuffle(index);
for (int d = 0; d < dr.length; d++) {
int nr = temp.get(i).r + dr[index[d]];
int nc = temp.get(i).c + dc[index[d]];
if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
continue;
}
if (used[nr][nc]) {
continue;
}
used[nr][nc] = true;
temp.add(P[nr][nc]);
dfsFirst(temp, i + 1, length, end, scoreDfs + A[nr][nc], current);
used[nr][nc] = false;
temp.remove(temp.size() - 1);
}
}
private static boolean equals(ArrayList<Point> l, ArrayList<Point> l2) {
if (l.size() != l2.size()) {
return false;
}
for (int i = 0; i < l.size(); i++) {
if (!l.get(i).equals(l2.get(i))) {
return false;
}
}
return true;
}
}
private static final void shuffle(int[] a) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
swap(a, i, j);
}
}
private static final void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
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;
}
}
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();
}
}