Google Code Jam 2018 Round1A : A. Waffle Choppers

45分スマホで問題見て、実装時間15分ではさすがに通りませんでした。
https://codejam.withgoogle.com/2018/challenges/0000000000007883/dashboard

問題

2次元グリッド上の一部のマスにチョコレートがある。
このグリッドを縦V個、横H個の切れ目を入れ、(V+1)*(H+1)個の矩形に分けたい。
各矩形にあるチョコレート数を等しくせよ。

解法

縦横個別にチョコレート数が等しくなるよう切れ目の位置を決め、最後の(V+1)*(H+1)の矩形が皆同じチョコレート数か判定すればよい。

int T,testcase;
int H,W,A,B;
string S[101];


void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	A++;
	B++;
	int num=0;
	FOR(y,H) {
		cin>>S[y];
		FORR(c,S[y]) c=(c=='@'), num+=c;
	}
	
	if(num%(A*B)) return _P("Case #%d: IMPOSSIBLE\n",TC);
	if(num==0) return _P("Case #%d: POSSIBLE\n",TC);
	
	vector<int> P(A+1,-1),Q(B+1,-1);
	
	j=0;
	FOR(y,H) {
		FOR(x,W) j+=S[y][x];
		if(j%(num/A)==0) P[j/(num/A)]=y;
	}
	j=0;
	FOR(x,W) {
		FOR(y,H) j+=S[y][x];
		if(j%(num/B)==0) Q[j/(num/B)]=x;
	}
	if(count(ALL(P),-1)>1 || count(ALL(Q),-1)>1) return _P("Case #%d: IMPOSSIBLE\n",TC);
	

	FOR(i,A) FOR(j,B) {
		int tot=0;
		for(y=P[i]+1;y<=P[i+1];y++) for(x=Q[j]+1;x<=Q[j+1];x++) tot+=S[y][x];
		if(tot!=num/(A*B)) return _P("Case #%d: IMPOSSIBLE\n",TC);
	}
	return _P("Case #%d: POSSIBLE\n",TC);
}

まとめ

もう少し頑張って1Aで突破しておきたかった。