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

• 問題: No.5022 XOR Printer
• ユーザー: prussian_coder
• 提出日時: 2025-07-15 11:24:26
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 736 ms / 2,000 ms
• コード長: 7,528 bytes
• コンパイル時間: 1,994 ms
• コンパイル使用メモリ: 137,416 KB
• 実行使用メモリ: 455,552 KB
• スコア: 5,223,434,866
• 最終ジャッジ日時: 2025-07-26 12:42:11
• 合計ジャッジ時間: 38,536 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <cstdint>
#include <utility>
#include <limits>
#include <functional>

using namespace std;

static int N, T;
static int N2;

inline pair<int,int> to2d(int p) {
    return {p / N, p % N};
}
inline int manhattan_distance(int p1, int p2) {
    auto [x1,y1] = to2d(p1);
    auto [x2,y2] = to2d(p2);
    return abs(x1 - x2) + abs(y1 - y2);
}

// Generate movement commands
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;
}

// Iterate over positions within manhattan distance <=8
inline void for_each_near(int pos, const function<void(int)>& f) {
    auto [x,y] = to2d(pos);
    for (int dx = -8; dx <= 8; ++dx) {
        int nx = x + dx;
        if (nx < 0 || nx >= N) continue;
        int rem = 8 - abs(dx);
        for (int dy = -rem; dy <= rem; ++dy) {
            int ny = y + dy;
            if (ny < 0 || ny >= N) continue;
            f(nx * N + ny);
        }
    }
}

struct State {
    vector<int> board;
    int s, pos, turn, score, prev_c_cnt;
    State* prev_state;
    pair<char,int> prev_action;
    State(const vector<int>& b, int _s, int _pos, int _turn, int _score)
        : board(b), s(_s), pos(_pos), turn(_turn), score(_score), prev_c_cnt(0), prev_state(nullptr), prev_action({'?',0}) {}
};

bool state_is_valid(const State* st) {
    if (st->turn == T) return true;
    int mask = (1 << 19) - 1;
    for (int v : st->board) {
        mask &= v;
        if (mask == 0) return true;
    }
    return false;
}

int state_last_score(const State* st) {
    int min_v = numeric_limits<int>::max();
    int min_pos = 0;
    for (int i = 0; i < N2; ++i) {
        if (st->board[i] < min_v) {
            min_v = st->board[i];
            min_pos = i;
        }
    }
    int dist = manhattan_distance(st->pos, min_pos);
    if (st->turn + dist + 3 >= T) return 0;
    return st->score + st->s - min_v;
}

vector<char> state_last_move(const State* st) {
    int min_v = numeric_limits<int>::max();
    int min_pos = 0;
    for (int i = 0; i < N2; ++i) {
        if (st->board[i] < min_v) {
            min_v = st->board[i];
            min_pos = i;
        }
    }
    auto cmds = generate_move_commands(st->pos, min_pos);
    cmds.push_back('W');
    cmds.push_back('C');
    cmds.push_back('W');
    return cmds;
}

struct BeamSearchSolver {
    static const int BEAM_WIDTH = 80;
    static const int STATE_QUE_SIZE = 10;
    struct PairHash { size_t operator()(uint64_t x) const { return x; } };

    State* process(const vector<int>& init_board) {
        // static arrays to avoid dynamic vector allocations
        static State* states[STATE_QUE_SIZE][BEAM_WIDTH];
        static int states_size[STATE_QUE_SIZE];
        for (int i = 0; i < STATE_QUE_SIZE; ++i) states_size[i] = 0;

        auto cmp = [](State* a, State* b) { return a->score > b->score; };

        // initial state
        State* initial = new State(init_board, 0, 0, 0,
            accumulate(init_board.begin(), init_board.end(), 0));
        states[0][0] = initial;
        states_size[0] = 1;
        push_heap(&states[0][0], &states[0][0] + 1, cmp);

        int best_score = 0;
        State* best_state = nullptr;

        for (int turn = 0; turn < T; ++turn) {
            int idx = turn % STATE_QUE_SIZE;
            // snapshot current states
            int curr_size = states_size[idx];
            State* curr[BEAM_WIDTH];
            for (int i = 0; i < curr_size; ++i) curr[i] = states[idx][i];
            states_size[idx] = 0;  // clear for next generation

            unordered_set<uint64_t, PairHash> seen;
            for (int i = 0; i < curr_size; ++i) {
                State* st = curr[i];
                uint64_t key = (uint64_t(st->score) << 16) | uint32_t(st->s/1024);
                if (!seen.insert(key).second) continue;
                // generate moves
                for_each_near(st->pos, [&](int v2) {
                    try_push(st, 'W', v2, states, states_size, cmp);
                    if (st->prev_c_cnt < 2) try_push(st, 'C', v2, states, states_size, cmp);
                });
            }
            // evaluate final scores
            for (int i = 0; i < curr_size; ++i) {
                int fs = state_last_score(curr[i]);
                if (fs > best_score) {
                    best_score = fs;
                    best_state = curr[i];
                }
            }
        }
        return best_state;
    }

    void try_push(State* st, char key, int pos,
                  State* states[][BEAM_WIDTH], int states_size[],
                  const function<bool(State*,State*)>& cmp) {
        int dist = manhattan_distance(st->pos, pos);
        int next_turn = st->turn + dist + 1;
        if (next_turn > T) return;
        int new_score = (key == 'C') ? st->score
                          : st->score + ((st->board[pos] ^ st->s) - st->board[pos]);
        int idx = next_turn % STATE_QUE_SIZE;
        int sz = states_size[idx];
        if (sz < BEAM_WIDTH) {
            State* ns = apply_move(st, key, pos, next_turn, new_score);
            if (state_is_valid(ns)) {
                states[idx][sz] = ns;
                ++states_size[idx];
                push_heap(&states[idx][0], &states[idx][states_size[idx]], cmp);
            }
        } else if (new_score > states[idx][0]->score) {
            State* ns = apply_move(st, key, pos, next_turn, new_score);
            if (state_is_valid(ns)) {
                pop_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
                states[idx][BEAM_WIDTH - 1] = ns;
                push_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
            }
        }
    }

    State* apply_move(State* st, char key, int pos,
                      int next_turn, int new_score) {
        State* ns = new State(*st);
        ns->prev_state = st;
        ns->prev_action = {key, st->pos};
        ns->turn = next_turn;
        ns->score = new_score;
        if (key == 'C') {
            ns->s ^= st->board[pos];
            ns->prev_c_cnt = st->prev_c_cnt + 1;
        } else {
            ns->board[pos] = st->board[pos] ^ st->s;
            ns->prev_c_cnt = 0;
        }
        ns->pos = pos;
        return ns;
    }
};

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

    cin >> N >> T;
    N2 = N * N;
    vector<int> board;
    board.reserve(N2);
    for (int i = 0; i < N2; ++i) {
        int x; cin >> x;
        board.push_back(x);
    }

    BeamSearchSolver solver;
    State* best = solver.process(board);
    vector<char> last_actions = state_last_move(best);
    vector<char> actions;
    for (State* cur = best; cur->prev_state != nullptr; cur = cur->prev_state) {
        auto [key, last_pos] = cur->prev_action;
        actions.push_back(key);
        auto cmds = generate_move_commands(last_pos, cur->pos);
        for (auto it = cmds.rbegin(); it != cmds.rend(); ++it) {
            actions.push_back(*it);
        }
    }
    reverse(actions.begin(), actions.end());
    actions.insert(actions.end(), last_actions.begin(), last_actions.end());
    for (char c : actions) {
        cout << c << '\n';
    }

    return 0;
}