IOI 2022 Day2 - Thousands Islands
概要
Author : KoD
解法
以下の条件を満たす経路を良い経路と呼ぶ。この問題は頂点$ 0を始点とする良い経路を求める問題である。
長さ$ 1以上
同じカヌーを連続して使わない
全てのカヌーを偶数回使う
始点と終点が等しい
問題文中の $ U_iを始点、$ V_iを終点とした有向グラフを$ Gとおく。以下の二つの補題を示す。
補題 1.
$ Gにおける頂点$ sの出次数が$ 1のとき次が成り立つ。
$ sを始点とする唯一の辺の終点を$ tとおくと、$ sを始点とする良い経路が存在するための必要十分条件は、$ sおよび$ sに接続するカヌーを取り除いたグラフにおいて$ tを始点とする良い経路が存在することである。
(証明) $ sを始点とする唯一の辺を$ eとおく。$ sから出発して初めて$ sに戻ってきたときに使った辺が$ eと異なるとき、$ eを奇数回しか使っていないにもかかわらずそれ以上移動できなくなる。よって初めて$ sに戻ってくるときは必ず$ eを使うので、$ sを始点とする良い経路が存在するならば$ tを始点とする$ sを通らない良い経路が存在する。逆は明らか。
補題 2.
$ Gにおける頂点$ sの出次数が$ 0のとき次が成り立つ。
$ sを始点とする良い経路は存在せず、$ sおよび$ sに接続するカヌーを取り除いても、他の頂点を始点とする良い経路が存在するかどうかは変化しない。
(証明) 明らかなので省略。
これらの補題を繰り返し用いると、より頂点数が少ない問題に置き換えていくことができる。
頂点$ 0の出次数が$ 0になってしまったら答えは$ \mathrm{false}である。そうでないとき頂点$ 0から異なる辺が$ 2本以上出ているので、そのうち$ 2つを$ e_1, e_2とおく。このとき、頂点$ 0を始点とする良い経路が存在することを示す。
補題 2. をこれ以上適用できない状態になったので、各$ k = 1, 2について、頂点$ 0を始点とし、最初に$ e_kを使い、同じカヌーを連続して使わずに頂点$ 0に戻るような経路が存在する (必ずしも良い経路でなくともよい) 。
(証明)$ u_1 \rightarrow u_2 \rightarrow \cdots と移動していき (出次数 1 以上なので必ず移動可能) 、$ u_nから移動したときに初めて到達済みの頂点$ u_mに戻ってきたとすると、$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_n \rightarrow u_m \rightarrow u_{m-1} \cdots \rightarrow u_1と移動すればよい。
経路$ u_1 \rightarrow \cdots \rightarrow u_mを$ P_k、経路$ u_m \rightarrow u_{m+1} \rightarrow \cdots \rightarrow u_n \rightarrow u_mを$ C_kとおくと、前述の移動方法は「$ P_k \rightarrow C_k \rightarrow (P_kの逆順$ )」と表せる。これを$ W_kとおく。
$ C_1, C_2が辺を共有しないならば「$ W_1 \rightarrow W_2 \rightarrow (W_1の逆順$ )\rightarrow (W_2の逆順$ )」のように移動すれば良い経路が得られる。
$ C_1, C_2が辺を共有するとき、$ C_2上を移動するときに初めて訪れる$ C_1上の頂点を$ xとして、
$ P_1 \rightarrow C_1 \rightarrow (P_1の逆順$ ) \rightarrow P_2
$ C_2上を$ xに到達するまで
$ C_1上を、$ xを始点として元々とは逆順に一周
$ C_2上を$ xから逆順に
$ P_2の逆順
のように移動すれば良い経路が得られる。
感想
複雑に見えるし、実際本番 AC が 6 人しかいない難問だが、実は比較的簡単な必要条件を列挙するだけで解けてしまう。
とてもいい問題。