結果
| 問題 | No.5025 Forest Fire |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-10-24 17:44:42 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,811 ms / 2,000 ms |
| + 291µs | |
| コード長 | 13,158 bytes |
| 記録 | |
| コンパイル時間 | 2,896 ms |
| コンパイル使用メモリ | 355,780 KB |
| 実行使用メモリ | 9,916 KB |
| スコア | 171,575,303 |
| 最終ジャッジ日時 | 2026-10-24 17:50:25 |
| 合計ジャッジ時間 | 150,543 ms |
|
ジャッジサーバーID （参考情報） |
judge6_0 / <nil> |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
//ライブラリへのリンク
//https://drive.google.com/drive/folders/1QDp2j94gwNBUf6lF2M-FTs9NVAKFpw5R
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmin_ref(T &a,const T &b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::steady_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::steady_clock::now();
}
void snap(){
start=chrono::steady_clock::now();
}
int get_ms(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
mt19937 mt;
uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){ //[l,r)
assert(l<r);
return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){ //[0.0,1.0]
return mt()*one_div_mt_max;
}
double rand_double(double l,double r){ //[l,r]
return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
assert(!v.empty());
return v[rand_int(len(v))];
}
template<class T> void add(vector<T> &a,vector<T> b){
for(auto i:b) a.push_back(i);
}
constexpr int N=50,K=100;
array<int,N*N> D;
array<array<int,4>,N*N> G;
int one(int i,int j){
return i*N+j;
}
pii two(int x){
return {x/N,x%N};
}
namespace Solver{
double calc_e(const array<bool,N*N> &is_cut){
array<bool,N*N> is_tree;
is_tree.fill(false);
rep(i,N*N){
if(is_cut[i]) continue;
if((int)rand_int(10)<D[i]) is_tree[i]=true;
}
array<int,N*N> root;
root.fill(-1);
rep(i,N*N){
if(!is_tree[i]) continue;
if(root[i]!=-1) continue;
queue<int> q;
q.push(i);
root[i]=i;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto y:G[x]){
if(y==-1) continue;
if(!is_tree[y]) continue;
if(root[y]!=-1) continue;
root[y]=i;
q.push(y);
}
}
}
array<int,N*N> cnt;
cnt.fill(0);
rep(i,N*N){
if(root[i]!=-1) cnt[root[i]]++;
}
double ret=0;
rep(i,N*N){
ret+=cnt[i]*cnt[i];
}
ret/=N*N;
return ret;
}
double calc_true_score(const array<bool,N*N> &is_cut,int try_turn){
assert(try_turn!=0);
double e=0;
rep(_,try_turn) e+=calc_e(is_cut);
e/=try_turn;
return e;
}
array<double,N*N> now_dry;
double calc_score(const array<bool,N*N> &is_cut){
int cut_cnt=0;
rep(i,N*N){
if(D[i]==0) continue;
if(is_cut[i]){
cut_cnt++;
continue;
}
}
if(K<cut_cnt) return INF;
array<int,N*N> root;
root.fill(-1);
rep(i,N*N){
if(!now_dry[i]) continue;
if(root[i]!=-1) continue;
if(is_cut[i]) continue;
queue<int> q;
q.push(i);
root[i]=i;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto y:G[x]){
if(y==-1) continue;
if(!now_dry[y]) continue;
if(root[y]!=-1) continue;
if(is_cut[y]) continue;
root[y]=i;
q.push(y);
}
}
}
array<int,N*N> cnt;
cnt.fill(0);
rep(i,N*N){
if(root[i]!=-1) cnt[root[i]]++;
}
double ret=0;
rep(i,N*N){
ret+=cnt[i]*cnt[i];
}
ret/=N*N;
return ret;
}
void solve(){
double best_true_score=INF;
vector<int> best_ans;
while(Timer::get_ms()<1800){
array<bool,N*N> is_cut;
is_cut.fill(false);
rep(i,N*N){
if((int)rand_int(10)<D[i]) now_dry[i]=true;
else now_dry[i]=false;
}
while(Timer::get_ms()<1800){
rep(i,N*N){
if(D[i]==0) continue;
if(is_cut[i]) continue;
}
array<int,N*N> root;
root.fill(-1);
int comp_cnt=0;
rep(i,N*N){
if(!now_dry[i]) continue;
if(root[i]!=-1) continue;
if(is_cut[i]) continue;
queue<int> q;
q.push(i);
root[i]=comp_cnt;
comp_cnt++;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto y:G[x]){
if(y==-1) continue;
if(!now_dry[y]) continue;
if(root[y]!=-1) continue;
if(is_cut[y]) continue;
root[y]=root[i];
q.push(y);
}
}
}
array<int,N*N> cnt;
cnt.fill(0);
rep(i,N*N){
if(root[i]!=-1) cnt[root[i]]++;
}
vector<int> ord(comp_cnt);
rep(i,comp_cnt) ord[i]=i;
sort(all(ord),[&](int i,int j){return cnt[i]>cnt[j];});
//if(20<len(ord)) ord.resize(20);
int pre_score=calc_score(is_cut);
double best_score=0;
auto best_is_cut=is_cut;
for(auto r:ord){
int max_i=-INF,max_j=-INF,min_i=INF,min_j=INF;
rep(i,N){
rep(j,N){
if(root[one(i,j)]==r){
chmax(max_i,i);
chmax(max_j,j);
chmin(min_i,i);
chmin(min_j,j);
}
}
}
rep(d,6){
auto new_is_cut=is_cut;
int new_cnt=0;
if(d==0){
replr(i,min_i,max_i+1){
int p=one(i,(min_j+max_j)/2);
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==1){
replr(j,min_j,max_j+1){
int p=one((min_i+max_i)/2,j);
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==2){
replr(i,min_i,max_i+1){
if(N<=min_j+i) continue;
int p=one(i,min_j+i-min_i);
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==3){
replr(i,min_i,max_i+1){
if(max_j-(i-min_i)<0) continue;
int p=one(i,max_j-(i-min_i));
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==4){
replr(j,min_j,max_j+1){
if(max_i-(j-min_j)<0) continue;
int p=one(max_i-(j-min_j),j);
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
if(d==5){
replr(j,min_j,max_j+1){
if(N<=min_i+(j-min_j)) continue;
int p=one(min_i+(j-min_j),j);
//if(root[p]!=r) continue;
if(D[p]!=0&&!is_cut[p]) new_cnt++;
new_is_cut[p]=true;
}
}
int new_score=calc_score(new_is_cut);
double good_score=(double)(pre_score-new_score)/new_cnt;
//cerr << new_score << " " << best_score << endl;
if(chmax(best_score,good_score)){
best_is_cut=new_is_cut;
}
}
}
if(is_cut==best_is_cut) break;
is_cut=best_is_cut;
}
vector<int> ans;
rep(i,N*N){
if(D[i]==0) continue;
if(is_cut[i]) ans.push_back(i);
}
double true_score=calc_true_score(is_cut,100);
if(chmin(best_true_score,true_score)){
best_ans=ans;
}
cerr << true_score << endl;
}
assert(len(best_ans)<=K);
cout << len(best_ans) << '\n';
for(auto p:best_ans){
auto [i,j]=two(p);
cout << i << ' ' << j << '\n';
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int n,k;
cin >> n >> k;
rep(i,N){
rep(j,N){
char c;
cin >> c;
D[one(i,j)]=c-'0';
}
}
rep(i,N*N) G[i].fill(-1);
rep(i,N){
rep(j,N){
if(j+1<N){
G[one(i,j)][3]=one(i,j+1);
G[one(i,j+1)][2]=one(i,j);
}
if(i+1<N){
G[one(i,j)][1]=one(i+1,j);
G[one(i+1,j)][0]=one(i,j);
}
}
}
Solver::solve();
exit(0);
}