AtCoder Regular Contest #012 C.五目並べチェッカー
問題
碁石ののった19路盤が与えられる。
その状態が五目並べとして正常であるか判定する。
異常な状態とは、
・どちらかのプレイヤーが勝利条件をみたしているのに、もう片方のプレイヤーがさらに碁石をおいている
・お互いが置いた個数がありえない
のどちらか。
考え方
異常な状態はたくさん考えられるので、正常な状態ならYESを返すように条件を書く。
正常な条件は、
・黒の数=白の数の時、どっちも勝っていない、か、白が勝っている状態
・黒の数=白の数+1の時、どっちも勝っていない、か、黒が勝っている状態
しかない。
黒または白が勝っているかどうかは、ある場所からある方向に連続で同じ色がn個連続していて、nが5以上10未満のときで判定できる。
10以上一直線に並ぶことはありえないので、かならずNOを返す。
最後に、片方が勝っていても状態がおかしいかどうかとして、
ooooo o o o ooooo
のような場合があり、ありえないのではぶきたい。
(すでに勝利しているのに手を置いていることになる)
これは、
「最後の1手」になりうる手が存在するかどうか
で判定できる。
ループを回して、勝っている方の碁石の一つを取り除いてみて、1回以上成立しない場合があればそれが最後の1手としてありえる。
しかし、どの碁石を取り除いても成立してしまっている場合はすでに勝利が確定していた場合になるので、NOを返す必要がある。