オフラインでリアルタイムに「どう書く」をやるイベント。
またやります
http://atnd.org/events/32191
で。例によって参考問題。
難易度と分量はこれを目安にと言いたいところだけれども、たぶんこれは難しすぎる。
こんなに難しい問題は出しませんよ、という意味で参考に。
フカシギの数え方( http://www.youtube.com/watch?v=Q4gTV4r0zRs )が余りにも素晴らしかったので、そこから
フカシギの通行止め
4✕4 のマス目の辺を通っての左上から右下に行く方法は何通りあるか計算する。
※ ビデオに合わせて 4✕4 と書いたが、縦に5本 横にも5本の道があり、頂点数は 25個である。
ただし
- 同じ頂点を二度通ってはいけない。
- ところどころ行き止まりがある。
- ビデオを見るとわかるが、行き止まりなしで 8512通り。
- 不正入力には対処しなくてよい。
行き止まりを表現するために、頂点に a〜y の名前を順につける。
入力文字列が "fg gh" なら、行き止まりは二箇所。fとgの間とgとhの間。
入力と出力の例
以下、"入力" -> 出力 # コメント の形式で例を示す
"" -> 8512 #そのまま。これが最大値。
"af" -> 4256 #対称性より半分になる
"xy" -> 4256 #対称性より半分になる
"pq qr rs st di in ns sx" -> 184 #3x3マスと同値
"af pq qr rs st di in ns sx" -> 92 #3x3マスのパターンの半分
"bg ch di ij no st" -> 185 #3x3マスのパターン +1
"bc af ch di no kp mr ns ot pu rs" -> 16 #4x2x2
"ab af" -> 0 #入口を塞いだ
"ty xy" -> 0 #出口を塞いだ
"bg ch ej gh lm lq mr ot rs sx" -> 11 #2x4+3
"ty ch hi mn kp mr rs sx" -> 18 #6*3
"xy ch hi mn kp mr rs sx" -> 32 #4*8
"ch hi mn kp mr rs sx" -> 50 #6*3+4*8
"ab cd uv wx" -> 621
"gh mn st lq qr" -> 685
"fg gl lm mr rs" -> 171
※ 解答例をコメント欄に（ソースではなく）リンクの形で書いてくださるとありがたいです。
※ そのうち ruby か groovy で解答例を投稿するつもり。