SRM 455 Div2 Hard DonutsOnTheGrid

問題
http://community.topcoder.com/stat?c=problem_statement&pm=10717

'.'か'0'のどちらかの要素を持つグリッドをまず計算する。辺の長さが3以上で辺が全て'0'である長方形の数を求めよ。

頻出問題っぽい。普通にするとO(n^4)で間に合わない。まずはある座標から左側にどれだけ'0'が連続するか求めておく。後に2カラム選んで、その中でyを縦方向に動かす。この時に2行前に辺を張れるならcntを増やしていき、今見ているy行目にも辺が張れると分かった時点でcntを合計値に足していく。

（追記）
２行前に辺が張れるのを調べているのは、ドーナツの穴のサイズが最低でも1x1以上であることから。一行前を調べて辺が張ってあり、今見ている行に辺が張ってあったとしても、この2辺を上辺下辺とする長方形をドーナツにはできない。

こんな感じ↓

i　　 j
0000
0 . .0
0000 cnt 1 result 1
0000 　　　 result 2
0 . .0 cnt 2
0 . .0 cnt 3
0000　　　　result 5
0 . .0

わからなかったのだけれど、kusano_progさんの答えが参考になった。

以下ソース。

int xline[360][360];
int yline[360][360];

class DonutsOnTheGrid {
public:
  long long calc(int H, int W, int seed, int threshold) {
    long long result = 0;
    vector<string> field(H, string(W, '0'));
    ll se = seed;
    for(int i = 0; i < H * W; i++){
      se = (se * 25173 + 13849) % 65536;
      if(se >= threshold) field[i / W][i % W] = '.';
    }
    
    memset(xline, 0, sizeof(xline));
    memset(yline, 0, sizeof(yline));

    //(j, i)からどれだけ'0'が連続するか計算
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
	for(int k = 0; k + i < H; k++){
	  if(field[k + i][j] == '0') yline[i][j]++;
	  else break;
	}
	for(int k = 0; k + j < W; k++){
	  if(field[i][k + j] == '0') xline[i][j]++;
	  else break;
	}
      }
    }
    for(int i = 0; i < W; i++){
      for(int j = i + 2; j < W; j++){

	int cnt = 0;

	for(int y = 2; y < H; y++){
	  if(j - i < xline[y - 2][i])
	    cnt++;
	  if(!(field[y - 1][i] == '0' && field[y - 1][j] == '0'))
	    cnt = 0;
	  if(j - i < xline[y][i])
	    result += cnt;
	}
      }
    }
    return result;
  }

これからはしばらくDiv2 Hardをやっていこう。なるべく解いたら公開していきたい。

2週目感想
辺のつながりを前もって計算する部分をboolで計算しており、配列が大きすぎてSIGKILL。また正常に計算できなかったためギブアップ。上のコードを参考にした。
cntの値を蓄積していき、張れるところで今までのまとめて足し上げるのはうまい。