Hello 2025 : G. Secret Message

本番中に詰められなかった…。
https://codeforces.com/contest/2057/problem/G

問題

白黒で塗られたグリッドが与えられる。
白マスの数をW、連結した白マスの外周の長さの総和をPとする。
黒マスのいくつかを選択し、以下を満たすようにしたい。
一例を示せ。

• 黒マスの選択数をSとすると、S≦(W+P)/5
• 黒マスは、選択されているか選択マスに隣接するかのいずれかである。

解法

元のグリッドを(白黒とは別の)5色で均等に彩色したとする。
すると、5色のうち以下のルールで黒マスを選択すると、必ず1つ条件を満たすものがある。

• 5色うち選択された色に彩色された黒マスは、選択マスとする。
• 5色うち選択された色に彩色された白マスは、隣接する黒マスを選択マスとする。

int T;
int H,W;
string S[2020202];
vector<pair<int,int>> V[5];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) cin>>S[y];
		FOR(i,5) V[i].clear();
		
		for(y=-1;y<=H;y++) for(x=-1;x<=W;x++) {
			i=((y+5)*2+(x+5))%5;
			if(y>=0&&y<H&&x>=0&&x<W&&S[y][x]=='#') {
				V[i].push_back({y,x});
			}
			else {
				int ty[4]={y+1,y,y-1,y};
				int tx[4]={x,x+1,x,x-1};
				FOR(j,4) if(ty[j]>=0&&ty[j]<H&&tx[j]>=0&&tx[j]<W&&S[ty[j]][tx[j]]=='#') V[i].push_back({ty[j],tx[j]});
			}
			
		}
		vector<pair<int,int>> R=V[0];
		FOR(i,5) if(V[i].size()<R.size()) R=V[i];
		FORR2(y,x,R) S[y][x]='S';
		FOR(y,H) cout<<S[y]<<"\n";
		
		
	}
}

まとめ

実装よりも考察が難しいタイプの問題。