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

• 問題: No.5022 XOR Printer
• ユーザー: tnktsyk
• 提出日時: 2025-07-26 15:36:46
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 465 ms / 2,000 ms
• コード長: 7,084 bytes
• コンパイル時間: 2,387 ms
• コンパイル使用メモリ: 213,056 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,648,420,920
• 最終ジャッジ日時: 2025-07-26 15:37:14
• 合計ジャッジ時間: 27,212 ms
• ジャッジサーバーID （参考情報）: judge5 / judge6

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

/*************************************************
 * XOR Printer (yukicoder No.5022)
 * Multi-stage greedy with strict non-degradation:
 *  1. Compute best single-s solution (2^20 exhaustive), build its ops (baseline).
 *  2. Try repeating stages:
 *     - On current board, find best s by 2^20 exhaustive.
 *     - Build diff with XOR basis, generate C list.
 *     - Choose W cells (those gaining with new s).
 *     - If gain>0 AND total ops within T, commit; else stop.
 *  3. Compare final multi-stage score vs baseline. Output better.
 *
 *  Moves only over necessary cells (C/W) with greedy routing to save ops.
 *  Always safe: never outputs worse score than baseline.
 *************************************************/

// ===== XOR Basis (20-bit) with bitset representation =====
struct XorBasis {
    static const int B = 20;
    int v[B];
    bitset<128> used[B];
    XorBasis(){ memset(v,0,sizeof(v)); }
    void add(int x, const bitset<128>& bs){
        bitset<128> c = bs;
        for(int b=B-1;b>=0;--b){
            if(((x>>b)&1)==0) continue;
            if(v[b]==0){ v[b]=x; used[b]=c; return; }
            x ^= v[b];
            c ^= used[b];
        }
    }
    pair<int, bitset<128>> build(int target) const{
        int t=target, made=0; bitset<128> sel; sel.reset();
        for(int b=B-1;b>=0;--b){
            if(((t>>b)&1)==0) continue;
            if(v[b]==0) continue;
            t ^= v[b]; made ^= v[b]; sel ^= used[b];
        }
        return {made, sel};
    }
};

inline ll eval_single(const vector<int>& A, int s){
    ll sum=0; for(int x:A){ int y=x^s; sum += (y>x?y:x); } return sum; }

// Greedy visit order for a set of indices; append opch for each cell visited.
static void visit_cells(int N, int &r, int &c, const vector<int>& ids, vector<char>& ops, char opch){
    if(ids.empty()) return;
    vector<char> used(ids.size(),0);
    for(size_t done=0; done<ids.size(); ++done){
        int best=-1, bestd=1e9;
        for(size_t i=0;i<ids.size();++i){
            if(used[i]) continue;
            int id=ids[i]; int tr=id/N, tc=id%N;
            int d=abs(tr-r)+abs(tc-c);
            if(d<bestd){ bestd=d; best=i; }
        }
        used[best]=1;
        int id=ids[best]; int tr=id/N, tc=id%N;
        while(r<tr){ ops.push_back('D'); ++r; }
        while(r>tr){ ops.push_back('U'); --r; }
        while(c<tc){ ops.push_back('R'); ++c; }
        while(c>tc){ ops.push_back('L'); --c; }
        ops.push_back(opch);
    }
}

// Convert bitset<128> to vector<int> (0..NN-1)
static vector<int> bs_to_vec(const bitset<128>& bs, int NN){
    vector<int> v; v.reserve(NN);
    for(int i=0;i<NN;i++) if(bs.test(i)) v.push_back(i);
    return v;
}

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

    int N,T; if(!(cin>>N>>T)) return 0; // N=10, T=1000
    const int NN = N*N;

    vector<vector<int>> A2(N, vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A2[i][j];

    vector<int> flatA(NN);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) flatA[i*N+j]=A2[i][j];

    // ---------- Baseline single-s ----------
    int bestS_single = 0; ll bestScore_single = -1;
    for(int s=0; s<(1<<20); ++s){
        ll sc = eval_single(flatA, s);
        if(sc > bestScore_single){ bestScore_single=sc; bestS_single=s; }
    }
    // Build ops for baseline later (after we know if multi-stage beats it)

    auto build_baseline_ops = [&](int S)->vector<char>{
        XorBasis B; // basis on original board
        for(int i=0;i<N;i++) for(int j=0;j<N;j++){
            bitset<128> bs; bs.reset(); bs.set(i*N+j);
            B.add(A2[i][j], bs);
        }
        auto [S_real, cells] = B.build(S);
        if(S_real != S){
            ll sc_real = eval_single(flatA, S_real);
            if(sc_real >= bestScore_single){ bestScore_single=sc_real; S=S_real; }
            else { auto tmp=B.build(S); cells = tmp.second; }
        }
        vector<int> Cvec = bs_to_vec(cells, NN);
        vector<int> Wvec; Wvec.reserve(NN);
        for(int id=0; id<NN; ++id){ int a=flatA[id], b=a^S; if(b>a) Wvec.push_back(id); }
        vector<char> ops; ops.reserve(1200);
        int r=0,c=0;
        visit_cells(N,r,c,Cvec,ops,'C');
        visit_cells(N,r,c,Wvec,ops,'W');
        if((int)ops.size()>T) ops.resize(T);
        return ops;
    };

    // ---------- Multi-stage attempt ----------
    vector<int> board = flatA; // current values
    int curS = 0;              // current s
    vector<char> ops_multi;    // operations for multi-stage plan
    int r=0,c=0;               // cursor pos
    ll currentScore = 0; for(int v:board) currentScore += v;

    auto time_start = chrono::steady_clock::now();
    const double TIME_LIMIT = 1.90; // safety

    while(true){
        if((int)ops_multi.size() > T-200) break; // margin
        double t = chrono::duration<double>(chrono::steady_clock::now()-time_start).count();
        if(t > TIME_LIMIT) break;

        // 1) best s on current board (exhaustive)
        int targetS=-1; ll bestGain=0; // gain over currentScore
        for(int s=0; s<(1<<20); ++s){
            ll sum=0; for(int x:board){ int y=x^s; sum += (y>x?y:x); }
            ll g = sum - currentScore;
            if(g > bestGain){ bestGain=g; targetS=s; }
        }
        if(bestGain <= 0) break; // done

        // 2) Build basis on current board, realize diff
        int diff = curS ^ targetS;
        XorBasis B;
        for(int i=0;i<N;i++) for(int j=0;j<N;j++){
            bitset<128> bs; bs.reset(); bs.set(i*N+j);
            B.add(board[i*N+j], bs);
        }
        auto [diffReal, needCbs] = B.build(diff);
        int newS = curS ^ diffReal;

        // 3) choose W cells and compute new score with realizable newS
        vector<int> Wvec; Wvec.reserve(NN);
        ll newScore = 0;
        for(int id=0; id<NN; ++id){
            int a = board[id]; int b = a ^ newS;
            if(b > a){ Wvec.push_back(id); newScore += b; } else newScore += a;
        }
        if(newScore <= currentScore) break; // cannot improve actually

        // Build ops for this stage to check T first
        vector<char> tmp; tmp.reserve(needCbs.count()*6 + Wvec.size()*6 + 10);
        int tr=r, tc=c;
        vector<int> Cvec = bs_to_vec(needCbs, NN);
        visit_cells(N, tr, tc, Cvec, tmp, 'C');
        curS = newS; // after C, we hold newS
        visit_cells(N, tr, tc, Wvec, tmp, 'W');
        // check
        if((int)ops_multi.size() + (int)tmp.size() > T) break;

        // commit
        ops_multi.insert(ops_multi.end(), tmp.begin(), tmp.end());
        r=tr; c=tc; currentScore = newScore;
        for(int id: Wvec) board[id] ^= curS;
    }

    // Compare multi vs baseline
    if(currentScore > bestScore_single){
        // multi-stage better
        if((int)ops_multi.size() > T) ops_multi.resize(T);
        for(char ch: ops_multi) cout<<ch<<'\n';
    }else{
        auto ops_base = build_baseline_ops(bestS_single);
        for(char ch: ops_base) cout<<ch<<'\n';
    }
    return 0;
}