結果
問題 |
No.5022 XOR Printer
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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'; }