無理に穴開けなくてもいいんじゃないですかね…。
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_h
問題
H*Wの大きさのグリッドが与えられる。
各セルには1~9の数値が振られている。
このグリッドから3*3以上のサイズの長方形領域を抽出し、かつ抽出後周辺部以外の1マスをくり抜いた形状を作ったとき、残ったセルの数値の総和がKとなるようにしたい。
そのような形状の作り方の組み合わせを求めよ。
解法
まずは2次元の累積和を求め、矩形の範囲における数値の総和をO(1)で計算できるようにしておこう。
同様に、矩形の範囲に1~9がそれぞれ何個登場するかも、2次元の累積和を求めておく。
仮に矩形の位置を総当たりする場合を考える。
矩形の面積がK+p (1≦p≦9)の場合、矩形内部におけるpの数値を持つマスの数を数え上げればいいことになる。
面積の計算もpの数値のマスの数も、前処理によりO(1)で計算できるので、あとは矩形の位置の総当たりを頑張ればよい。
単純に総当たりすると上端下端左端右端を総当たりするのでO(R^2*C^2)かかり間に合わない。
上端y1、左端x1を総当たりすることにする。
下端y2を下げていくと、数値の和が最初にKを超える右端x2が単調増加することがわかる。
よって、y2の変化に対し尺取法の要領で対応するx2を求めていこう。
後は右端をx2~(x2+3)程度の範囲で探索して、数値の和がK+9以下のケースを求めればよい。
こうするとO(R*C*(R+C))になる。
上端・左端・下端を決めた後、右端を二分探索する手もある。この場合O(R^2*C*logC)になるがなんとか間に合うようだ。
int H,W,K; string S[400]; int tot[11][400][400]; ll ret; ll sum(int top,int left,int bot,int right,int n) { return tot[n][bot+1][right+1]-tot[n][top][right+1]-tot[n][bot+1][left]+tot[n][top][left]; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>K; FOR(y,H) { cin>>S[y]; FOR(x,W) tot[S[y][x]-'0'][y+1][x+1]++, tot[10][y+1][x+1]+=S[y][x]-'0'; } FOR(i,11) FOR(y,H) FOR(x,W) tot[i][y+1][x+1] += tot[i][y+1][x]+tot[i][y][x+1]-tot[i][y][x]; int top,left,right,bottom; FOR(top,H-2) FOR(left,W-2) { int right=left+2; for(bottom=H-1;bottom>=top+2;bottom--) { while(right<W && sum(top,left,bottom,right,10)<=K) right++; for(r=right;r<W;r++) { ll ts=sum(top,left,bottom,r,10); if(ts>=K+10) break; ret += sum(top+1,left+1,bottom-1,r-1,ts-K); } } } cout<<ret<<endl; }
まとめ
これはすんなり解けて良かった。
むしろ二分探索は思いつかなかった。