結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2025-07-26 14:42:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,168 ms / 2,000 ms |
| コード長 | 8,395 bytes |
| コンパイル時間 | 3,646 ms |
| コンパイル使用メモリ | 298,576 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,074,959,413 |
| 最終ジャッジ日時 | 2025-07-26 14:43:19 |
| 合計ジャッジ時間 | 54,636 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// greedy_xor_v10.cpp
// ------------------------------------------------------------------
// ポイント
// * 800 000‑899 999 を “80 万台”,
// 900 000‑999 999 を “90 万台” と定義。
// * それぞれ **最終的に 2 マスは残す** という制約を追加。
// ‑ 初期状態でそのレンジに 2 未満しか無ければ制約なし。
// ‑ 残数 (= まだレンジ内にあるマス数) が reserve(=2) 以下に
// なったら、そのレンジのセルは以後スキップ(改善対象にしない)。
// * 改善手ゼロなら “ブロック” は従来通り。
// * その他手数・コピー 1/2/3 評価ロジックは v9 と同じ。
// ------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_COST12 = 30;
constexpr int MAX_COST3 = 45;
constexpr int LOW80 = 800000, HIGH80 = 899999;
constexpr int LOW90 = 900000, HIGH90 = 999999;
struct Plan{
double ratio=-1; int gain=0,cost=0; char type=0;
int ar=0,ac=0,b1r=0,b1c=0,b2r=0,b2c=0,b3r=0,b3c=0;
};
inline int manh(int r1,int c1,int r2,int c2){
return abs(r1-r2)+abs(c1-c2);
}
void addMoves(int r1,int c1,int r2,int c2,vector<char>& ops){
if(r2>r1) ops.insert(ops.end(),r2-r1,'D'); else ops.insert(ops.end(),r1-r2,'U');
if(c2>c1) ops.insert(ops.end(),c2-c1,'R'); else ops.insert(ops.end(),c1-c2,'L');
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N,T; if(!(cin>>N>>T)) return 0;
vector<vector<int>> A(N,vector<int>(N));
for(auto& row:A) for(int& x:row) cin>>x;
vector<pair<int,int>> cells;
cells.reserve(N*N);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) cells.emplace_back(i,j);
// --- 初期レンジ内セル数 ---
int init80=0, init90=0;
for(auto [i,j]:cells){
int v=A[i][j];
if(LOW80<=v && v<=HIGH80) ++init80;
else if(LOW90<=v && v<=HIGH90) ++init90;
}
const int reserve80 = (init80>=2 ? 2 : 0);
const int reserve90 = (init90>=2 ? 2 : 0);
int remain80 = init80, remain90 = init90;
vector<vector<char>> blocked(N,vector<char>(N,0));
int r=0,c=0,s=0;
vector<char> ops;
int step=1;
auto in80=[&](int v){return LOW80<=v && v<=HIGH80;};
auto in90=[&](int v){return LOW90<=v && v<=HIGH90;};
while(true){
// ----- choose a -----
int ar=-1,ac=-1,min_val=INT_MAX;
// phase 1: 80/90 万レンジ優先（残数 > reserve）
auto try_pick=[&](int low,int high,int remain,int reserve)->bool{
bool found=false;
for(auto [i,j]:cells){
if(blocked[i][j]) continue;
int v=A[i][j];
if(v<low||v>high) continue;
if(remain<=reserve) continue; // 残すべき数を下回るので不可
if(v<min_val){ min_val=v; ar=i; ac=j; found=true;}
}
return found;
};
bool picked = try_pick(LOW80,HIGH80,remain80,reserve80)
|| try_pick(LOW90,HIGH90,remain90,reserve90);
// phase 2: 全体最小値
if(!picked){
for(auto [i,j]:cells){
if(blocked[i][j]) continue;
int v=A[i][j];
if(v<min_val){ min_val=v; ar=i; ac=j; picked=true; }
}
}
if(!picked) break; // 全ブロック済み
int a_val=A[ar][ac];
Plan best; best.ar=ar; best.ac=ac;
auto skip_by_reserve=[&](int i,int j)->bool{
int v=A[i][j];
if(in80(v) && remain80<=reserve80) return true;
if(in90(v) && remain90<=reserve90) return true;
return false;
};
// ---------- 1‑copy ----------
for(auto [br,bc]:cells){
if(br==ar&&bc==ac) continue;
if(skip_by_reserve(br,bc)) continue;
int cost=manh(r,c,br,bc)+1+manh(br,bc,ar,ac)+1;
if(cost>MAX_COST12 || (int)ops.size()+cost> T) continue;
int gain=(a_val ^ (s ^ A[br][bc]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'1',ar,ac,br,bc};
}
// ---------- 2‑copy ----------
for(auto [b1r,b1c]:cells){
if(b1r==ar&&b1c==ac) continue;
if(skip_by_reserve(b1r,b1c)) continue;
for(auto [b2r,b2c]:cells){
if((b2r==ar&&b2c==ac)||(b2r==b1r&&b2c==b1c)) continue;
if(skip_by_reserve(b2r,b2c)) continue;
int cost=manh(r,c,b1r,b1c)+1+manh(b1r,b1c,b2r,b2c)+1+manh(b2r,b2c,ar,ac)+1;
if(cost>MAX_COST12 || (int)ops.size()+cost> T) continue;
int gain=(a_val ^ (s ^ A[b1r][b1c] ^ A[b2r][b2c]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'2',ar,ac,b1r,b1c,b2r,b2c};
}
}
// ---------- 3‑copy ----------
for(auto [b1r,b1c]:cells){
if(b1r==ar&&b1c==ac) continue;
if(skip_by_reserve(b1r,b1c)) continue;
for(auto [b2r,b2c]:cells){
if((b2r==ar&&b2c==ac)||(b2r==b1r&&b2c==b1c)) continue;
if(skip_by_reserve(b2r,b2c)) continue;
for(auto [b3r,b3c]:cells){
if(b3r==ar&&b3c==ac) continue;
if((b3r==b1r&&b3c==b1c)||(b3r==b2r&&b3c==b2c)) continue;
if(skip_by_reserve(b3r,b3c)) continue;
int cost=manh(r,c,b1r,b1c)+1+
manh(b1r,b1c,b2r,b2c)+1+
manh(b2r,b2c,b3r,b3c)+1+
manh(b3r,b3c,ar,ac)+1;
if(cost>MAX_COST3 || (int)ops.size()+cost> T) continue;
int gain=(a_val ^ (s ^ A[b1r][b1c] ^ A[b2r][b2c] ^ A[b3r][b3c]))-a_val;
if(gain<=0) continue;
double ratio=(double)gain/cost;
if(ratio>best.ratio) best={ratio,gain,cost,'3',ar,ac,b1r,b1c,b2r,b2c,b3r,b3c};
}
}
}
// --- 改善手無し → ブロックして continue ---
if(best.ratio<0){
blocked[ar][ac]=1;
continue;
}
// --- 残数更新 (a は必ず書き換わる) ---
if(in80(a_val)) --remain80;
else if(in90(a_val)) --remain90;
auto after_write=[&](int oldv,int newv){
if(in80(oldv) && !in80(newv)) --remain80;
else if(!in80(oldv) && in80(newv)) ++remain80;
if(in90(oldv) && !in90(newv)) --remain90;
else if(!in90(oldv) && in90(newv)) ++remain90;
};
// ---------- 実行 ----------
if(best.type=='1'){
int vb=A[best.b1r][best.b1c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s ^= vb; r=best.b1r; c=best.b1c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int oldA=A[ar][ac]; A[ar][ac]^=s;
after_write(oldA,A[ar][ac]);
r=ar; c=ac;
}else if(best.type=='2'){
int vb1=A[best.b1r][best.b1c], vb2=A[best.b2r][best.b2c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s ^= vb1; r=best.b1r; c=best.b1c;
addMoves(r,c,best.b2r,best.b2c,ops); ops.push_back('C');
s ^= vb2; r=best.b2r; c=best.b2c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int oldA=A[ar][ac]; A[ar][ac]^=s;
after_write(oldA,A[ar][ac]);
r=ar; c=ac;
}else{
int vb1=A[best.b1r][best.b1c], vb2=A[best.b2r][best.b2c], vb3=A[best.b3r][best.b3c];
addMoves(r,c,best.b1r,best.b1c,ops); ops.push_back('C');
s ^= vb1; r=best.b1r; c=best.b1c;
addMoves(r,c,best.b2r,best.b2c,ops); ops.push_back('C');
s ^= vb2; r=best.b2r; c=best.b2c;
addMoves(r,c,best.b3r,best.b3c,ops); ops.push_back('C');
s ^= vb3; r=best.b3r; c=best.b3c;
addMoves(r,c,ar,ac,ops); ops.push_back('W');
int oldA=A[ar][ac]; A[ar][ac]^=s;
after_write(oldA,A[ar][ac]);
r=ar; c=ac;
}
++step;
}
for(char ch:ops) cout<<ch<<'\n';
return 0;
}