第一回日本最強プログラマー学生選手権 C: Cell Inversion
200位入れなかったが？俺は黄色コーダーやぞ？あ、今は青コーダーか（てへぺろ）
辛いね
問題概要
横一列に並んだ2N枚のオセロをN回区間選んでひっくり返す
区間の端はN回とも異なりちょうど全てのオセロが一回ずつ選ばれるようにする
N回の操作後オセロが全部白になってるようなひっくり返し方は何通りか
前提とか自明部分とか
操作の順番によって最終的な色が変わらないのは自明なので最初にansをN!にしておく
一回の操作で[L,R]を選ぶみたいな感じで表記する
解法
こういうのは左端から順番に決めるのが典型なのでとりあえずそれで考える
左からi個目のコマの色は自分より左でまだRを見つけていないLの数(以下 wait_L と表記）だけひっくり返されることが確定している
この時点（i番目のオセロをwait_L回ひっくり返した状態）で黒ならもう一回ひっくり返さないといけないのでi番目はLの役に、白ならもうひっくり返してはいけないのでRの役にならないといけない
今回数えるのはペアの通りなのでRになる時に wait_Lだけansにかけてあげればよい
wait_Lをi番目がRになったら-1、Lになったら+1するのを忘れない
コード
lがwait_Lの意味で使われている
12行目はxorで、偶奇問題の時に使うと場合分けをスッキリ書ける。今回だとs[i]が黒でwait_Lが偶数かs[i]が白でwait_Lが奇数ならi番目はL、それ以外ならRにするって感じ。
16行目はLとRの個数が一致しなかった場合はansは0になることを書いてる。ちなみにどこかでLよりRの方が多くなる場合は13行目によって必ずansに0がかけられるようになってる。
