#1108008 (C++23) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: K2
• 提出日時: 2025-07-26 16:02:22
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,982 ms / 2,000 ms
• コード長: 7,348 bytes
• コンパイル時間: 3,281 ms
• コンパイル使用メモリ: 292,672 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,934,994,309
• 最終ジャッジ日時: 2025-07-26 16:04:09
• 合計ジャッジ時間: 106,567 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

/* --------------------------------------------------------------------------
 * Grid XOR Maximisation - 2‑phase solver (Random search → SA)
 * 固定長版：コピーセル数 = MAX_CHOOSE に固定
 *   • pos の長さは常に MAX_CHOOSE
 *   • 近傍操作は SWAP / REPLACE のみ（長さは変えない）
 * --------------------------------------------------------------------------
 */

// ---------- utilities ------------------------------------------------------
struct Timer {
    using Clock = chrono::high_resolution_clock;
    chrono::time_point<Clock> st{Clock::now()};
    double elapsed() const {
        return chrono::duration<double>(Clock::now() - st).count();
    }
};

// ---------- constants ------------------------------------------------------
constexpr int N = 10;
constexpr int OP_LIMIT = 1000;
constexpr int MAX_CHOOSE = 7;       // ← 固定長
constexpr double RAND_PHASE = 1.00; // seconds for pure random search
constexpr double TL = 1.98;         // total time limit (s)

using Board = array<array<uint32_t, N>, N>;

// ---------- state representation ------------------------------------------
struct State {
    array<int, MAX_CHOOSE> pos;   // fixed‑size array (indices 0..99)
    vector<uint32_t> s;           // size MAX_CHOOSE+1, s[0]=0
    bitset<100> mask;             // copy cell mask
    long long score = -1;         // board score
};

// ---------- helpers --------------------------------------------------------
inline bitset<100> make_mask(const array<int, MAX_CHOOSE>& pos) {
    bitset<100> bs;
    for (int v : pos) bs.set(v);
    return bs;
}

inline long long eval_board(const vector<uint32_t>& s,
                            const Board& A,
                            const bitset<100>& copyMask) {
    long long sum = 0;
    for (int idx = 0; idx < 100; ++idx) {
        int i = idx / N, j = idx % N;
        if (copyMask.test(idx)) {
            sum += A[i][j];
        } else {
            uint32_t best = A[i][j];
            for (uint32_t v : s) {
                uint32_t cand = A[i][j] ^ v;
                if (cand > best) best = cand;
            }
            sum += best;
        }
    }
    return sum;
}

inline void rebuild_prefXor(State& st, const Board& A) {
    st.s.resize(MAX_CHOOSE + 1);
    st.s[0] = 0;
    for (int k = 0; k < MAX_CHOOSE; ++k) {
        int idx = st.pos[k];
        st.s[k + 1] = st.s[k] ^ A[idx / N][idx % N];
    }
    st.mask = make_mask(st.pos);
}

// ---------- neighbour generator -------------------------------------------
struct Mutator {
    mt19937 rng;
    uniform_real_distribution<double> uni{0.0, 1.0};
    uniform_int_distribution<int> cellDist{0, 99};
    explicit Mutator(uint32_t seed) : rng(seed) {}

    array<int, MAX_CHOOSE> random_pos() {
        array<int, MAX_CHOOSE> v{};
        int filled = 0;
        while (filled < MAX_CHOOSE) {
            int x = cellDist(rng);
            bool dup = false;
            for (int i = 0; i < filled; ++i) if (v[i] == x) { dup = true; break; }
            if (!dup) v[filled++] = x;
        }
        return v;
    }

    // mutate in‑place (SWAP or REPLACE) keeping length constant
    void mutate(array<int, MAX_CHOOSE>& pos) {
        double r = uni(rng);
        if (r < 0.5) { // SWAP
            uniform_int_distribution<int> d(0, MAX_CHOOSE - 1);
            int a = d(rng), b = d(rng);
            if (a != b) swap(pos[a], pos[b]);
        } else {       // REPLACE one element with unused cell
            uniform_int_distribution<int> d(0, MAX_CHOOSE - 1);
            int idx = d(rng);
            for (int t = 0; t < 20; ++t) {
                int x = cellDist(rng);
                bool dup = false;
                for (int v : pos) if (v == x) { dup = true; break; }
                if (!dup) { pos[idx] = x; break; }
            }
        }
    }
};

// ---------- random search --------------------------------------------------
State random_search(const Board& A, Timer& timer, Mutator& mut) {
    State best; best.score = -1;
    while (timer.elapsed() < RAND_PHASE) {
        State st; st.pos = mut.random_pos();
        rebuild_prefXor(st, A);
        st.score = eval_board(st.s, A, st.mask);
        if (st.score > best.score) best = st;
    }
    return best;
}

// ---------- simulated annealing -------------------------------------------
State simulated_annealing(const Board& A, State init, Timer& timer, Mutator& mut) {
    State cur = init, best = cur;
    constexpr double T0 = 1e5, Tend = 1.0;

    while (true) {
        double t = timer.elapsed();
        if (t >= TL) break;
        double temp = T0 * pow(Tend / T0, (t - RAND_PHASE) / (TL - RAND_PHASE));

        State nxt = cur;
        mut.mutate(nxt.pos);
        rebuild_prefXor(nxt, A);
        nxt.score = eval_board(nxt.s, A, nxt.mask);

        long long diff = nxt.score - cur.score;
        if (diff >= 0 || mut.uni(mut.rng) < exp(double(diff) / temp)) {
            cur = nxt;
            if (cur.score > best.score) best = cur;
        }
    }
    return best;
}

// ---------- operation sequence builder ------------------------------------
vector<char> build_ops(const State& best, const Board& A) {
    const vector<uint32_t>& pref = best.s;
    const bitset<100>& mask = best.mask;

    array<array<int, N>, N> idx{}; for (auto& r : idx) r.fill(-1);

    for (int cell = 0; cell < 100; ++cell) {
        if (mask.test(cell)) continue;
        int i = cell / N, j = cell % N;
        int best_k = 0; uint32_t best_val = A[i][j];
        for (int k = 1; k <= MAX_CHOOSE; ++k) {
            uint32_t cand = A[i][j] ^ pref[k];
            if (cand > best_val) { best_val = cand; best_k = k; }
        }
        idx[i][j] = best_k;
    }

    vector<char> ops; ops.reserve(OP_LIMIT);
    auto push=[&](char c){ if((int)ops.size()<OP_LIMIT) ops.push_back(c); };

    for (int phase = 0; phase <= MAX_CHOOSE; ++phase) {
        if (phase > 0) {
            for (int row = 0; row < N; ++row) {
                for (int k = 0; k < N; ++k) {
                    int col = (row % 2 == 0) ? k : (N - 1 - k);
                    if (idx[row][col] == phase) push('W');
                    if (k != N - 1) push(row % 2 ? 'L' : 'R');
                }
                if (row != N - 1) push('D');
            }
            if (phase == MAX_CHOOSE) break;
        }
        int tgt = best.pos[phase]; int tx = tgt / N, ty = tgt % N;
        if (phase == 0) { for (int d = 0; d < tx; ++d) push('D'); }
        else            { for (int d = N - 1; d > tx; --d) push('U'); }
        for (int d = 0; d < ty; ++d) push('R');
        push('C');
        for (int d = ty; d > 0; --d) push('L');
        for (int d = tx; d > 0; --d) push('U');
    }

    if ((int)ops.size() > OP_LIMIT) ops.resize(OP_LIMIT);
    return ops;
}

// ---------- main -----------------------------------------------------------
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n_in, t_in; if (!(cin >> n_in >> t_in)) return 0;
    Board A{}; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> A[i][j];

    Timer timer; Mutator mut(123456789u);

    State init = random_search(A, timer, mut);
    State best = simulated_annealing(A, init, timer, mut);

    auto ops = build_ops(best, A);
    for (char c : ops) cout << c << '\n';
}