No.002 D

※ コードは WA が取れてない

駒を動かす方向に敵の駒がない場合は特別扱いで, そのような駒がある方が勝ちである. 双方にそのような駒がある場合は敵陣に近い方が勝ちである. (敵陣までの距離が同じならば先手の勝ち)

そうでない場合は, 駒を取られないように動かすのが最適である. そこで, あと何手駒を取られないように動かせるかを考える.

配置 o.oo.x.xx のようにお互いの先頭の駒が1マス空いている場合を考える. このときは先手はあと1手, 後手はあと2手動かすことができる.

次に配置 o.oo...x.xx のお互いの先頭の駒が2マス以上空いている場合を考える. このとき, 手番が先手の場合で先頭の駒を動かすと, 先手の残り可能手数が1手増え, 後手の残り可能手数が3手減る. すなわち5手得をする. すなわち, 先手の駒の個数と後手の駒の個数を $i, j$ とすると, $i+j-2$ 手の得になるということである. これは手番が後手の場合でも同じである.

よって, お互いの先頭のマスが2マス以上空いている状態の部分でなるべく双方の駒数の合計が多い部分を詰めていき, 最終的にそういう部分がなくなったときに残り可能手数が多い方が勝ちとなる.

なお, 間のマスが奇数のときは双方同じ手数詰められるのでこのような状態は最初から間のマスは1マスとしてよく, 間のマスが偶数のときは間のマスを2マスとすればいい.