AtCoder Beginner Contest 155 F. Perils in Parallel

F - Perils in Parallel

以下は公式解説とほとんど同じですが、捉え方がすこしだけ異なります。

スイッチのオフとオンをそれぞれ0と1とします。ある範囲のスイッチを切り替えるというのは、法を2としてある範囲に1を足すことに言い換えられます。ある範囲に値を足すという操作は、階差数列の上ではある二要素に値を足すという操作に変わります。また数列のすべての要素が0であるという条件は、階差数列の要素がすべて0であると言い換えられます。このことを踏まえ、階差数列の上で議論をすることにします。

階差数列の各要素を頂点とし、この操作によって変化する二要素を辺で結んだグラフを考えます。値が1である頂点の上にコマを置くことにしましょう。このときこの操作は、頂点上のコマを隣接頂点に動かしていく操作だと捉えることができます。ただし移動先にすでにコマがある場合は、この二つは消滅するものとしてください。このように考えると、コマが消えるときはかならず二つずつ消えるので、各連結成分ごとにコマは偶数個ずつでなければならないことがわかります。一方で、偶数個であればコマを動かしていってすべてが消せるのは明らかです。具体的なやり方としては、各連結成分に対して適当な全域木を作り、コマを根に向かって持ち上げていくというのがあります。

類題があります。