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

• 問題: No.5022 XOR Printer
• ユーザー: wanui
• 提出日時: 2025-07-26 20:20:51
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,883 ms / 2,000 ms
• コード長: 9,821 bytes
• コンパイル時間: 2,616 ms
• コンパイル使用メモリ: 222,216 KB
• 実行使用メモリ: 7,720 KB
• スコア: 5,212,457,459
• 最終ジャッジ日時: 2025-07-26 20:22:32
• 合計ジャッジ時間: 99,411 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

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

コンパイルメッセージ

main.cpp: In function ‘std::pair<board_t, std::vector<signed char> > rulebased(board_t, std::vector<signed char>)’:
main.cpp:198:111: warning: narrowing conversion of ‘(((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((distance_table[bd.board_t::player][z] + distance_table[z][o]) * 100)) + (marathon::engine.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % 100))’ from ‘std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
  198 |                         bestpair = min(bestpair, {(distance_table[bd.player][z] + distance_table[z][o]) * 100 + marathon::engine() % 100, {z, o}});
      |                                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

#include <bits/stdc++.h>
// clang-format off
#ifdef ONLINE_JUDGE
const int LOCAL = 0;
#else
const int LOCAL = 1;
#endif
using namespace std;
#define debug1(a) {if(LOCAL){cerr<<#a<<":"<<a<<endl; }}
#define debug2(a,b) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }}
#define debug3(a,b,c) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }}
#define debug4(a,b,c,d) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }}
#define debug5(a,b,c,d,e) {if(LOCAL){cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<" "<<#e<<":"<<e<<endl; }}
// clang-format on
const double CLOCK_RATIO = 1000;
using pii = pair<int, int>;
namespace marathon {
std::mt19937 engine(0);
clock_t start_time;
double now() {
    return CLOCK_RATIO * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
    start_time = clock();
    std::random_device seed_gen;
    engine.seed(seed_gen());
}
template <typename T>
void vecremove_first(std::vector<T> &vec, T elem) {
    // elemに一致する最初の要素を削除
    vec.erase(std::find(vec.begin(), vec.end(), elem));
}
};  // namespace marathon
const int inf = 1e9;
const int N = 10;
const int T = 1000;
const int N2 = 100;
int INIT_TBL[N2];
int distance_table[N2][N2];
const int8_t COPY = -1;
const int8_t WRITE = -2;

string int_to_bits(int x) {
    string res;
    for (int b = 19; b >= 0; b--) {
        if ((x >> b) & 1) {
            res.push_back('1');
        } else {
            res.push_back('0');
        }
    }
    return res;
}
void output(vector<int8_t> ops) {
    int player = 0;
    for (auto op : ops) {
        if (op == COPY) {
            cout << "C" << endl;
        } else if (op == WRITE) {
            cout << "W" << endl;
        } else {
            pii p = {player / N, player % N};
            pii g = {op / N, op % N};
            while (p != g) {
                if (p.first < g.first) {
                    cout << "D" << endl;
                    p.first++;
                } else if (p.first > g.first) {
                    cout << "U" << endl;
                    p.first--;
                } else if (p.second < g.second) {
                    cout << "R" << endl;
                    p.second++;
                } else if (p.second > g.second) {
                    cout << "L" << endl;
                    p.second--;
                } else {
                    assert(0);
                }
            }
            player = op;
        }
    }
}
struct board_t {
    int total_cost;
    int tbl[N2];
    int x;
    int player;
};
pair<board_t, vector<int8_t>> rulebased(board_t init_bd, vector<int8_t> init_ops) {
    // XORの性質を考えると「上の桁から順に 0→1 にする」のがよい
    int TS = T - 3;
    auto bd = init_bd;
    auto ops = init_ops;
    auto op_move = [&](int u) {
        bd.total_cost += distance_table[bd.player][u];
        bd.player = u;
        ops.push_back(u);
        assert(bd.total_cost <= T);
    };
    auto op_write = [&]() {
        bd.total_cost += 1;
        bd.tbl[bd.player] = bd.x ^ bd.tbl[bd.player];
        ops.push_back(WRITE);
        assert(bd.total_cost <= T);
    };
    auto op_copy = [&]() {
        bd.total_cost += 1;
        bd.x = bd.x ^ bd.tbl[bd.player];
        ops.push_back(COPY);
        assert(bd.total_cost <= T);
    };
    bitset<N2> ignored = 0;
    vector<int> terminals;
    int terminal_cost = 0;
    auto calc_terminal_cost = [&]() {
        if (terminals.size() == 0) return 0;
        return distance_table[bd.player][terminals[0]] + terminal_cost;
    };
    for (int bit = 19; bit >= 0; bit--) {
        bool must_change = false;
        {
            if (((bd.x >> bit) & 1) == 0) must_change = true;
            for (int b = bit + 1; b <= 19; b++) {
                if (((bd.x >> b) & 1) > 0) must_change = true;
            }
        }

        if (must_change) {
            pii bestmv = {inf, -1};
            for (int u = 0; u < N2; u++) {
                if (ignored[u]) continue;
                int y = bd.x ^ bd.tbl[u];
                if (((y >> bit) & 1) == 0) continue;
                bool ok = true;
                for (int b = bit + 1; b <= 19; b++) {
                    if ((y >> b) & 1) ok = false;
                }
                if (ok) {
                    bestmv = min(pii{(distance_table[bd.player][u] + 1) * 100 + marathon::engine() % 100, u}, bestmv);
                }
            }
            if (bestmv.first > TS - bd.total_cost - calc_terminal_cost()) break;

            {
                int u = bestmv.second;
                op_move(u);
                op_copy();
            }
        }
        // debug3(bit, bd.x, bd.player);
        vector<int> goals;
        for (int u = 0; u < N2; u++) {
            if (ignored[u]) continue;
            if ((bd.x ^ bd.tbl[u]) > bd.tbl[u]) {
                goals.push_back(u);
            }
        }

        {
            pair<int, pii> bestpair = {inf, {inf, inf}};
            while (goals.size()) {
                // debug1(goals.size());
                //  TODO TSPをちゃんと解く

                pii min_g = {inf, inf};
                for (auto g : goals) {
                    min_g = min(min_g, {(distance_table[bd.player][g] + 1) * 100 + marathon::engine() % 100, g});
                }
                if (min_g.first / 100 > TS - bd.total_cost - calc_terminal_cost()) break;
                {
                    int g = min_g.second;
                    op_move(g);
                    op_write();
                    marathon::vecremove_first(goals, g);
                }
            }

            if (goals.size() >= 1) break;
            if (bit > 0 && bit < 19) {
                // 1110と、1111を1個ずつ確保
                int nbit = bit - 1;
                vector<int> zero;
                vector<int> one;
                for (int g = 0; g < N2; g++) {
                    if (ignored[g]) continue;
                    if ((bd.tbl[g] >> nbit) & 1) {
                        one.push_back(g);
                    } else {
                        zero.push_back(g);
                    }
                }
                // debug2(one.size(), zero.size());
                for (auto z : zero) {
                    for (auto o : one) {
                        // int y = bd.tbl[z] ^ bd.tbl[o];
                        bestpair = min(bestpair, {(distance_table[bd.player][z] + distance_table[z][o]) * 100 + marathon::engine() % 100, {z, o}});
                    }
                }
                if (bestpair.first >= inf) break;
                int s = bestpair.second.first;
                int t = bestpair.second.second;
                // debug2(bit, int_to_bits(bd.x));
                if (distance_table[bd.player][s] + distance_table[s][t] + 4 > TS - bd.total_cost - calc_terminal_cost()) break;
                op_move(s);
                op_write();
                op_copy();
                op_write();
                op_move(t);
                op_copy();
                // debug3(bit, int_to_bits(bd.x), bd.total_cost);
                ignored[s] = 1;
            }
        }
        {
            vector<pii> terminal;
            for (int u = 0; u < N2; u++) {
                if (ignored[u]) {
                    terminal.push_back({bd.tbl[u], u});
                }
            }
            sort(terminal.begin(), terminal.end());

            terminal_cost = 0;
            terminals.clear();
            for (int i = 0; i < terminal.size(); i++) {
                terminals.push_back(terminal[i].second);
            }
            for (int j = 1; j < terminals.size(); j++) {
                terminal_cost += distance_table[terminals[j - 1]][terminals[j]] + 1;
            }
        }
    }
    do {
        vector<pii> terminal;
        pii nonterminal = {inf, inf};
        for (int u = 0; u < N2; u++) {
            if (ignored[u]) {
                terminal.push_back({bd.tbl[u], u});
            } else {
                nonterminal = min(nonterminal, {distance_table[bd.player][u], u});
            }
        }
        int nt = nonterminal.second;
        if (distance_table[bd.player][nt] + 1 > T - bd.total_cost) break;
        op_move(nt);
        op_copy();

        sort(terminal.begin(), terminal.end());

        for (auto tt : terminal) {
            int t = tt.second;
            if (distance_table[bd.player][t] + 2 > T - bd.total_cost) break;
            op_move(t);
            op_copy();
            op_write();
        }
    } while (0);

    // debug2("rulebased end", bd.total_cost);
    return {bd, ops};
}
pair<int, vector<int8_t>> solve() {
    vector<int8_t> ops;
    board_t bd;

    bd.player = 0;
    bd.x = 0;
    bd.total_cost = 0;
    for (int u = 0; u < N2; u++) {
        bd.tbl[u] = INIT_TBL[u];
    }
    tie(bd, ops) = rulebased(bd, ops);

    int score = 0;
    for (int u = 0; u < N2; u++) {
        score += bd.tbl[u];
    }
    return {score, ops};
}
int main() {
    marathon::marathon_init();
    int n, t;
    cin >> n >> t;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> INIT_TBL[r * N + c];
        }
    }
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    distance_table[r * N + c][i * N + j] = abs(r - i) + abs(c - j);
                }
            }
        }
    }
    pair<int, vector<int8_t>> best;
    best.first = -1;
    for (int loop = 0; marathon::now() < 1800; loop++) {
        int s;
        vector<int8_t> ops;
        tie(s, ops) = solve();
        best = max(best, {s, ops});
        if (loop % 100 == 0) debug3(loop, s, best.first);
    }

    output(best.second);

    return 0;
}