結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 tnktsyk
|
| 提出日時 | 2025-07-26 16:13:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,903 ms / 2,000 ms |
| コード長 | 10,110 bytes |
| コンパイル時間 | 2,653 ms |
| コンパイル使用メモリ | 220,052 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 4,695,387,536 |
| 最終ジャッジ日時 | 2025-07-26 16:14:48 |
| 合計ジャッジ時間 | 97,660 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/****************************************************
* "Try a lot, keep only improvements" framework
* - N=10, T=1000, Ai < 2^20 固定前提。
* - 現在盤面boardと保持中sを持ち、いろんなヒューリスティックで候補sを作成。
* - 各候補ごとに実際の基底でdiffを構成→利得計算→ops/time内なら即採用。
* - 非劣化保証: gain<=0 なら採用しない。
*
* Heuristics order (ループで繰り返し):
* 1) 全体単一s 全探索 (最初の1回だけ)
* 2) ブロックサイズ {5,4,3,2} 全探索 (全ブロック)
* 3) ビットトグル利得最大 (1bitずつ)
* 4) ランダムs候補 (RND_SAMPLES 回)
* 5) ランダム小ブロック (RND_BLOCKS 回、サイズ2〜4)
* これらを時間/手数が切れるまで回す。
*
* ルーティング: 必要セルのみを貪欲巡回。
****************************************************/
// ===== XOR Basis (20-bit) =====
struct XorBasis {
static const int B = 20;
int v[B];
vector<int> mask[B];
XorBasis(){ memset(v,0,sizeof(v)); }
void add(int x, const vector<int>& cells){
vector<int> c = cells;
for(int b=B-1;b>=0;--b){
if(((x>>b)&1)==0) continue;
if(!v[b]){ v[b]=x; mask[b]=c; return; }
x ^= v[b];
vector<int> a = mask[b], res; res.reserve(c.size()+a.size());
sort(c.begin(),c.end()); sort(a.begin(),a.end());
size_t i=0,j=0;
while(i<c.size()||j<a.size()){
if(j==a.size() || (i<c.size() && c[i]<a[j])) res.push_back(c[i++]);
else if(i==c.size() || a[j]<c[i]) res.push_back(a[j++]);
else { ++i; ++j; }
}
c.swap(res);
}
}
pair<int, vector<int>> build(int target) const{
int t=target, made=0; vector<int> sel;
for(int b=B-1;b>=0;--b){
if(((t>>b)&1)==0) continue;
if(!v[b]) continue;
t ^= v[b]; made ^= v[b];
vector<int> a = mask[b], res; res.reserve(sel.size()+a.size());
sort(sel.begin(),sel.end()); sort(a.begin(),a.end());
size_t i=0,j=0;
while(i<sel.size()||j<a.size()){
if(j==a.size() || (i<sel.size() && sel[i]<a[j])) res.push_back(sel[i++]);
else if(i==sel.size() || a[j]<sel[i]) res.push_back(a[j++]);
else { ++i; ++j; }
}
sel.swap(res);
}
return {made, sel};
}
};
inline ll eval_score(const vector<int>& A, int s){
ll sum=0; for(int x:A){ int y=x^s; sum += (y>x?y:x); } return sum; }
static void greedy_visit(int N,int &r,int &c,const vector<int>& ids,vector<char>& ops,char ch){
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 rr=id/N, cc=id%N; int d=abs(rr-r)+abs(cc-c);
if(d<bestd){ bestd=d; best=(int)i; }
}
used[best]=1; int id=ids[best]; int rr=id/N, cc=id%N;
while(r<rr){ ops.push_back('D'); ++r; }
while(r>rr){ ops.push_back('U'); --r; }
while(c<cc){ ops.push_back('R'); ++c; }
while(c>cc){ ops.push_back('L'); --c; }
ops.push_back(ch);
}
}
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 BITS=20, NN=100;
vector<vector<int>> A(N,vector<int>(N));
for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>A[i][j];
vector<int> board(NN); for(int i=0;i<N;i++) for(int j=0;j<N;j++) board[i*N+j]=A[i][j];
vector<char> ops; ops.reserve(5000);
int r=0,c=0; int curS=0;
mt19937 rng(114514);
auto start = chrono::steady_clock::now();
const double TL = 1.90;
auto time_ok=[&](){return chrono::duration<double>(chrono::steady_clock::now()-start).count()<TL;};
auto total_sum=[&](){ ll s=0; for(int v:board) s+=v; return s; };
// apply helper: try targetS, restrict W to idsRestrict (empty => all)
auto try_apply = [&](int targetS, const vector<int>& idsRestrict, bool strict_restrict)->bool{
if(!time_ok()) return false;
ll base = total_sum();
// Build basis on current board
XorBasis B; for(int i=0;i<N;i++)for(int j=0;j<N;j++){int id=i*N+j; B.add(board[id], {id});}
int diff = curS ^ targetS;
auto [diffReal, needC] = B.build(diff);
int newS = curS ^ diffReal;
// decide W cells
vector<int> wCells; wCells.reserve(NN);
ll after=0;
if(idsRestrict.empty()){
for(int id=0; id<NN; ++id){ int a=board[id], b=a^newS; if(b>a){ wCells.push_back(id); after+=b; } else after+=a; }
}else{
vector<char> mark(NN,0); for(int id:idsRestrict) mark[id]=1;
for(int id=0; id<NN; ++id){
int a=board[id], b=a^newS;
if(mark[id]){ // only update inside block
if(b>a){ wCells.push_back(id); after+=b; } else after+=a;
}else{
// outside block: keep as is
after+=a;
if(!strict_restrict) {
// allow outside also if profitable (optional)
if(b>a){ wCells.push_back(id); after-=a; after+=b; }
}
}
}
}
ll gain = after - base;
if(gain<=0) return false;
// simulate ops
vector<char> tmp; tmp.reserve(needC.size()*6 + wCells.size()*6 + 10);
int tr=r, tc=c;
greedy_visit(N,tr,tc,needC,tmp,'C');
greedy_visit(N,tr,tc,wCells,tmp,'W');
if((int)ops.size() + (int)tmp.size() > T) return false;
// commit
ops.insert(ops.end(), tmp.begin(), tmp.end());
r=tr; c=tc; curS=newS;
for(int id:wCells) board[id]^=curS;
return true;
};
// ---- 0) global best single s (once) ----
{
ll base = total_sum();
int bestS=0; ll bestG=0;
for(int s=0;s<(1<<BITS);++s){
ll tot=0; for(int x:board){ int y=x^s; tot+=(y>x?y:x);} ll g=tot-base; if(g>bestG){bestG=g; bestS=s;}
}
if(bestG>0) try_apply(bestS, {}, true);
}
// heuristic loop
const int RND_SAMPLES = 2000;
const int RND_BLOCKS = 800;
vector<int> blockSizes = {5,4,3,2};
bool improved=true;
while(improved && time_ok() && (int)ops.size() <= T-200){
improved=false;
// 1) block sizes deterministic scan
for(int sz: blockSizes){
if(!time_ok() || (int)ops.size()>T-200) break;
for(int rs=0; rs<N; rs+=sz){
int re=min(N,rs+sz);
for(int cs=0; cs<N; cs+=sz){
int ce=min(N,cs+sz);
vector<int> ids; ids.reserve(sz*sz);
for(int i=rs;i<re;i++) for(int j=cs;j<ce;j++) ids.push_back(i*N+j);
// exhaust best s for this block
// compute current block sum
ll blkBase=0; for(int id:ids) blkBase+=board[id];
int bs=-1; ll bg=0;
for(int s=0;s<(1<<BITS);++s){
ll tot=0; for(int id:ids){ int a=board[id]; int b=a^s; tot+=(b>a?b:a);} ll g=tot-blkBase; if(g>bg){bg=g; bs=s;}
}
if(bg<=0) continue;
if(try_apply(bs, ids, true)) improved=true;
}
}
}
if(!time_ok() || (int)ops.size()>T-200) break;
// 2) bit-greedy loop (one pass). Repeat outer while for more.
for(int loop=0; loop<20 && time_ok() && (int)ops.size()<=T-200; ++loop){
ll base=total_sum();
// build basis once
XorBasis B; for(int i=0;i<N;i++) for(int j=0;j<N;j++){ int idx=i*N+j; B.add(board[idx], {idx}); }
int bestBit=-1; ll gainBest=0; int bestNewS=curS; vector<int> bestNeedC, bestW;
for(int b=BITS-1;b>=0;b--){
int diff = 1<<b;
auto [diffReal, needC] = B.build(diff);
int newS = curS ^ diffReal;
ll g=0; vector<int> wCells;
for(int id=0; id<NN; ++id){ int a=board[id], bval=a^newS; if(bval>a){ g+= (bval-a); wCells.push_back(id);} }
if(g>gainBest || (g==gainBest && b>bestBit)){
gainBest=g; bestBit=b; bestNewS=newS; bestNeedC=needC; bestW=wCells;
}
}
if(gainBest<=0) break;
vector<char> tmp; tmp.reserve(bestNeedC.size()*6 + bestW.size()*6 + 10);
int tr=r, tc=c;
greedy_visit(N,tr,tc,bestNeedC,tmp,'C');
greedy_visit(N,tr,tc,bestW,tmp,'W');
if((int)ops.size()+ (int)tmp.size() > T) break;
ops.insert(ops.end(), tmp.begin(), tmp.end());
r=tr; c=tc; curS=bestNewS;
for(int id:bestW) board[id]^=curS;
improved=true;
}
if(!time_ok() || (int)ops.size()>T-200) break;
// 3) random s full-board
for(int k=0;k<RND_SAMPLES && time_ok() && (int)ops.size()<=T-200; ++k){
int s = rng() & ((1<<BITS)-1);
if(try_apply(s, {}, true)) improved=true;
}
if(!time_ok() || (int)ops.size()>T-200) break;
// 4) random small blocks with random s subset (cheap approx)
for(int k=0;k<RND_BLOCKS && time_ok() && (int)ops.size()<=T-200; ++k){
int sz = 2 + (rng()%3); // 2..4
int rs = rng()% (N-sz+1);
int cs = rng()% (N-sz+1);
vector<int> ids;
for(int i=rs;i<rs+sz;i++) for(int j=cs;j<cs+sz;j++) ids.push_back(i*N+j);
int s = rng() & ((1<<BITS)-1);
if(try_apply(s, ids, true)) improved=true;
}
}
if((int)ops.size()>T) ops.resize(T);
for(char ch:ops) cout<<ch<<'\n';
return 0;
}