SRM 261 DIV II

先週参加できなかったので練習してみた。DIV II の 1000点問題 GomokuBoardChecker がハマり問題。五目並べの盤面が与えられて、それが "INVALID" か "IN PROGRESS" か "DRAW"、もしくは勝った方を答えるというもの。クロスして五目が並んだときの状態が INVALID か否かの判定をするのが面倒。こんな良問よく考え付くなぁ。

"O の勝ちの例"
 O.X.O.
 .OX.O.
 X.O.O.
 X..OO.
 ..XXOX
 XXXXOO

"INVALID の例"
 O.XX.O
 .OX..O
 X.O..O
 X..O.O
 ..XXOO
 XXXX.O

クロスしている最後の１手が有効であることを確認しないといけない。もちろん手数のチェックも必要。(O が最後に打ってないと INVALID)。実際、この問題二人しか正答できていないのか。

で、そのチェックは brute force で１つ石を取り除いて(=最後の一手)五目にならないことを調べればよい、か。これでも計算時間は足りるのか。