メモリの走査方向をちょっと変えたら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