お誕生日コンテスト : B - ライスゲーム

予備知識があると有利な問題。
http://birthday0410.contest.atcoder.jp/tasks/birthday0410_b

問題

数Nが与えられる。
NxNのフィールドに、生存マスをN個配置したい。
N個の生存マスは連結しており、かつ以後状態が変化しない構成を答えよ。

解法

まず、状態が変化しないケースを以下を参照に見てみる。
固定物体 (ライフゲーム) - Wikipedia

このうち、「はしけ」の構造はもっと長くなっても状態が普遍であることが容易に想像がつく。
Nが奇数の場合は、このはしけの端っこに対し、「ボート」の例のように１マス追加すればよい。
以下はN=8,9の場合である。
なお、N<4の時は答えは無い。

........
..#.....
.#.#....
..#.#...
...#.#..
....#...
........
........

.........
.##......
.#.#.....
..#.#....
...#.#...
....#....
.........
.........
.........

int N;
string S[1001];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	
	if(N==4) return _P("....\n.##.\n.##.\n....\n");
	if(N<4) return _P("-1\n");
	
	FOR(x,N) FOR(y,N) S[x]+=".";
	for(x=1;x<=N/2;x++) {
		S[x+1][x] = S[x][x+1] = '#';
	}
	if(N%2) S[1][1]='#';
	
	FOR(x,N) cout << S[x] << endl;
}

まとめ

これはWikipediaを見てすんなり思いついた。