結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 bird01
|
| 提出日時 | 2025-07-26 16:59:55 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 7,246 bytes |
| コンパイル時間 | 3,764 ms |
| コンパイル使用メモリ | 307,280 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,194,490,680 |
| 最終ジャッジ日時 | 2025-07-26 17:04:03 |
| 合計ジャッジ時間 | 5,892 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// 1.ベースライン,何もしない
// 2.最適なsを求め,全セルをフリップ→?
// 3.最大桁を1にする
// 4.2桁目も1にする→壊れている
// 5.2桁目も1にする
// 6.1セル犠牲にしてs=0にリセット,上位桁から1にする
// 7.犠牲になるセルは候補の中で現在の値が最大のものにする→これだけだとターン数増加でスコア低下,移動順の工夫でデメリット消失
// 8.移動順を2-optで修正
// 9.s=0にリセットした後(0,0)に移動しないようにした,s=0にリセットする際の訪問順を2パターン試すようにした
// 10.2-opt最適化で最初に訪問するセルが(0,0)になっていたので自由にした
// 11.sをセットする際の訪問順を2パターン試すようにした
// 12.初期解を螺旋順に変更
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i < (b); i++)
typedef pair<int,int> pii;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, T;
cin >> n >> T;
vector<vector<int>> A(n, vector<int>(n));
rep(i, 0, n) rep(j, 0, n) cin >> A[i][j];
vector<char> ops;
int cx = 0, cy = 0;
int s = 0;
// マンハッタン距離計算
auto dist = [&](const pii &p1, const pii &p2) {
return abs(p1.first - p2.first) + abs(p1.second - p2.second);
};
auto distc = [&](int x1, int y1, const pii &p2) {
return abs(x1 - p2.first) + abs(y1 - p2.second);
};
// 移動ヘルパー
auto moveTo = [&](const pii &to) {
while (ops.size() < T && cx < to.first) { ops.push_back('D'); ++cx; }
while (ops.size() < T && cx > to.first) { ops.push_back('U'); --cx; }
while (ops.size() < T && cy < to.second) { ops.push_back('R'); ++cy; }
while (ops.size() < T && cy > to.second) { ops.push_back('L'); --cy; }
};
// 最大ビット検出
int maxBit = 0;
rep(i, 0, n) rep(j, 0, n) if (A[i][j] > 0) {
int b = 31 - __builtin_clz(A[i][j]);
maxBit = max(maxBit, b);
}
// 各ビットを大きい方から処理
rep(order, 0, maxBit+1) {
if (ops.size() >= T) break;
int bit = maxBit - order;
// 1) セル選択
vector<pii> single;
vector<pair<pii,pii>> pairs;
rep(i, 0, n) rep(j, 0, n) {
int v = A[i][j];
if (((v >> bit) & 1) && [&]{ for (int b2 = bit+1; b2 <= maxBit; ++b2) if ((v >> b2) & 1) return false; return true; }()) {
single.emplace_back(i,j);
}
}
if (order > 0) {
rep(i1, 0, n) rep(j1, 0, n) rep(i2, i1, n) rep(j2, 0, n) {
if (i1 == i2 && j1 >= j2) continue;
int v = A[i1][j1] ^ A[i2][j2];
if (((v >> bit) & 1) && [&]{ for (int b2 = bit+1; b2 <= maxBit; ++b2) if ((v >> b2) & 1) return false; return true; }()) {
pairs.emplace_back(pii(i1,j1), pii(i2,j2));
}
}
}
// 2) 選択
vector<pii> sel;
if (order == 0) {
int bestD = INT_MAX;
for (auto &p : single) {
int d = distc(cx, cy, p);
if (d < bestD) { bestD = d; sel = {p}; }
}
} else {
int bestMn = -1;
for (auto &pr : pairs) {
int v1 = A[pr.first.first][pr.first.second];
int v2 = A[pr.second.first][pr.second.second];
int mn = min(v1, v2);
if (mn > bestMn) { bestMn = mn; sel = {pr.first, pr.second}; }
}
}
if (sel.empty()) continue;
// 3) 選択セル訪問 & コピー (順序を試す)
set<int> skip;
if (sel.size() == 2) {
pii start = {cx, cy};
pii p0 = sel[0], p1 = sel[1];
int costA = distc(start.first, start.second, p0) + 1 + dist(p0, p1) + 1;
int costB = distc(start.first, start.second, p1) + 1 + dist(p1, p0) + 1;
vector<pii> orderSel = (costA <= costB ? sel : vector<pii>{p1, p0});
for (auto &p : orderSel) {
moveTo(p);
if (ops.size() >= T) break;
ops.push_back('C'); s ^= A[p.first][p.second];
skip.insert(p.first * n + p.second);
}
} else {
for (auto &p : sel) {
moveTo(p);
if (ops.size() >= T) break;
ops.push_back('C'); s ^= A[p.first][p.second];
skip.insert(p.first * n + p.second);
}
}
if (ops.size() >= T) break;
// 4) 書き込み対象列挙
vector<pii> writes;
rep(i, 0, n) {
if (i % 2 == 0) rep(j, 0, n) {
int idx = i*n + j;
if (!skip.count(idx)) {
int nxt = A[i][j] ^ s;
if (nxt > A[i][j]) writes.emplace_back(i,j);
}
} else for (int j = n-1; j >= 0; --j) {
int idx = i*n + j;
if (!skip.count(idx)) {
int nxt = A[i][j] ^ s;
if (nxt > A[i][j]) writes.emplace_back(i,j);
}
}
}
// 5) 初期解: グリーディで最寄りを順繰りに訪問
auto writesCopy = writes; // 元の書き込みリスト
int P = writesCopy.size();
vector<pii> base;
if (P > 0) {
vector<bool> used(P, false);
pii curPos = {cx, cy};
rep(k, 0, P) {
int bestIdx = -1;
int bestDist = INT_MAX;
rep(i, 0, P) if (!used[i]) {
int d = dist(curPos, writesCopy[i]);
if (d < bestDist) { bestDist = d; bestIdx = i; }
}
base.push_back(writesCopy[bestIdx]);
used[bestIdx] = true;
curPos = base.back();
}
}
// 2-opt 最適化
if (base.size() >= 2) {
bool improved = true;
while (improved) {
improved = false;
rep(i, 0, (int)base.size()-1) {
rep(j, i+1, (int)base.size()) {
pii prev = (i > 0 ? base[i-1] : pii(cx, cy));
pii cur = base[i];
pii endp = base[j];
pii nextp = (j+1 < (int)base.size() ? base[j+1] : sel.front());
int oldC = dist(prev, cur) + dist(endp, nextp);
int newC = dist(prev, endp) + dist(cur, nextp);
if (newC < oldC) {
reverse(base.begin()+i, base.begin()+j+1);
improved = true;
break;
}
}
if (improved) break;
}
}
}
// 6) 書き込み実行
for (auto &p : base) {
moveTo(p);
if (ops.size() >= T) break;
ops.push_back('W'); A[p.first][p.second] ^= s;
}
if (ops.size() >= T) break;
// 7) リセット: sel 再訪問 & コピー (順序を試す)
if (sel.size() == 2) {
// 現在位置
pii start = {cx, cy};
// 順序A: sel[0], sel[1]
int dA1 = distc(start.first, start.second, sel[0]) + 1;
int dA2 = dist(sel[0], sel[1]) + 1;
int costA = dA1 + dA2;
// 順序B: sel[1], sel[0]
int dB1 = distc(start.first, start.second, sel[1]) + 1;
int dB2 = dist(sel[1], sel[0]) + 1;
int costB = dB1 + dB2;
vector<pii> order = (costA <= costB ? sel : vector<pii>{sel[1], sel[0]});
for (auto &p : order) {
moveTo(p);
if (ops.size() >= T) break;
ops.push_back('C'); s ^= A[p.first][p.second];
}
} else {
for (auto &p : sel) {
moveTo(p);
if (ops.size() >= T) break;
ops.push_back('C'); s ^= A[p.first][p.second];
}
}
if (ops.size() >= T) break;
}
// 出力
rep(i, 0, ops.size()) cout << ops[i] << '\n';
return 0;
}