結果
| 問題 | No.5025 Forest Fire |
| コンテスト | |
| ユーザー |
 Shki
|
| 提出日時 | 2026-10-20 12:30:32 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,459 ms / 2,000 ms |
| + 865µs | |
| コード長 | 20,465 bytes |
| 記録 | |
| コンパイル時間 | 4,431 ms |
| コンパイル使用メモリ | 391,652 KB |
| 実行使用メモリ | 9,928 KB |
| スコア | 158,969,697 |
| 最終ジャッジ日時 | 2026-10-24 14:37:39 |
| 合計ジャッジ時間 | 134,654 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / <nil> |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// C++17, no external libraries. N = 50, K = 100.
// This solver minimizes the expected squared connected component sizes.
using ll = long long;
using Clock = chrono::steady_clock;
struct Random {
uint64_t state;
explicit Random(uint64_t s) : state(s) {}
uint64_t next() {
uint64_t z = (state += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
int integer(int n) { return (int)(next() % (uint64_t)n); }
double real() { return (next() >> 11) * 0x1.0p-53; }
};
class Solver {
static constexpr int NS = 192;
int N, K, V;
bool sparseEnough = false;
vector<int> d, trees;
vector<array<int,4>> adj;
vector<uint8_t> degree;
vector<vector<uint8_t>> dry;
Random rnd;
Clock::time_point start;
const double TIME_LIMIT = 1.50; // Leave margin for slower judges.
vector<int> tin, low, sub, separateSum, separateSq, dfsOrder;
int timer = 0;
const vector<uint8_t>* currentCut = nullptr;
const vector<uint8_t>* currentDry = nullptr;
vector<int> mark, queueBuffer, comp, sizes;
int stamp = 0;
double elapsed() const {
return chrono::duration<double>(Clock::now() - start).count();
}
bool timeOkay(double deadline) const { return elapsed() < deadline; }
ll evalOne(const vector<uint8_t>& cut, const vector<uint8_t>& sample) {
if (++stamp == INT_MAX) { fill(mark.begin(), mark.end(), 0); stamp = 1; }
ll result = 0;
for (int root = 0; root < V; ++root) {
if (!sample[root] || cut[root] || mark[root] == stamp) continue;
int h = 0, t = 1;
queueBuffer[0] = root;
mark[root] = stamp;
while (h < t) {
int u = queueBuffer[h++];
for (int z = 0; z < degree[u]; ++z) {
int w = adj[u][z];
if (sample[w] && !cut[w] && mark[w] != stamp) {
mark[w] = stamp;
queueBuffer[t++] = w;
}
}
}
result += (ll)t*t;
}
return result;
}
ll evaluate(const vector<uint8_t>& cut, int from, int count) {
ll val = 0;
for (int s = from; s < from + count; ++s) val += evalOne(cut, dry[s]);
return val;
}
void dfs(int u, int parent) {
tin[u] = low[u] = timer++;
sub[u] = 1;
separateSum[u] = separateSq[u] = 0;
dfsOrder.push_back(u);
for (int z = 0; z < degree[u]; ++z) {
int v = adj[u][z];
if ((*currentCut)[v] || !(*currentDry)[v]) continue;
if (tin[v] == -1) {
dfs(v, u);
sub[u] += sub[v];
low[u] = min(low[u], low[v]);
if (low[v] >= tin[u]) {
separateSum[u] += sub[v];
separateSq[u] += sub[v]*sub[v];
}
} else if (v != parent) {
low[u] = min(low[u], tin[v]);
}
}
}
void removalGains(const vector<uint8_t>& cut, int S, vector<ll>& gain) {
fill(gain.begin(), gain.end(), 0);
currentCut = &cut;
for (int s = 0; s < S; ++s) {
currentDry = &dry[s];
fill(tin.begin(), tin.end(), -1);
dfsOrder.clear();
timer = 0;
for (int r = 0; r < V; ++r) {
if (cut[r] || !dry[s][r] || tin[r] != -1) continue;
int first = (int)dfsOrder.size();
dfs(r, -1);
int componentSize = (int)dfsOrder.size() - first;
int totalSq = componentSize*componentSize;
for (int i = first; i < (int)dfsOrder.size(); ++i) {
int u = dfsOrder[i];
int leftover = componentSize - 1 - separateSum[u];
gain[u] += (ll)totalSq - separateSq[u] - leftover*leftover;
}
}
}
}
void restoreCosts(const vector<uint8_t>& cut, int S, vector<ll>& cost) {
fill(cost.begin(), cost.end(), 0LL);
for (int s = 0; s < S; ++s) {
fill(comp.begin(), comp.end(), -1);
sizes.clear();
for (int r = 0; r < V; ++r) {
if (cut[r] || !dry[s][r] || comp[r] != -1) continue;
int id = (int)sizes.size();
int h = 0, t = 1;
queueBuffer[0] = r;
comp[r] = id;
while (h < t) {
int u = queueBuffer[h++];
for (int z = 0; z < degree[u]; ++z) {
int w = adj[u][z];
if (!cut[w] && dry[s][w] && comp[w] == -1) {
comp[w] = id;
queueBuffer[t++] = w;
}
}
}
sizes.push_back(t);
}
for (int v : trees) {
if (!cut[v] || !dry[s][v]) continue;
int uniqueIds[4], count = 0;
ll joined = 1, previous = 0;
for (int z = 0; z < degree[v]; ++z) {
int id = comp[adj[v][z]];
if (id == -1) continue;
bool duplicate = false;
for (int j = 0; j < count; ++j) duplicate |= (uniqueIds[j] == id);
if (duplicate) continue;
uniqueIds[count++] = id;
ll q = sizes[id];
joined += q;
previous += q*q;
}
cost[v] += joined*joined - previous;
}
}
}
int numberCut(const vector<uint8_t>& cut) const {
int c = 0;
for (int v : trees) c += cut[v];
return c;
}
void greedyComplete(vector<uint8_t>& cut, int samplesCount, double deadline) {
vector<ll> gain(V);
int count = numberCut(cut);
while (count < K && timeOkay(deadline)) {
removalGains(cut, samplesCount, gain);
ll bestVal = -1;
int bestVertex = -1;
for (int v : trees) {
if (!cut[v] && gain[v] > bestVal) {
bestVal = gain[v];
bestVertex = v;
}
}
if (bestVertex < 0) break;
cut[bestVertex] = 1;
++count;
}
}
// Cheap single pass to fill a geometric candidate to exactly K cuts.
void fillOnce(vector<uint8_t>& cut) {
if (numberCut(cut) >= K) return;
vector<ll> gains(V);
removalGains(cut, 12, gains);
vector<int> remaining;
for (int v : trees) if (!cut[v]) remaining.push_back(v);
sort(remaining.begin(), remaining.end(), [&](int a, int b) {
return gains[a] > gains[b];
});
int current = numberCut(cut);
for (int v : remaining) {
if (current >= K) break;
cut[v] = 1;
++current;
}
}
// Water-aware thin blocking barriers. The resulting path can bend.
vector<int> getBarrier(bool horizontal, int target, int seed) {
const int INF = 1000000000;
vector<int> dp(V, INF), parent(V, -1);
auto at = [&](int progress, int pos) {
return horizontal ? pos*N + progress : progress*N + pos;
};
for (int pos = 0; pos < N; ++pos) {
int v = at(0, pos);
dp[pos] = 500*!!d[v] + 6*d[v] + 9*abs(pos-target);
}
for (int x = 1; x < N; ++x) {
for (int p = 0; p < N; ++p) {
int best = INF, idx = -1;
for (int delta = -1; delta <= 1; ++delta) {
int prev = p+delta;
if (prev < 0 || prev >= N) continue;
int trial = dp[(x-1)*N+prev];
if (trial < best) { best = trial; idx = prev; }
}
int v = at(x,p);
int waviness = (seed&1) ? 5 : 12;
dp[x*N+p] = best + 500*!!d[v] + 6*d[v] + waviness*abs(p-target);
parent[x*N+p] = idx;
}
}
int p = 0, best = INF;
for (int j = 0; j < N; ++j) {
int score = dp[(N-1)*N+j] + 9*abs(j-target);
if (score < best) best = score, p = j;
}
vector<int> result;
result.reserve(N);
for (int x = N-1; x >= 0; --x) {
result.push_back(at(x,p));
if (x) p = parent[x*N+p];
}
return result;
}
vector<uint8_t> makeCut(const vector<int>& a, const vector<int>& b) {
vector<uint8_t> cut(V, 0);
for (int v : a) if (d[v]) cut[v] = 1;
for (int v : b) if (d[v]) cut[v] = 1;
return cut;
}
int swapSize(double progress) {
int maxK = min({7,K,(int)trees.size()-K});
if (maxK == 0) return 0;
double decay = 1.0 + 1.4*progress, sum = 0;
double weight[8];
for (int i = 1; i <= maxK; ++i) {
weight[i] = 0.96*exp(-decay*(i-1)) + 0.04;
sum += weight[i];
}
double r = rnd.real()*sum;
for (int i = 1; i <= maxK; ++i) {
r -= weight[i];
if (r < 0) return i;
}
return maxK;
}
// Every successful neighbor retains exactly the same number of cuts.
bool propose(vector<uint8_t>& out, const vector<uint8_t>& cut,
const vector<int>& cutList, const vector<int>& lowRest,
const vector<int>& highGain, double progress) {
if (cutList.empty()) return false;
out = cut;
int roll = rnd.integer(100);
if (roll < 8) {
// Move all cut sites on one (popular) row or column by one cell.
bool row = (rnd.integer(2) == 0);
int counts[50] = {};
for (int u : cutList) ++counts[row ? u/N : u%N];
int maxCount = *max_element(counts, counts+N);
if (maxCount >= 5) {
vector<int> lines;
for (int i=0;i<N;i++) if (counts[i] >= max(5,maxCount-3)) lines.push_back(i);
int line = lines[rnd.integer((int)lines.size())];
int off = rnd.integer(2) ? 1 : -1;
if (line+off >= 0 && line+off < N) {
vector<pair<int,int>> changes;
for (int j = 0; j < N; ++j) {
int old = row ? line*N+j : j*N+line;
int nxt = row ? (line+off)*N+j : j*N+line+off;
if (cut[old] && d[nxt] && !cut[nxt]) changes.push_back({old,nxt});
}
if (changes.size() >= 3) {
for (auto [a,b]:changes) { out[a]=0; out[b]=1; }
return true;
}
}
}
}
int k = swapSize(progress);
if (k == 0) return false;
vector<int> removed;
removed.reserve(k);
bool cluster = k>=2 && rnd.integer(100)<45;
int anchor = cutList[rnd.integer((int)cutList.size())];
for (int j=0;j<k;j++) {
int a = -1;
if (cluster) {
for (int trial=0;trial<30;trial++) {
int q=cutList[rnd.integer((int)cutList.size())];
int distance=abs(q/N-anchor/N)+abs(q%N-anchor%N);
if (out[q] && distance <= k+2) {a=q;break;}
}
}
if (a < 0 && !lowRest.empty() && rnd.integer(100)<60) {
int top = min((int)lowRest.size(), 30+7*k);
for (int trial=0;trial<20;trial++) {
int q=lowRest[rnd.integer(top)];
if (out[q]) { a=q;break; }
}
}
if (a < 0) {
for (int trial=0;trial<20;trial++) {
int q=cutList[rnd.integer((int)cutList.size())];
if (out[q]) {a=q;break;}
}
}
if (a < 0) for (int q:cutList) if (out[q]) {a=q;break;}
if (a < 0) return false;
removed.push_back(a);
out[a]=0;
}
for (int j=0;j<k;j++) {
int a=removed[j], b=-1;
if (rnd.integer(100)<75) {
int radius=rnd.integer(100)<80?2:5;
for (int tries=0;tries<35;tries++) {
int y=a/N + rnd.integer(2*radius+1)-radius;
int x=a%N + rnd.integer(2*radius+1)-radius;
if (x<0||x>=N||y<0||y>=N) continue;
int q=y*N+x;
if (d[q] && !cut[q] && !out[q]) {b=q;break;}
}
}
if (b < 0 && !highGain.empty()) {
int top=min((int)highGain.size(), 100+15*k);
for (int tries=0;tries<35;tries++) {
int q=highGain[rnd.integer(top)];
if (!cut[q] && !out[q]) {b=q;break;}
}
}
if (b<0) {
for (int tries=0;tries<35;tries++) {
int q=trees[rnd.integer((int)trees.size())];
if (!cut[q] && !out[q]) {b=q;break;}
}
}
if (b<0) for (int q:trees) if (!cut[q] && !out[q]) {b=q;break;}
if (b<0) return false;
out[b]=1;
}
return true;
}
public:
Solver(int n, int k, vector<int> dd)
: N(n), K(k), V(n*n), d(move(dd)), adj(V), degree(V,0),
rnd(0x31aa707f682e1cb9ULL), start(Clock::now()),
tin(V), low(V), sub(V), separateSum(V), separateSq(V),
mark(V), queueBuffer(V), comp(V) {
for (int v=0;v<V;v++) {
if (d[v]>0) trees.push_back(v);
int y=v/N,x=v%N;
if (y) adj[v][degree[v]++]=v-N;
if (y+1<N) adj[v][degree[v]++]=v+N;
if (x) adj[v][degree[v]++]=v-1;
if (x+1<N) adj[v][degree[v]++]=v+1;
}
// Guard against log(0) in scorers that don't handle E==0.
// If <=K trees exist, leaving one is always legal and ensures E>0.
if (!trees.empty() && (int)trees.size()<=K) {
sparseEnough = true;
K=(int)trees.size()-1;
}
else K=min(K,(int)trees.size());
dry.assign(NS,vector<uint8_t>(V));
for (int s=0;s<NS;s++) {
for (int v=0;v<V;v++) dry[s][v]=(d[v] && rnd.integer(10)<d[v]);
}
}
vector<uint8_t> solve() {
vector<uint8_t> empty(V,0);
if (sparseEnough) {
// Keep exactly one lowest-d tree: E remains positive, so log(E)
// is defined even if the checker has no special E==0 handling.
int survivor=trees[0];
for (int v:trees) if (d[v]<d[survivor]) survivor=v;
for (int v:trees) if (v!=survivor) empty[v]=1;
return empty;
}
if (K==0) return empty;
if (K==(int)trees.size()) {
for(int v:trees) empty[v]=1;
return empty;
}
vector<uint8_t> best=empty;
ll bestValidation = LLONG_MAX;
auto registerCandidate = [&](const vector<uint8_t>& cand) {
ll value = evaluate(cand,96,96);
if (value < bestValidation) {bestValidation=value;best=cand;}
};
// Initial greedy: always valid even if interrupted.
vector<uint8_t> greed(V,0);
greedyComplete(greed,32,0.70);
fillOnce(greed);
registerCandidate(greed);
if (timeOkay(0.85) && K>=50) {
vector<vector<int>> horizontal, vertical;
for (int t : {10,15,20,25,30,35,40}) {
horizontal.push_back(getBarrier(true,t,0));
vertical.push_back(getBarrier(false,t,0));
}
vector<pair<ll,vector<uint8_t>>> candidates;
auto addCandidate=[&](const vector<int>&a,const vector<int>&b) {
vector<uint8_t> c=makeCut(a,b);
if (numberCut(c)>K) return;
candidates.emplace_back(evaluate(c,0,6),move(c));
};
for (const auto &h:horizontal) for (const auto &v:vertical) {
if (!timeOkay(0.98)) break;
addCandidate(h,v);
}
for(int i=0;i<7;i++) for(int j=i+1;j<7;j++) {
if (!timeOkay(0.98)) break;
addCandidate(horizontal[i],horizontal[j]);
addCandidate(vertical[i],vertical[j]);
}
sort(candidates.begin(),candidates.end(),
[](const auto&a,const auto&b){return a.first<b.first;});
if(candidates.size()>5) candidates.resize(5);
for(auto& item:candidates) {
if(!timeOkay(1.07)) break;
fillOnce(item.second);
registerCandidate(item.second);
}
}
// Simulated annealing on common random numbers, with independent validation.
if(!timeOkay(1.14)) return best;
vector<uint8_t> current=best, trial;
const int SA_S=32;
ll currentScore=evaluate(current,0,SA_S);
ll bestSA=currentScore;
double saStart=elapsed(), saFinish=TIME_LIMIT-0.04;
double T0=max(10.0,(double)currentScore/SA_S*0.010);
double T1=max(0.3,(double)currentScore/SA_S*0.000010);
int accepted=0, lastRankUpdate=-10000, iter=0;
vector<int> cutList, lowRest, highGain;
vector<ll> gains(V), costs(V);
auto refreshCutList=[&]() {
cutList.clear();
for(int v:trees) if(current[v]) cutList.push_back(v);
};
auto refreshRanks=[&]() {
removalGains(current,12,gains);
restoreCosts(current,12,costs);
lowRest=cutList;
sort(lowRest.begin(),lowRest.end(),[&](int a,int b){return costs[a]<costs[b];});
highGain.clear();
for(int v:trees) if(!current[v]) highGain.push_back(v);
sort(highGain.begin(),highGain.end(),[&](int a,int b){return gains[a]>gains[b];});
if(highGain.size()>160)highGain.resize(160);
lastRankUpdate=accepted;
};
refreshCutList();
while(timeOkay(saFinish)) {
++iter;
if (lastRankUpdate < 0 || (accepted-lastRankUpdate>=24 && timeOkay(saFinish-0.08))) {
refreshRanks();
}
double progress=(elapsed()-saStart)/max(0.001,saFinish-saStart);
progress=max(0.0,min(1.0,progress));
if(!propose(trial,current,cutList,lowRest,highGain,progress))continue;
ll newVal=evaluate(trial,0,SA_S);
ll delta=newVal-currentScore;
double temp=T0*pow(T1/T0,progress)*SA_S;
if(delta<=0 || (rnd.real()<exp(-double(delta)/max(1e-9,temp)))) {
current.swap(trial);
currentScore=newVal;
++accepted;
refreshCutList();
}
if(currentScore<bestSA) {
bestSA=currentScore;
if(timeOkay(saFinish-0.005)) registerCandidate(current);
}
}
// Validate the final state if possible.
if(timeOkay(TIME_LIMIT-0.006)) registerCandidate(current);
return best;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
if(!(cin >> N >> K)) return 0;
if(N <= 0 || N > 50 || K < 0) { cout << "0\n"; return 0; }
// Each dry level is a SINGLE DIGIT (0..9).
// Accept both contiguous digit rows and whitespace-separated cells.
// Read characters rather than extracting multi-digit ints.
vector<int> d(N*N);
int filled = 0;
char ch;
while (filled < N*N && cin.get(ch)) {
if (ch >= '0' && ch <= '9') d[filled++] = ch - '0';
}
if (filled != N*N) {
cout << "0\n";
return 0;
}
Solver solver(N,K,d);
auto cut=solver.solve();
// Output sanitizer: never emit an invalid cell, repeated coordinate or >K cuts.
vector<int> output;
for (int v=0;v<N*N;v++) if (cut[v] && d[v]>0 && (int)output.size()<K)
output.push_back(v);
cout << output.size() << '\n';
for (int v : output) cout << v/N << ' ' << v%N << '\n';
return 0;
}