ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 1637 色の切り替え

問題
提出コード
解説見たらやっていることが少し違ったのでメモしておきます。

まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。
そして、全ての頂点を1度押すことを考えます。すると、全ての辺について、色が変わる回数は2回になります(辺に繋がっている頂点が2個なので)。
つまり、ある頂点集合Sについて考えると、その補集合を押した時と結果は同じになります。このことから、頂点1を押す、として最適解を探した時も頂点1を押さない、とした時も結果は同じです。
よって、頂点1は押さない、と確定させることができます。
今回作りたいのは全域木です。頂点1と頂点yを繋ぐ、としましょう。
頂点1については押さないことが確定しているので、(1,y)の辺が赤になるよう、頂点yで調整をする必要があります。この時点で、yの押す/押さないが確定します。
1,y以外の頂点xについて見てみると、

  • xを押す/押さないで、頂点1/yのどちらと繋がっているかが切り替わる

  • xを押す/押さないで、頂点1,yの両方と繋がっている/繋がっていないが切り替わる

の2パターンに分かれます。後者については、繋がっているを選択すると、1-x-y-1の閉路ができるので、繋がっていないを選択するしかありません。よって、このパターンについては操作が一意に決まります。
前者のパターンの頂点集合をA = \{a,b,c,\ldots\}としましょう。
aについて、押す/押さないを決めてみます。すると、b,c,\ldotsのそれぞれについて、aと繋がっている辺が赤くなるパターンと、黒くなるパターンが、押す/押さないで決まります。赤いパターンを選択してしまうと、頂点1,yを含んだ閉路が必ずできてしまうので、黒くなるパターンを選択するしかありません。
ここまでで、全ての頂点の押す/押さないが確定しました(Aが空の場合もありますが、そのときは空とわかった時点で、全ての頂点の押す/押さないが確定しています)。
あとは、押した結果グラフが全域木になっているか確認してペナルティを計算すれば良いです。
yを決めるのでO(N)Aについて押す/押さないを確認するのでO(N)、押す操作を実際に行うのでO(N)で、結局O(N^{3})です。
チェックするパートについても、全ての辺を愚直に走査すれば良いです。たかだかO(N)回しかチェックしないので、こちらもO(N^{3})になります。

感想

昔見た時は全く歯が立ちませんでしたが、今解いたら順調に考察が進んだので面白かったです。
昔一度解説を見て感動した記憶がありますが、全然違う考察ルートを辿ったので、記憶に残っていないことがバレました。