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

• 問題: No.5022 XOR Printer
• ユーザー: prussian_coder
• 提出日時: 2025-07-14 22:12:08
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,904 ms / 2,000 ms
• コード長: 6,585 bytes
• コンパイル時間: 1,418 ms
• コンパイル使用メモリ: 136,488 KB
• 実行使用メモリ: 68,224 KB
• スコア: 5,199,078,246
• 最終ジャッジ日時: 2025-07-26 12:40:12
• 合計ジャッジ時間: 94,633 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

using namespace std;

int N, T, N2;
vector<vector<int>> NEAR_POS;

pair<int,int> to2d(int pos) {
    return { pos / N, pos % N };
}

int manhattan_distance(int p1, int p2) {
    auto [x1,y1] = to2d(p1);
    auto [x2,y2] = to2d(p2);
    return abs(x1 - x2) + abs(y1 - y2);
}

vector<char> generate_move_commands(int start, int end) {
    vector<char> cmds;
    auto [x1,y1] = to2d(start);
    auto [x2,y2] = to2d(end);
    int cx = x1, cy = y1;
    while (cx < x2) { cmds.push_back('D'); ++cx; }
    while (cx > x2) { cmds.push_back('U'); --cx; }
    while (cy < y2) { cmds.push_back('R'); ++cy; }
    while (cy > y2) { cmds.push_back('L'); --cy; }
    return cmds;
}

struct State {
    vector<int> board;
    int s, pos, turn, score;
    State* prev_state;
    pair<char,int> prev_action;

    State(const vector<int>& b, int _s, int _pos, int _turn, int _score,
          State* p = nullptr, pair<char,int> act = {'\0',0})
      : board(b), s(_s), pos(_pos), turn(_turn), score(_score),
        prev_state(p), prev_action(act) {}

    bool is_done() const {
        return turn == T;
    }

    bool is_valid() const {
        if (is_done()) return true;
        int b = (1<<19) - 1;
        for (int v : board) {
            b &= v;
            if (b == 0) return true;
        }
        return false;
    }

    vector<pair<char,int>> get_next_moves() const {
        vector<pair<char,int>> mv;
        for (int np : NEAR_POS[pos]) {
            mv.emplace_back('W', np);
            mv.emplace_back('C', np);
        }
        return mv;
    }

    int get_next_turn(int np) const {
        return turn + manhattan_distance(pos, np) + 1;
    }

    int calc_next_score(char key, int np) const {
        if (key == 'C') return score;
        int new_v = board[np] ^ s;
        return score + new_v - board[np];
    }

    State* process_move(char key, int np) const {
        State* ns = new State(*this);
        ns->prev_state   = const_cast<State*>(this);
        ns->prev_action  = { key, pos };
        ns->turn         = get_next_turn(np);
        if (key == 'C') {
            ns->s ^= ns->board[np];
        } else {
            ns->score         = calc_next_score(key, np);
            ns->board[np]    ^= ns->s;
        }
        ns->pos = np;
        return ns;
    }

    int last_score() const {
        int min_v = board[0], min_p = 0;
        for (int i = 1; i < board.size(); ++i)
            if (board[i] < min_v) { min_v = board[i]; min_p = i; }
        int d = manhattan_distance(pos, min_p);
        if (turn + d + 3 >= T) return 0;
        int sum = 0;
        for (int v : board) sum += v;
        return sum + s - min_v;
    }

    vector<char> last_move() const {
        int min_v = board[0], min_p = 0;
        for (int i = 1; i < board.size(); ++i)
            if (board[i] < min_v) { min_v = board[i]; min_p = i; }
        auto cmds = generate_move_commands(pos, min_p);
        cmds.push_back('W');
        cmds.push_back('C');
        cmds.push_back('W');
        return cmds;
    }
};

class BeamSearchSolver {
public:
    int beam_width     = 100;
    int state_que_size = 15;

    State* process(const vector<int>& init_board) {
        vector<vector<State*>> states(state_que_size);
        int init_score = 0;
        for (int v : init_board) init_score += v;

        State* init = new State(init_board, 0, 0, 0, init_score);
        states[0].push_back(init);

        int best_score = 0;
        State* best_state = nullptr;

        for (int turn = 0; turn < T; ++turn) {
            auto &curr = states[turn % state_que_size];
            for (State* st : curr) {
                for (auto [key, np] : st->get_next_moves()) {
                    int nt = st->get_next_turn(np);
                    if (nt > T) continue;
                    int sc = st->calc_next_score(key, np);
                    if (sc < st->score) continue;

                    int idx = nt % state_que_size;
                    if (states[idx].size() < beam_width) {
                        State* ns = st->process_move(key, np);
                        if (ns->is_valid()) states[idx].push_back(ns);
                    } else {
                        // find and replace worst (minimum) if better
                        int min_i = 0, min_s = states[idx][0]->score;
                        for (int i = 1; i < states[idx].size(); ++i)
                            if (states[idx][i]->score < min_s) {
                                min_s = states[idx][i]->score;
                                min_i = i;
                            }
                        if (sc > min_s) {
                            State* ns = st->process_move(key, np);
                            if (ns->is_valid()) {
                                delete states[idx][min_i];
                                states[idx][min_i] = ns;
                            }
                        }
                    }
                }
            }

            if (turn >= T - 30) {
                for (State* st : curr) {
                    int ls = st->last_score();
                    if (ls > best_score) {
                        best_score = ls;
                        best_state = st;
                    }
                }
            }

            // clear out old states
            curr.clear();
        }

        return best_state;
    }
};

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

    cin >> N >> T;
    N2 = N * N;
    vector<int> board(N2);
    for (int i = 0; i < N2; ++i) {
        cin >> board[i];
    }

    NEAR_POS.assign(N2, {});
    for (int i = 0; i < N2; ++i) {
        for (int j = 0; j < N2; ++j) {
            if (manhattan_distance(i, j) <= 13) {
                NEAR_POS[i].push_back(j);
            }
        }
    }

    BeamSearchSolver solver;
    State* best = solver.process(board);

    // backtrack actions
    vector<char> actions_rev;
    State* cur = best;
    while (cur->prev_state) {
        actions_rev.push_back(cur->prev_action.first);
        auto cmds = generate_move_commands(cur->prev_action.second, cur->pos);
        reverse(cmds.begin(), cmds.end());
        for (char c : cmds) actions_rev.push_back(c);
        cur = cur->prev_state;
    }
    reverse(actions_rev.begin(), actions_rev.end());

    // append final moves
    auto tail = best->last_move();
    for (char c : tail) actions_rev.push_back(c);

    // output
    for (char c : actions_rev) {
        cout << c << "\n";
    }

    return 0;
}