Codeforces Round #628 (Div. 2) - C. Ehab and Path-etic MEXs
概要
サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。
頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をMEX(u, v)とする。
すべてのありうる(u, v)のペアについて、MEX(u, v)の値の最大値の最小化をせよ。
制約： 1 <= N <= 10^5
ACするまで
1. 最大値の最小化、二分探索か？
2. 手元でいろいろ実験をしてみると、どう置いても、任意の2辺を通るように頂点(u, v)を設定することはできるっぽい。
3. つまり、0と1の書かれた辺を1つの集合として含むような(u, v)は必ず存在する。答えの下限は2。
4. 適当なパスを選び、その通る辺の両端に0と1を置いて、2が存在しないように、残りのパスの辺の上を埋めてばよさそう
5. 実装。実装方針によって、煩雑さが違ってくる。
5. AC!
考察
手元で実験すればわかる事実として、
木の任意の2辺を通るようにパスを取ることは可能。
木は連結されてるグラフなので、その上の異なる2つの辺は、それぞれの1方の頂点からとって、もう1方の辺へたどり着ける。
というわけで、どのように配置しても、0と書かれた辺と1と書かれた辺を通るパスは存在してしまうため、MEXの最大値の下限は2である。
では、3以上になるのはどういう場合か？というと、0と書かれた辺と1と書かれた辺の間のパスに、2と書かれた辺があってしまうことで、逆に言えば2と書かれた辺さえなければMEXの最大値は2という答えになる。
枝分かれが存在する木(次数が3以上の頂点が1つ以上ある)では、次数が1の頂点から始めて、もう1つの次数が1の頂点へたどりつくパスの始まりの辺と終わりの辺に0と1を置き、その間に2以外の数字を置けばよい。
枝分かれが存在しない木は、どう置いても、次数が1の頂点間では0, 1, ..., N-2まで全部あるので、この場合はMEXの最大値はN-1になる。
後はこれを実装すればよい。
この問題のように、辺の順番が大事なタイプは、std::mapを使って、辺の両側の頂点と辺の順番を紐づけて、普通に隣接リストで持つと実装しやすい。
僕は次数が1の頂点から次数が1の頂点へのパスを1本見つけて、そこに2がないように数字を置き、残りの数字を適当に置くという実装を下。
別の実装法としては、枝分かれに相当する次数が3の頂点について、本筋から外れてる辺を1本選んで、2と数字を書き込めば、あとは本筋の始点と終点に0と1を書くだけで適当に残りのを書けば構築できる。
一言
別のことやってると急に頭から解法が出てくるもんだね。
