AtCoder ARC #019 : D - ほんとうのたたかい

本番惜しいところまで行ったけど時間切れだった。
http://arc019.contest.atcoder.jp/tasks/arc019_4

問題

NxN(<=150)のグリッドを成すセル上にいくつか'O'を配置したい。
軸に平行な長方形を作るような4セルを選んだ時、4セルとも'O'が置かれることが無いようにしたまま、'O'を1700個以上配置せよ。

解法

テキストでの解答は下記の通り。
http://arc019.contest.atcoder.jp/submissions/144994

13個の'O'を含む(13x13)の正方形を(13x13)個並べると全体で169x169の行列で2197個のOが置けることになる。
そのうち150x150個分を取れば1700個配置できる。

まず、一番上の行の(13x13)の正方形を考える。
i列目に配置する正方形はi行目のみ'O'で埋めるようにする。
答えのうち以下に該当する。
これは明らかに4点選んでも'O'が4つそろうことはない。

OOOOOOOOOOOOO.........................................................................................................................................
.............OOOOOOOOOOOOO............................................................................................................................
..........................OOOOOOOOOOOOO...............................................................................................................
.......................................OOOOOOOOOOOOO..................................................................................................
....................................................OOOOOOOOOOOOO.....................................................................................
.................................................................OOOOOOOOOOOOO........................................................................
..............................................................................OOOOOOOOOOOOO...........................................................
...........................................................................................OOOOOOOOOOOOO..............................................
........................................................................................................OOOOOOOOOOOOO.................................
.....................................................................................................................OOOOOOOOOOOOO....................
..................................................................................................................................OOOOOOOOOOOOO.......
...............................................................................................................................................OOOOOOO
......................................................................................................................................................

次に一番左側、同様にi行目の正方形にはi列目を'O'で埋めるようにする。
答えのうち以下の部分。

O............
O............
O............
O............
O............
O............
O............
O............
O............
O............
O............
O............
O............
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
.O...........
..O..........
..O..........
..O..........
..O..........

それ以外の(13x13)の正方形については、各行に1個ずつ'O'が置かれるようにしたい。
以下の形を基本形とする。1行目の'O'の位置P=0、行間の'O'の位置の差Q=1といえる。
右の正方形に行くほどPを増し、下にいく程Qが増えるようにして正方形を敷き詰めればよい。

O............
.O...........
..O..........
...O.........
....O........
.....O.......
......O......
.......O.....
........O....
.........O...
..........O..
...........O.
............O

コードで書くと以下の通り。

void solve() {
	int f,i,j,k,l,x,y;
	int R=0,C=0;
	f=0;
	_P("150\n");
	FOR(y,13) {
		FOR(x,150) {
			if(x>=y*13 && x<y*13+13) _P("O"),f++;
			else _P(".");
		}
		_P("\n");
	}
	R=13;
	FOR(l,13) {
		FOR(y,13) {
			if(++R>150) break;
			C=0;
			FOR(x,13) {
				if(x==l)  _P("O"),f++;
				else _P(".");
			}
			C=13;
			int st=y;
			FOR(x,13) {
				//_P("|");
				FOR(i,13) {
					if(C++>=150) break;
					if(i==st) _P("O"),f++;
					else _P(".");
				}
				st+=l;
				st%=13;
			}
			_P("\n");
		}
	}
	//_P("%d\n",f);
}

まとめ

本番、(12x12)を敷き詰めたところ、最後のQにおいてQが12の約数になるとき同じ形の正方形ができてしまい失敗した。
12じゃなく奇数の13を選んでおけば…。