結果

問題 No.5022 XOR Printer
ユーザー bird01
提出日時 2025-07-26 16:13:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,230 bytes
コンパイル時間 3,683 ms
コンパイル使用メモリ 300,324 KB
実行使用メモリ 7,716 KB
スコア 5,178,384,688
最終ジャッジ日時 2025-07-26 16:14:51
合計ジャッジ時間 5,679 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 1.ベースライン,何もしない
// 2.最適なsを求め,全セルをフリップ→?
// 3.最大桁を1にする
// 4.2桁目も1にする→壊れている
// 5.2桁目も1にする
// 6.1セル犠牲にしてs=0にリセット,上位桁から1にする
// 7.犠牲になるセルは候補の中で現在の値が最大のものにする→これだけだとターン数増加でスコア低下,移動順の工夫でデメリット消失
// 8.移動順を2-optで修正

#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);
      }
    }
    // ペア候補 (order>0)
    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;
    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) 書き込み対象列挙 (snake order)
    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) 2-opt 最適化 (tail: sel[0])
    auto tail = sel.front();
    auto base = writes;
    int P = base.size();
    if (P >= 2) {
      bool improved = true;
      while (improved) {
        improved = false;
        rep(i, 1, P) {
          rep(j, i+1, P) {
            pii prev = (i > 0 ? base[i-1] : pii(cx,cy));
            pii cur = base[i];
            pii endp = base[j];
            pii next = (j+1 < P ? base[j+1] : tail);
            int oldC = dist(prev, cur) + dist(endp, next);
            int newC = dist(prev, endp) + dist(cur, next);
            if (newC < oldC) {
              reverse(base.begin()+i, base.begin()+j+1);
              improved = true;
              break;
            }
          }
          if (improved) break;
        }
      }
    }

    // 6) base 順に移動 & W
    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 再訪問 & コピー
    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;

    // 8) (0,0) 戻り
    moveTo({0,0});
  }

  // 出力
  rep(i, 0, ops.size()) cout << ops[i] << '\n';
  return 0;
}
0