Codeforces #789 : Div1 B. Tokitsukaze and Meeting

4問目まで割と易しかった回。
https://codeforces.com/contest/1677/problem/B

問題

N*Wのセルと、0/1の列が与えられる。0/1の列が、徐々にシフトする形でセルに埋められていく。
シフトのステップ毎に、1個以上1が並ぶ列・行の数を求めよ。

解法

シフトすると考えず、シフトではなく左上から順に0/1が埋まっていくと考えてもよい。
列と行別々に考え、それぞれ列・行に初めて1が入るタイミングを数えていこう。

int T;
int H,W;
string S;
int C[1010101],R[1010101],P[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>S;
		FOR(i,H*W) {
			C[i+1]=C[i]+(S[i]=='1');
			R[i+1]=0;
			P[i+1]=0;
		}
		
		FOR(i,W) {
			int x=0;
			FOR(y,H) {
				if(S[y*W+i]=='1') {
					P[y*W+i+1]++;
					break;
				}
			}
		}
		for(i=1;i<=H*W;i++) {
			if(C[i]-C[max(i-W,0)]) R[i]++;
			if(i>=W) R[i]+=R[i-W];
			P[i]+=P[i-1];
		}
		for(i=1;i<=H*W;i++) cout<<(R[i]+P[i])<<" ";
		cout<<endl;
	}
}

まとめ

本番はまともにシフトして考えてたっぽいな…。