mini notes

競技プログラミングの解法メモを残していきます。

ARC012 C - 五目並べチェッカー

問題:C - 五目並べチェッカー

解答:Submission #13696167 - AtCoder Regular Contest 012

解法:いろいろな最終盤面が考えられるため、うまく場合分けをしてゆくことが必要。以下、各条件はそれより上の条件でYESNOが決まらなかったもののみ到達するものとする。

①石の個数について、先手が黒なので、「黒の個数 = 白の個数」(この場合白で終了)または「黒の個数 = 白の個数 + 1」(この場合黒で終了)でなければならない。そうでなければNO。

②終了石をlas、その一つ前の石をnlasとする。nlasの石で終了条件(石が5つ以上ならんでいる状態)を満たしているとNO。

③lasの石で終了条件を満たしていない(つまり両石とも終了条件をみたさない)場合はYES。

④ここまでくると「石の個数OK」、「nlasは終了条件を満たさない」、「lasは終了条件を満たしている」ということになる。
lasは最終盤面の1手前では終了条件を満たしていなことが必要となる。これはどれか1つのlasの石を置いていないことにして終了していない盤面が存在すればよい。これは実際に全てのlasの石で試せばよい。
この条件にて盤面の判定が完了する。