#1107825 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: mtmr_s1
• 提出日時: 2025-07-26 13:43:04
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 8,157 bytes
• コンパイル時間: 2,210 ms
• コンパイル使用メモリ: 209,644 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,764,444,585
• 最終ジャッジ日時: 2025-07-26 13:43:10
• 合計ジャッジ時間: 5,660 ms
• ジャッジサーバーID （参考情報）: judge6 / judge4

ファイルパターン	結果
other	AC * 50

ソースコード

/*****************************************************************************************
 *  XOR-Printer 10×10  ―  “ランダム順＋局所乱択” ベースライン
 *
 *  ▼ アルゴリズム
 *  1. 100 マスの訪問順をシャッフル
 *  2. 各区間 (start → goal) で
 *       - PATH_TRIALS 本の “ランダムな最短経路” を生成
 *       - 各経路について COPY_TRIALS 通りの Copy 位置を乱択
 *       - 目標マスで Write したときの増点が最大のものを採用
 *       - Write は **after > before の場合しか出さない**（減点禁止）
 *  3. 累計 1000 手、または 1.9 秒で打ち切り
 *  4. 余った手はランダムウォークしつつ Hill-Climb（増点なら必ず Write）
 *
 *****************************************************************************************/
#include <bits/stdc++.h>
using namespace std;

/* ====== 型と定数 ====== */
using u32 = uint32_t;
struct XY { int r, c; };

constexpr int N            = 10;
constexpr int MAX_OPS      = 1000;
constexpr long long TL_US  = 1'900'000;        // 1.9 秒で安全停止
constexpr int PATH_TRIALS  = 20;               // 各区間で試す経路本数
constexpr int COPY_TRIALS  = 32;               // 各経路で試す Copy 組み合わせ数

/* ====== 盤面・状態 ====== */
u32 A[N][N];                 // 現在の値
u32 s = 0;                   // 手持ち値
XY  pos{0,0};                // 現在位置

/* ====== 出力操作列 ====== */
vector<char> OPS;
inline bool ops_full()                 { return (int)OPS.size() >= MAX_OPS; }
inline void emit(char op)              { if (!ops_full()) OPS.push_back(op); }

/* ====== 乱数ユーティリティ ====== */
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rnd(T ub)   { return uniform_int_distribution<T>(0, ub - 1)(rng); }
inline bool coin()                     { return uniform_int_distribution<int>(0,1)(rng); }

/* ====== タイムリミット ====== */
auto T0 = chrono::steady_clock::now();
inline bool time_over() {
    return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - T0).count() > TL_US;
}

/* ====== 座標ヘルパ ====== */
inline int mdist(const XY& a, const XY& b) {
    return abs(a.r - b.r) + abs(a.c - b.c);
}

/* ------------------------------------------------------------
 *  ランダムな最短経路を 1 本生成
 *    – 戻り値: 移動後座標列 (goal を含む)
 * ----------------------------------------------------------*/
vector<XY> random_shortest_path(const XY& st, const XY& gl) {
    int dr = gl.r - st.r, dc = gl.c - st.c;
    vector<char> moves;
    moves.insert(moves.end(), abs(dr), dr < 0 ? 'U' : 'D');
    moves.insert(moves.end(), abs(dc), dc < 0 ? 'L' : 'R');
    shuffle(moves.begin(), moves.end(), rng);

    vector<XY> path;
    path.reserve(moves.size());
    XY cur = st;
    for (char mv : moves) {
        if (mv == 'U') --cur.r;
        else if (mv == 'D') ++cur.r;
        else if (mv == 'L') --cur.c;
        else               ++cur.c;
        path.push_back(cur);
    }
    return path;                // len == mdist
}

/* ------------------------------------------------------------
 *  1 候補パスをシミュレーションして評価
 *    – Copy は copyMask の bit で指定
 *    – Write は「増点になる場合だけ」 ops の末尾に付ける
 * ----------------------------------------------------------*/
struct Cand {
    long long gain;             // 得点増分 (>=0, 0 の場合は Write 無し)
    vector<char> ops;           // 操作列
    u32 end_s;                  // 終点での手持ち s
};

Cand simulate(const vector<XY>& path, uint32_t copyMask, u32 cur_s) {
    Cand res; res.gain = 0;
    vector<char>& ops = res.ops;
    XY cur = pos;
    u32 tmp_s = cur_s;

    /* ---- 移動＋Copy ---- */
    for (size_t i = 0; i < path.size(); ++i) {
        const XY& nx = path[i];
        // 移動 1 step
        if      (nx.r < cur.r) ops.push_back('U');
        else if (nx.r > cur.r) ops.push_back('D');
        else if (nx.c < cur.c) ops.push_back('L');
        else                   ops.push_back('R');
        cur = nx;

        // Copy?
        if (copyMask & (1u << i)) {
            tmp_s ^= A[cur.r][cur.c];
            ops.push_back('C');
        }
    }

    /* ---- Write (必要なら) ---- */
    u32 after = A[cur.r][cur.c] ^ tmp_s;
    if (after > A[cur.r][cur.c]) {
        res.gain = after - A[cur.r][cur.c];
        ops.push_back('W');
    }
    res.end_s = tmp_s;
    return res;
}

/* ------------------------------------------------------------
 *  操作列を実際に適用（盤面・状態更新 & 出力）
 *      – W は必ず再チェックして「増点時のみ」実行
 * ----------------------------------------------------------*/
void apply_ops(const vector<char>& ops) {
    for (char op : ops) {
        if (ops_full()) break;

        if (op == 'U' || op == 'D' || op == 'L' || op == 'R') {
            emit(op);
            if (op == 'U') --pos.r;
            else if (op == 'D') ++pos.r;
            else if (op == 'L') --pos.c;
            else               ++pos.c;
        }
        else if (op == 'C') {
            emit('C');
            s ^= A[pos.r][pos.c];
        }
        else if (op == 'W') {
            u32 after = A[pos.r][pos.c] ^ s;
            if (after > A[pos.r][pos.c] && !ops_full()) {
                emit('W');
                A[pos.r][pos.c] = after;           // 書き込み確定
            }
        }
    }
}

/* ==============================
 *            main
 * ============================*/
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* --- 入力 --- */
    int Nin, Tlim;   // N=10, T=1000 固定
    cin >> Nin >> Tlim;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];

    /* --- 100 マスの訪問順をシャッフル --- */
    vector<int> order(100);
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);

    /* --- 各区間で乱択探索 --- */
    for (int k = 0; k < 100 && !ops_full() && !time_over(); ++k) {
        XY goal{ order[k] / 10, order[k] % 10 };
        if (goal.r == pos.r && goal.c == pos.c) continue;

        long long bestGain = -1;
        Cand bestCand;

        for (int p = 0; p < PATH_TRIALS && !time_over(); ++p) {
            auto path = random_shortest_path(pos, goal);

            for (int t = 0; t < COPY_TRIALS; ++t) {
                uint32_t mask = rnd<uint32_t>(1u << path.size());
                Cand cand = simulate(path, mask, s);

                if ((int)OPS.size() + (int)cand.ops.size() > MAX_OPS) continue;
                if (cand.gain > bestGain) { bestGain = cand.gain; bestCand = std::move(cand); }
            }
        }

        /* bestGain < 0 なら Write 無しの短経路を使う */
        if (bestGain < 0) {
            auto plain = random_shortest_path(pos, goal);
            bestCand = simulate(plain, 0u, s);   // Write 無し (gain=0)
        }

        apply_ops(bestCand.ops);
        s = bestCand.end_s;                      // Copy 分だけ更新
    }

    /* --- 余った手：ランダムウォーク Hill-Climb --- */
    const int d4[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while (!ops_full() && !time_over()) {
        int dir = rnd(4);
        XY nxt{ pos.r + d4[dir][0], pos.c + d4[dir][1] };
        if (nxt.r < 0 || nxt.r >= N || nxt.c < 0 || nxt.c >= N) continue;

        /* 移動 */
        emit(dir == 0 ? 'U' : dir == 1 ? 'D' : dir == 2 ? 'L' : 'R');
        pos = nxt;

        /* Write が増点なら必ず実行 */
        u32 after = A[pos.r][pos.c] ^ s;
        if (after > A[pos.r][pos.c] && !ops_full()) {
            emit('W');
            A[pos.r][pos.c] = after;
        }
        else if (!ops_full() && coin()) {        // 50 % で Copy 試行
            emit('C');
            s ^= A[pos.r][pos.c];
        }
    }

    /* --- 出力（ヘッダ行なし） --- */
    for (char c : OPS) cout << c << '\n';
    return 0;
}