結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2025-07-26 14:27:01 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 710 ms / 2,000 ms |
| コード長 | 9,042 bytes |
| コンパイル時間 | 3,361 ms |
| コンパイル使用メモリ | 298,928 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,005,388,552 |
| 最終ジャッジ日時 | 2025-07-26 14:27:42 |
| 合計ジャッジ時間 | 38,278 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// greedy_xor_v7.cpp
// ------------------------------------------------------------------
// • N = 10, T = 1000 固定
// • a 候補: 値が小さい上位 K = 5 マス
// • Copy を “1 回 / 2 回 / 3 回” まで同時に評価し，gain / cost 最大を採用
// • 1 改善あたりの手数上限を
// ─ 1‑copy / 2‑copy: MAX_COST12 = 30
// ─ 3‑copy : MAX_COST3 = 45
// • 操作列は stdout，詳細ログは stderr
// ------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_COST12 = 30; // 1・2‑copy 用手数上限
constexpr int MAX_COST3 = 45; // 3‑copy 用手数上限
constexpr int K = 1; // a 候補数
// ───────────────────────── helpers ──────────────────────────
inline int manh(int r1, int c1, int r2, int c2) {
return abs(r1 - r2) + abs(c1 - c2);
}
void addMoves(int r1, int c1, int r2, int c2, vector<char>& ops) {
if (r2 > r1) ops.insert(ops.end(), r2 - r1, 'D');
else ops.insert(ops.end(), r1 - r2, 'U');
if (c2 > c1) ops.insert(ops.end(), c2 - c1, 'R');
else ops.insert(ops.end(), c1 - c2, 'L');
}
struct BestPlan {
double ratio = -1.0;
int gain = 0, cost = 0;
char type = 0; // '1','2','3'
int ar = 0, ac = 0; // target cell
int b1r = 0, b1c = 0, b2r = 0, b2c = 0, b3r = 0, b3c = 0;
};
// ─────────────────────────── main ───────────────────────────
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T;
if (!(cin >> N >> T)) return 0;
vector<vector<int>> A(N, vector<int>(N));
for (auto& row : A) for (int& x : row) cin >> x;
// 全セル座標
vector<pair<int,int>> cells;
cells.reserve(N * N);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cells.emplace_back(i, j);
int r = 0, c = 0; // 現在位置
int s = 0; // レジスタ
vector<char> ops; // 操作列
int step = 1;
while (true) {
// ---------- a 候補: 値が小さい上位 K ----------
vector<pair<int,int>> a_cands = cells;
partial_sort(a_cands.begin(), a_cands.begin() + K, a_cands.end(),
[&](auto p1, auto p2) {
return A[p1.first][p1.second] < A[p2.first][p2.second];
});
a_cands.resize(K);
BestPlan best;
// ---------- 各 a について探索 ----------
for (auto [ar, ac] : a_cands) {
int a_val = A[ar][ac];
// ---- 1‑copy ---------------------------------------------------
for (auto [br, bc] : cells) {
if (br == ar && bc == ac) continue;
int cost = manh(r,c, br,bc)+1 + manh(br,bc, ar,ac)+1;
if (cost > MAX_COST12 || (int)ops.size() + cost > T) continue;
int gain = (a_val ^ (s ^ A[br][bc])) - a_val;
if (gain <= 0) continue;
double ratio = (double)gain / cost;
if (ratio > best.ratio) {
best = {ratio, gain, cost, '1', ar, ac, br, bc};
}
}
// ---- 2‑copy ---------------------------------------------------
for (auto [b1r, b1c] : cells) {
if (b1r == ar && b1c == ac) continue;
for (auto [b2r, b2c] : cells) {
if ((b2r == ar && b2c == ac) || (b2r == b1r && b2c == b1c)) continue;
int cost = manh(r,c, b1r,b1c)+1 +
manh(b1r,b1c, b2r,b2c)+1 +
manh(b2r,b2c, ar,ac)+1;
if (cost > MAX_COST12 || (int)ops.size() + cost > T) continue;
int gain = (a_val ^ (s ^ A[b1r][b1c] ^ A[b2r][b2c])) - a_val;
if (gain <= 0) continue;
double ratio = (double)gain / cost;
if (ratio > best.ratio) {
best = {ratio, gain, cost, '2', ar, ac, b1r, b1c, b2r, b2c};
}
}
}
// ---- 3‑copy ---------------------------------------------------
for (auto [b1r, b1c] : cells) {
if (b1r == ar && b1c == ac) continue;
for (auto [b2r, b2c] : cells) {
if ((b2r == ar && b2c == ac) || (b2r == b1r && b2c == b1c)) continue;
for (auto [b3r, b3c] : cells) {
if (b3r == ar && b3c == ac) continue;
if ((b3r == b1r && b3c == b1c) || (b3r == b2r && b3c == b2c)) continue;
int cost = manh(r,c, b1r,b1c)+1 +
manh(b1r,b1c, b2r,b2c)+1 +
manh(b2r,b2c, b3r,b3c)+1 +
manh(b3r,b3c, ar,ac)+1;
if (cost > MAX_COST3 || (int)ops.size() + cost > T) continue;
int gain = (a_val ^
(s ^ A[b1r][b1c] ^ A[b2r][b2c] ^ A[b3r][b3c])) - a_val;
if (gain <= 0) continue;
double ratio = (double)gain / cost;
if (ratio > best.ratio) {
best = {ratio, gain, cost, '3',
ar, ac, b1r, b1c, b2r, b2c, b3r, b3c};
}
}
}
}
}
// ---------- 改善手なし → 終了 ----------
if (best.ratio < 0) break;
// ---------- ログ (stderr) ----------
if (best.type == '1') {
cerr << "Step " << step << ": 1‑copy "
<< "a=(" << best.ar+1 << "," << best.ac+1 << ") val=" << A[best.ar][best.ac]
<< " | b=(" << best.b1r+1 << "," << best.b1c+1 << ") val=" << A[best.b1r][best.b1c]
<< " | s=" << s << " | gain=" << best.gain
<< "/cost=" << best.cost << '\n';
} else if (best.type == '2') {
cerr << "Step " << step << ": 2‑copy "
<< "a=(" << best.ar+1 << "," << best.ac+1 << ") val=" << A[best.ar][best.ac]
<< " | b1=(" << best.b1r+1 << "," << best.b1c+1 << ") val=" << A[best.b1r][best.b1c]
<< " | b2=(" << best.b2r+1 << "," << best.b2c+1 << ") val=" << A[best.b2r][best.b2c]
<< " | s=" << s << " | gain=" << best.gain
<< "/cost=" << best.cost << '\n';
} else { // 3‑copy
cerr << "Step " << step << ": 3‑copy "
<< "a=(" << best.ar+1 << "," << best.ac+1 << ") val=" << A[best.ar][best.ac]
<< " | b1=(" << best.b1r+1 << "," << best.b1c+1 << ") val=" << A[best.b1r][best.b1c]
<< " | b2=(" << best.b2r+1 << "," << best.b2c+1 << ") val=" << A[best.b2r][best.b2c]
<< " | b3=(" << best.b3r+1 << "," << best.b3c+1 << ") val=" << A[best.b3r][best.b3c]
<< " | s=" << s << " | gain=" << best.gain
<< "/cost=" << best.cost << '\n';
}
// ---------- 手を実行 ----------
if (best.type == '1') {
int vb = A[best.b1r][best.b1c];
addMoves(r,c, best.b1r,best.b1c, ops); ops.push_back('C');
s ^= vb; r = best.b1r; c = best.b1c;
addMoves(r,c, best.ar,best.ac, ops); ops.push_back('W');
A[best.ar][best.ac] ^= s;
r = best.ar; c = best.ac;
} else if (best.type == '2') {
int vb1 = A[best.b1r][best.b1c], vb2 = A[best.b2r][best.b2c];
addMoves(r,c, best.b1r,best.b1c, ops); ops.push_back('C');
s ^= vb1; r = best.b1r; c = best.b1c;
addMoves(r,c, best.b2r,best.b2c, ops); ops.push_back('C');
s ^= vb2; r = best.b2r; c = best.b2c;
addMoves(r,c, best.ar,best.ac, ops); ops.push_back('W');
A[best.ar][best.ac] ^= s;
r = best.ar; c = best.ac;
} else { // 3‑copy
int vb1 = A[best.b1r][best.b1c], vb2 = A[best.b2r][best.b2c], vb3 = A[best.b3r][best.b3c];
addMoves(r,c, best.b1r,best.b1c, ops); ops.push_back('C');
s ^= vb1; r = best.b1r; c = best.b1c;
addMoves(r,c, best.b2r,best.b2c, ops); ops.push_back('C');
s ^= vb2; r = best.b2r; c = best.b2c;
addMoves(r,c, best.b3r,best.b3c, ops); ops.push_back('C');
s ^= vb3; r = best.b3r; c = best.b3c;
addMoves(r,c, best.ar,best.ac, ops); ops.push_back('W');
A[best.ar][best.ac] ^= s;
r = best.ar; c = best.ac;
}
++step;
}
// ---------- 出力 ----------
for (char ch : ops) cout << ch << '\n';
return 0;
}