AtCoder Regular Contest 155 C - Even Sum Triplet
考えたこと
各操作についてその操作を打ち消すような逆の操作ができるため
A, Bをそれぞれ操作して同じ列を作れるか判定する問題だと思っていい
まず、ABをソートしても一致させられない場合はNo
1が2個か、0が3つの時に並び変えられるので
00100のように1が孤立しているとつらそう
1をまとめたい
1をまとめられるかを考える。
どちらも1についての操作ができない場合は、長さが3以上の0の列についてA, Bをsortして一致するかを判定。
どちらか片方だけ1の操作が出来る場合はおかしいのでNo(1の操作は途中で出来なくなることはない)
どちらも1の操作ができる場合、
1を二つ並べて近くの1のところまで動かしていくと111が作れる
111は工夫することでスライドさせていく事が出来、またその中の一つを切り離すことができる。
よって以下の方法で中央に1をまとめることができる
11を左右に動かして111の状態を作り、111の状態で真ん中まで戻る。
以後同様に左右の1を11を使って取りに行き111の状態で真ん中まで戻る
あとは、中央にまとまった1を左に動かしてやることで1をすべて左に寄せることができる。
また、1が2つ以上並んでいて、0が一つ以上列に存在する場合
1をソートすることができる
例えば、i, i+1をソートしたい場合、iの近くに0を持ってきてやればいい。
0については個数が3以上の場合ソートでき、二つの場合はソートできない
よって0が3つ以上ある場合は、一致させることができ
0が2つ以下の場合は0の順序があっていれば一致させられる
