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

• 問題: No.5022 XOR Printer
• ユーザー: Keroru
• 提出日時: 2025-07-26 16:34:48
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,923 ms / 2,000 ms
• コード長: 5,764 bytes
• コンパイル時間: 3,548 ms
• コンパイル使用メモリ: 297,156 KB
• 実行使用メモリ: 7,720 KB
• スコア: 5,169,446,165
• 最終ジャッジ日時: 2025-07-26 16:36:32
• 合計ジャッジ時間: 103,191 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

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

ソースコード

// Baseline Score: 1518598366
// Improved Score: 1542584325
// Improvement: 23985959
// XOR Printer greedy solver prepared for beam search.
// Randomly allocate 7-13 turns to each of the 100 cells and traverse them in
// snake order. For each cell, greedily select up to two assist cells within
// distance d(=3) whose total cost does not exceed the allocated budget. Repeat
// the whole process while time allows and output the best sequence found using
// newline separated operations.

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

struct Input {
    int N, T;
    vector<vector<long long>> grid;
};

struct Pos {int r, c;};

inline int dist(const Pos& a, const Pos& b){
    return abs(a.r - b.r) + abs(a.c - b.c);
}

struct State {
    int N, limit;
    vector<long long> grid; // flattened N*N
    Pos cur{0,0};
    long long s = 0;
    long long score = 0;
    string ops;

    int idx(int r,int c) const { return r*N + c; }
};

void move_to(State& st, Pos to){
    while(st.cur.r < to.r){ st.ops += 'D'; st.cur.r++; }
    while(st.cur.r > to.r){ st.ops += 'U'; st.cur.r--; }
    while(st.cur.c < to.c){ st.ops += 'R'; st.cur.c++; }
    while(st.cur.c > to.c){ st.ops += 'L'; st.cur.c--; }
}

void apply_C(State& st){
    st.s ^= st.grid[st.idx(st.cur.r, st.cur.c)];
    st.ops += 'C';
}

void apply_W(State& st){
    int id = st.idx(st.cur.r, st.cur.c);
    st.score -= st.grid[id];
    st.grid[id] ^= st.s;
    st.score += st.grid[id];
    st.ops += 'W';
}

pair<long long,string> run_once(const Input& in, mt19937& rng){
    const int D = 4;
    State st;
    st.N = in.N;
    st.limit = min(in.T, 1000);
    st.grid.resize(in.N*in.N);
    for(int i=0;i<in.N;i++) for(int j=0;j<in.N;j++){
        st.grid[st.idx(i,j)] = in.grid[i][j];
        st.score += in.grid[i][j];
    }
    st.ops.reserve(st.limit);

    int cells = in.N * in.N;
    vector<int> budget(cells, 7);
    int leftover = st.limit - 7*cells;
    if(leftover < 0) leftover = 0;
    uniform_int_distribution<int> distCell(0, cells-1);
    while(leftover > 0){
        int id = distCell(rng);
        if(budget[id] < 13){
            budget[id]++; leftover--; }
    }

    vector<Pos> path; path.reserve(cells);
    for(int r=0;r<in.N;r++){
        if(r%2==0){
            for(int c=0;c<in.N;c++) path.push_back({r,c});
        }else{
            for(int c=in.N-1;c>=0;c--) path.push_back({r,c});
        }
    }

    auto inside=[&](int r,int c){return 0<=r && r<in.N && 0<=c && c<in.N;};

    for(size_t idx=0; idx<path.size(); ++idx){
        Pos x = path[idx];
        int mvTo = dist(st.cur, x);
        if((int)st.ops.size() + mvTo + 1 > st.limit) break; // need at least W
        move_to(st, x);

        int xid = st.idx(x.r, x.c);
        int cellRemain = min(budget[idx], st.limit - (int)st.ops.size())+1;
        long long bestVal = st.grid[xid] ^ st.s; // no assist
        int bestType = 0; // 0 none,1 one,2 two
        Pos bestA,bestB; int bestCost=1; long long bestS=st.s;

        vector<Pos> cells;
        for(int dr=-D; dr<=D; dr++)
            for(int dc=-D; dc<=D; dc++)
                if(abs(dr)+abs(dc)<=D && inside(x.r+dr,x.c+dc))
                    cells.push_back({x.r+dr,x.c+dc});

        for(auto a: cells){
            int c1 = dist(x,a)*2 + 2 + 0; // includes C and W
            if(c1 > cellRemain) continue;
            long long ns = st.s ^ st.grid[st.idx(a.r,a.c)];
            long long val = st.grid[xid] ^ ns;
            if(val > bestVal){
                bestVal = val; bestType=1; bestA=a; bestCost=c1; bestS=ns;
            }
        }

        for(size_t i=0;i<cells.size();i++) for(size_t j=i+1;j<cells.size();j++){
            Pos a=cells[i], b=cells[j];
            int c2 = dist(x,a) + dist(a,b) + dist(b,x) + 3;
            if(c2 > cellRemain) continue;
            long long ns = st.s ^ st.grid[st.idx(a.r,a.c)] ^ st.grid[st.idx(b.r,b.c)];
            long long val = st.grid[xid] ^ ns;
            if(val > bestVal){
                bestVal = val; bestType=2; bestA=a; bestB=b; bestCost=c2; bestS=ns;
            }
        }

        if(bestType==0){
            apply_W(st); // cost 1 already ensured
        }else if((int)st.ops.size() + bestCost <= st.limit){
            if(bestType==1){
                move_to(st,bestA); apply_C(st);
                move_to(st,x); apply_W(st);
            }else{
                move_to(st,bestA); apply_C(st);
                move_to(st,bestB); apply_C(st);
                move_to(st,x); apply_W(st);
            }
            st.s = bestS;
        }

        if(idx+1 >= path.size()) break;
        Pos nxt = path[idx+1];
        int mv = dist(st.cur, nxt);
        if((int)st.ops.size()+mv > st.limit) break;
        move_to(st, nxt);
    }

    string out; out.reserve(st.ops.size()*2);
    for(char c: st.ops){ out.push_back(c); out.push_back('\n'); }
    if(!out.empty()) out.pop_back();
    return {st.score, out};
}

pair<long long,string> solve(const Input& in){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto start = chrono::steady_clock::now();
    long long bestScore = -1; string bestOps; int loops=0;
    do{
        auto [sc,ops] = run_once(in, rng);
        if(sc > bestScore){ bestScore = sc; bestOps = std::move(ops); }
        loops++;
    }while(chrono::duration<double>(chrono::steady_clock::now()-start).count() < 1.92);
    cerr << bestScore << "\n";
    cerr << loops << "\n";
    return {bestScore, bestOps};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Input in; if(!(cin>>in.N>>in.T)) return 0; in.grid.assign(in.N, vector<long long>(in.N));
    for(int i=0;i<in.N;i++) for(int j=0;j<in.N;j++) cin>>in.grid[i][j];
    auto [score, out] = solve(in);
    cout<<out<<"\n"; cerr<<score<<"\n";
    return 0;
}