AOJ 1637 色の切り替え
問題
提出コード
解説見たらやっていることが少し違ったのでメモしておきます。
まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。
そして、全ての頂点を1度押すことを考えます。すると、全ての辺について、色が変わる回数は2回になります(辺に繋がっている頂点が2個なので)。
つまり、ある頂点集合について考えると、その補集合を押した時と結果は同じになります。このことから、頂点を押す、として最適解を探した時も頂点を押さない、とした時も結果は同じです。
よって、頂点は押さない、と確定させることができます。
今回作りたいのは全域木です。頂点と頂点を繋ぐ、としましょう。
頂点については押さないことが確定しているので、の辺が赤になるよう、頂点で調整をする必要があります。この時点で、の押す/押さないが確定します。
以外の頂点について見てみると、
を押す/押さないで、頂点のどちらと繋がっているかが切り替わる
を押す/押さないで、頂点の両方と繋がっている/繋がっていないが切り替わる
の2パターンに分かれます。後者については、繋がっているを選択すると、の閉路ができるので、繋がっていないを選択するしかありません。よって、このパターンについては操作が一意に決まります。
前者のパターンの頂点集合をとしましょう。
について、押す/押さないを決めてみます。すると、のそれぞれについて、と繋がっている辺が赤くなるパターンと、黒くなるパターンが、押す/押さないで決まります。赤いパターンを選択してしまうと、頂点を含んだ閉路が必ずできてしまうので、黒くなるパターンを選択するしかありません。
ここまでで、全ての頂点の押す/押さないが確定しました(が空の場合もありますが、そのときは空とわかった時点で、全ての頂点の押す/押さないが確定しています)。
あとは、押した結果グラフが全域木になっているか確認してペナルティを計算すれば良いです。
を決めるので、について押す/押さないを確認するので、押す操作を実際に行うのでで、結局です。
チェックするパートについても、全ての辺を愚直に走査すれば良いです。たかだか回しかチェックしないので、こちらもになります。
感想
昔見た時は全く歯が立ちませんでしたが、今解いたら順調に考察が進んだので面白かったです。
昔一度解説を見て感動した記憶がありますが、全然違う考察ルートを辿ったので、記憶に残っていないことがバレました。