kmjp's blog

競技プログラミング参加記です

yukicoder : No.440 2次元チワワ問題

メモリの走査方向をちょっと変えたら3倍速くなってびっくり。
http://yukicoder.me/problems/no/440

問題

H*Wのグリッドの各セルにcかwのいずれかが書かれている。

このグリッド内で矩形領域クエリがQ個与えられる。
それぞれ、以下の条件を満たす3マスの組がいくつあるか求めよ。

  • 3マスは領域内にある異なるマスで、同じ行か列にある。
  • 上下左右いずれかの順で3つのマスの文字列を並べるとcwwとなる(cのマスが真ん中に来るケースは不可)

解法

横方向に3マスが並ぶ場合を考える。
各行において、左端・右端を定めたとき、以下を求める。
dp(行, 左端, 右端) := 対応する行の左端から右端の範囲で、内部に左からcwwまたは左からwwcの順でセルが登場する数
これは左端を総当たりし、それぞれ右端を1つずつ右に伸ばして行きながらc,cw,cww,w,ww,wwcの登場回数をカウントしていけば良い。
この処理はO(HW^2)で済む。

縦の場合も同様に行えばよい。
ただO(HW^2+H^2W)のメモリを一度に確保しようとするとMLEの懸念があるので、自分は縦と横はそれぞれメモリ領域を使いまわしで行った。
後は各クエリに対し、各行・各列に対応する上記dp値を用いるとO(Q*(H+W))で全クエリに答えられる。
合わせるとO*1でちょっと重いがどうにかなる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	cin>>Q;
	FOR(i,Q) {
		cin>>U[i]>>L[i]>>D[i]>>R[i];
		U[i]--,D[i]--,L[i]--,R[i]--;
	}
	FOR(y,H) {
		FOR(x,W) {
			int nc=0, ncw=0, ncww=0;
			int nw=0, nww=0, nwwc=0;
			for(int z=x;z<W;z++) {
				if(S[y][z]=='c') {
					nc++;
					nwwc+=nww;
				}
				else {
					ncww+=ncw, ncw+=nc;
					nww+=nw, nw++;
				}
				dp[y][x][z]=ncww+nwwc;
			}
		}
	}
	FOR(i,Q) {
		for(y=U[i];y<=D[i];y++) ret[i]+=dp[y][L[i]][R[i]];
	}

	FOR(x,W) {
		FOR(y,H) {
			int nc=0, ncw=0, ncww=0;
			int nw=0, nww=0, nwwc=0;
			for(int z=y;z<H;z++) {
				if(S[z][x]=='c') {
					nc++;
					nwwc+=nww;
				}
				else {
					ncww+=ncw, ncw+=nc;
					nww+=nw, nw++;
				}
				dp[x][y][z]=ncww+nwwc;
			}
		}
	}
	
	FOR(i,Q) {
		for(x=L[i];x<=R[i];x++) ret[i]+=dp[x][U[i]][D[i]];
		cout<<ret[i]<<endl;
	}
}

まとめ

cwwだけで良くこんなに問題作れるなぁ。

*1:H+W)*(HW+Q