TopCoder SRM 817 : Div1 Easy Div2 Hard DogsInAGrid

解けるところは順当に解いてレート微増。
https://community.topcoder.com/stat?c=problem_statement&pm=17249&rd=18897

問題

40*40のマス目に、D・O・Gの文字を埋めることを考える。
3つの縦・横・斜めに連続するマスがDOGの順になっている(下から上や右から左に読んでも良い)箇所がN通りになるような埋め方を答えよ。

解法

"DOGODOGO…"で各行を埋めた場合、凡そD1個あたりでDOGが6個増えることになる。
これをもとに、Nに近づく範囲でDを埋めて行こう。
この作業は最大39列目まで行う。ここまででDOGの出現回数がNに足りないときは、40列目に縦に"DOGODOGO…"と埋めて帳尻を合わせよう。

以下のコードは一応DOGの登場回数チェックも行っている。

class DogsInAGrid {
	public:
	vector <string> construct(int N) {
		
		vector<string> R;
		int y,x;
		string S="OOGOOOGOOOGOOOGOOOGOOOGOOOGOOOGOOOGOOOGO";
		int tot=0;
		FOR(y,40) R.push_back(S);
		for(int x=0;x<=36;x+=4) {
			FOR(y,40) {
				int num=0;
				if(x>=2) num+=1+(y>=2)+(y<=37);
				if(x+2<=39) num+=1+(y>=2)+(y<=37);
				if(tot+num<=N) {
					R[y][x]='D';
					tot+=num;
				}
				
			}
		}
		for(y=2;y<=37;y+=4) R[y][39]='G';
		for(y=0;y<=39;y+=4) {
			int num=0;
			if(y+2<=37) num++;
			if(y-2>=0) num++;
			if(tot+num<=N) {
				R[y][39]='D';
				tot+=num;
			}
		}
		
		
		int sum=0;
		int dy[9]={1,1,1,0,0,0,-1,-1,-1};
		int dx[9]={1,0,-1,1,0,-1,1,0,-1};
		
		FOR(y,40) FOR(x,40) if(R[y][x]=='D') {
			int d;
			FOR(d,9) {
				if(y+dy[d]*2<0||y+dy[d]*2>=40) continue;
				if(x+dx[d]*2<0||x+dx[d]*2>=40) continue;
				if(R[y+dy[d]][x+dx[d]]!='O') continue;
				if(R[y+dy[d]*2][x+dx[d]*2]!='G') continue;
				sum++;
			}
		}
		assert(sum==N);
		return R;
		
	}
}

まとめ

チェックもしたので時間を食ったが、お蔭でミスしなかったので良かったとするか。