問題:A - 一次元オセロ
解答:Submission #11569003 - CODE FESTIVAL 2015 あさぷろ Hard
解法:以降、初期盤面で連続している黒または白はひとまとまりにして考える。
初期盤面をoxoxoとする。oが白、xが黒を表す。初手の黒は一番左に置くか一番右に置くかの2通り。oxoxoに対し左に黒を置くとxxxoxoとなる。2手目は白を置くが一番左に置くしかなく、ooooxo。3手目の黒は一番左に置くか一番右に置くかの2通り。左に置くとxxxxxxo。4手目の白は一番左に置くしかなく、ooooooooとなりゲーム終了。
上記より、黒は左に置くか右に置くかの選択肢があるが、白は直前に置いた黒と同じ方向にしか置けない。また、上記の場合一番右の白は全くひっくり返ることはない。
それぞれの手の選び方により、初期盤面のうち全くひっくり返らない白が1部分のみ存在する。また、その場合他の石がひっくり返る回数は手の選び方によらない。よって、ひっくり返らない白を全て試せばよい。