Google Code Jam 2015 Round 1B : B. Noisy Neighbors

この問題もミスが怖い。
https://code.google.com/codejam/contest/8224486/dashboard#s=p1

問題

整数R,C,Nが与えられる。

R*Cのグリッド中Nマスに人が住むとする。
隣接するマスに共に人が住んでいると、騒音のため不快感が生じる。
これを防ぐためには、そのような隣接マスの間に壁を張らなければならない。

人が住むNマスを最適に指定した場合、張らなければいけない壁の最小数を求めよ。

解法

市松模様状に人が住めば、壁は不要である。
ただ、市松模様ではR*Cのグリッド中約半分しか人が住めない。

それ以上に人が住む場合、できるだけ壁を張る数が少ない場所から順に埋めていけば良い。
角のセルは壁2枚、周辺部は3枚、その他は4枚必要である。

なお、最初の市松模様の取り方は2通りあるので両方試す必要がある。

int H,W,N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W>>N;
	if(H>W) swap(H,W);
	
	vector<int> S[2];
	
	FOR(y,H) FOR(x,W) {
		i=0;
		if(x>0) i++;
		if(x<W-1) i++;
		if(y>0) i++;
		if(y<H-1) i++;
		S[(y+x)%2].push_back(i);
	}
	
	int mi=100000;
	FOR(i,2) {
		x=N-S[i^1].size();
		sort(S[i].begin(),S[i].end());
		if(x<=0) mi=0;
		else mi=min(mi,accumulate(S[i].begin(),S[i].begin()+x,0));
	}
	
	_P("Case #%d: %d\n",_loop,mi);
}

まとめ

シンプルな問題設定でいいけど、色々コーナーケースが怖いな。