結果

問題 No.5022 XOR Printer
コンテスト
ユーザー K2
提出日時 2025-07-26 16:18:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,989 ms / 2,000 ms
コード長 6,269 bytes
コンパイル時間 3,604 ms
コンパイル使用メモリ 295,108 KB
実行使用メモリ 7,716 KB
スコア 5,055,143,936
最終ジャッジ日時 2025-07-26 16:19:47
合計ジャッジ時間 106,641 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

/* --------------------------------------------------------------------------
 * Grid XOR Maximisation – 2‑phase solver (Random search → SA)
 * 2025‑07‑26 update:
 *   • pos 長さ固定 (MAX_CHOOSE)
 *   • ルート生成を “常にマンハッタン最短経路” に変更
 *     ‑ 各フェーズごとに "今いるマス→最近傍の書き込み対象" を
 *       貪欲に訪問して W
 *     ‑ コピーセルへの移動もマンハッタン一直線
 *   • ヘビ走査を廃止し、移動手数を大幅削減
 * --------------------------------------------------------------------------
 */

// ---------- utilities ------------------------------------------------------
struct Timer { using Clock = chrono::high_resolution_clock; chrono::time_point<Clock> st{Clock::now()}; double elapsed() const { return chrono::duration<double>(Clock::now() - st).count(); } };

// ---------- constants ------------------------------------------------------
constexpr int N = 10;
constexpr int OP_LIMIT = 1000;
constexpr int MAX_CHOOSE = 15;
constexpr double RAND_PHASE = 1.00; // s
constexpr double TL = 1.98;         // s total
using Board = array<array<uint32_t, N>, N>;

// ---------- state ----------------------------------------------------------
struct State {
    array<int, MAX_CHOOSE> pos; // copy cells (0..99)
    vector<uint32_t> s;         // prefix XOR size MAX_CHOOSE+1
    bitset<100> mask;           // copy mask
    long long score = -1;
};

// ---------- evaluation helpers --------------------------------------------
inline bitset<100> make_mask(const array<int, MAX_CHOOSE>& pos) {
    bitset<100> bs; for (int v : pos) bs.set(v); return bs; }

inline long long eval_board(const vector<uint32_t>& s,const Board& A,const bitset<100>& copyMask){ long long sum=0; for(int idx=0;idx<100;++idx){ int i=idx/ N,j=idx%N; if(copyMask.test(idx)){ sum+=A[i][j]; }else{ uint32_t best=A[i][j]; for(uint32_t v:s){ uint32_t cand=A[i][j]^v; if(cand>best) best=cand;} sum+=best; } } return sum; }

inline void rebuild_prefXor(State& st,const Board& A){ st.s.resize(MAX_CHOOSE+1); st.s[0]=0; for(int k=0;k<MAX_CHOOSE;++k){ int idx=st.pos[k]; st.s[k+1]=st.s[k]^A[idx/ N][idx%N]; } st.mask=make_mask(st.pos);} 

// ---------- neighbour generator -------------------------------------------
struct Mutator{ mt19937 rng; uniform_real_distribution<double> uni{0.0,1.0}; uniform_int_distribution<int> cellDist{0,99}; explicit Mutator(uint32_t seed):rng(seed){}
    array<int,MAX_CHOOSE> random_pos(){ array<int,MAX_CHOOSE> v{}; int f=0; while(f<MAX_CHOOSE){ int x=cellDist(rng); bool dup=false; for(int i=0;i<f;++i) if(v[i]==x){dup=true;break;} if(!dup) v[f++]=x;} return v; }
    void mutate(array<int,MAX_CHOOSE>& pos){ if(uni(rng)<0.5){ // swap
            uniform_int_distribution<int>d(0,MAX_CHOOSE-1); int a=d(rng),b=d(rng); if(a!=b) swap(pos[a],pos[b]);
        }else{ // replace
            uniform_int_distribution<int>d(0,MAX_CHOOSE-1); int idx=d(rng); for(int t=0;t<20;++t){ int x=cellDist(rng); bool dup=false; for(int v:pos) if(v==x){dup=true;break;} if(!dup){pos[idx]=x;break;}} } }
};

// ---------- random + SA ----------------------------------------------------
State random_search(const Board&A,Timer&timer,Mutator&mut){ State best; best.score=-1; while(timer.elapsed()<RAND_PHASE){ State st; st.pos=mut.random_pos(); rebuild_prefXor(st,A); st.score=eval_board(st.s,A,st.mask); if(st.score>best.score) best=st;} return best; }

State simulated_annealing(const Board&A,State init,Timer&timer,Mutator&mut){ State cur=init,best=cur; constexpr double T0=1e5,Tend=1.0; while(true){ double t=timer.elapsed(); if(t>=TL) break; double temp=T0*pow(Tend/T0,(t-RAND_PHASE)/(TL-RAND_PHASE)); State nxt=cur; mut.mutate(nxt.pos); rebuild_prefXor(nxt,A); nxt.score=eval_board(nxt.s,A,nxt.mask); long long diff=nxt.score-cur.score; if(diff>=0||mut.uni(mut.rng)<exp(double(diff)/temp)){ cur=nxt; if(cur.score>best.score) best=cur; } } return best; }

// ---------- shortest‑path based operation builder --------------------------
vector<char> build_ops(const State& best,const Board&A){ const vector<uint32_t>&pref=best.s; const bitset<100>&mask=best.mask;
    // Prepare write target lists per phase (1..MAX_CHOOSE)
    array<vector<pair<int,int>>,MAX_CHOOSE+1> targets; // index by phase
    for(int idx=0;idx<100;++idx){ if(mask.test(idx)) continue; int i=idx/ N,j=idx%N; int best_k=0; uint32_t best_val=A[i][j]; for(int k=1;k<=MAX_CHOOSE;++k){ uint32_t cand=A[i][j]^pref[k]; if(cand>best_val){best_val=cand; best_k=k;} } targets[best_k].push_back({i,j}); }

    vector<char> ops; ops.reserve(OP_LIMIT);
    auto push=[&](char c){  ops.push_back(c); };
    auto move_line=[&](int& cx,int& cy,int tx,int ty){ // Manhattan path (vertical first)
        while(cx<tx){ push('D'); ++cx; }
        while(cx>tx){ push('U'); --cx; }
        while(cy<ty){ push('R'); ++cy; }
        while(cy>ty){ push('L'); --cy; }
    };

    int cx=0,cy=0; // current pos
    // Phases 0..MAX_CHOOSE (phase0 only move to first copy cell)
    for(int phase=0;phase<=MAX_CHOOSE;++phase){ if(phase>0){ auto&vec=targets[phase]; while(!vec.empty()){ // nearest greedy
                int bestIdx=0,bestDist=1e9; for(int i=0;i<(int)vec.size();++i){ int d=abs(cx-vec[i].first)+abs(cy-vec[i].second); if(d<bestDist){bestDist=d; bestIdx=i;} }
                auto [tx,ty]=vec[bestIdx]; move_line(cx,cy,tx,ty); push('W'); vec.erase(vec.begin()+bestIdx);
            }
            if(phase==MAX_CHOOSE) break; // no next copy cell needed
        }
        // move to next copy cell and C
        int tgt=best.pos[phase]; int tx=tgt/ N,ty=tgt%N; move_line(cx,cy,tx,ty); push('C');
    }

    // if((int)ops.size()>OP_LIMIT) ops.resize(OP_LIMIT);
    return ops; }

// ---------- main -----------------------------------------------------------
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n_in,t_in; if(!(cin>>n_in>>t_in)) return 0; Board A{}; for(int i=0;i<N;++i) for(int j=0;j<N;++j) cin>>A[i][j]; Timer timer; Mutator mut(123456789u);
    State init=random_search(A,timer,mut);
    State best=simulated_annealing(A,init,timer,mut);
    auto ops=build_ops(best,A);
    for(char c:ops) cout<<c<<'\n'; }
0