D - Miracle Tree 解説 by E869120
この問題も比較的難易度が高く、水色コーダーや青色コーダー、黄色コーダーの多くが苦戦したと思います。しかし、ある性質に気づけば一気に解きやすくなるタイプの問題でもあります。そこで本解説では、
- 考察 1：問題の条件の緩和（重要な性質）
- 考察 2：問題の言い換え
- D 問題「Miracle Tree」の解法
- D 問題の解法の具体例
- 読者への課題
- サンプルコード
の 6 つのセクションに分けて説明します。
1. 考察 1｜問題の条件の緩和
この問題では、次のような条件を満たす必要がありました。
条件2 すべての組 \((i, j)\) について、\(dist(i, j) \leq |E_i - E_j|\) となる。
しかし、これは以下のように言い換えても問題ありません。
条件2 \(E_{p_1} < E_{p_2} < E_{p_3} < \cdots < E_{p_N}\) とするとき、\(1 \leq i \leq N-1\) すべてについて、\(dist(p_i, p_{i+1}) \leq E_{p_{i+1}} - E_{p_i}\) を満たす。
理由 どのような \(L, R \ (L < R)\) についても \(dist(p_L, p_R) \leq dist(p_{L}, p_{L+1}) + dist(p_{L+1}, p_{L+2}) + \cdots + dist(p_{R-1}, p_R)\) を満たすため、条件2 が満たされればすべての組 \((i, j)\) について\(dist(i, j) \leq |E_i - E_j|\) となるから。
例えば下の図の場合、\(E_1 < E_4 < E_2 < E_3 < E_5\) であるため、\((i, j) = (1, 4), (4, 2), (2, 3), (3, 5)\) について \(dist(i, j) \leq |E_i - E_j|\) が満たされさえすれば良いのです。
2. 考察 2｜問題の言い換え
そこで、条件2 を満たす中で、できるだけ \(E_i\) の最大値を小さくするためにはどうすれば良いのでしょうか。値を制限ギリギリに設定するのです。つまり、以下のようになります。
条件2 + 条件 3 \(1 \leq i \leq N-1\) すべてについて、\(dist(p_i, p_{i+1}) = E_{p_{i+1}} - E_{p_i}\) を満たす。
そこで、\(E_i\) の最小値が \(1\) であることを考えると、\(E_i\) の最大値は \(dist(p_1, p_2) + dist(p_2, p_3) + \cdots dist(p_{N-1}, p_N) + 1\) となります。したがって、次のような問題に言い換えることができるのです。
ある頂点を出発し、\(N\) 頂点すべてを巡るとき、移動距離が最短となる「頂点を巡る順番」\(p_1 \to p_2 \to \cdots \to p_N\) はどのようなものか？
※この答えを \(Ans\) とすると、\(E_i\) の最大値は \(Ans + 1\) となります。
3. この問題の解法
まず、次のような有名事実があります。（木の巡回に関連します）
\(N\) 頂点すべてを巡って同じ頂点に戻ってくるためには、少なくとも合計距離 \(2(N-1)\) 必要である。
これは下図のように、同じ道を \(2\) 回通っていて、木の辺の数が \(N-1\)であることから分かります。
そこで、以下のような問題を考えましょう。
\(N\) 頂点全部を移動距離最短で巡る。ただし、頂点 \(s\) から出発し、頂点 \(t\) で移動を終了しなければならない。
これは、次のような方法により、合計距離 \(2(N-1) - dist(s, t)\) が達成できます。
- 頂点 \(s\) から深さ優先探索（DFS）をする。（初めて頂点に到達する順番は行きがけ順になる）
- ただし、頂点 \(t\) に向かう辺は、最後に探索する。
分かりやすいように例も載せておくと、下図のようになります。
\(dist(s, t)\) の最大値：木の直径を求める
最後に、\(2(N - 1) - dist(s, t)\) の最小値を計算するためには、\(dist(s, t)\) の最大値（木の直径とも呼ばれる）を求める必要があります。以下のアルゴリズムが有効です。
- 頂点 \(1\) から各頂点への最短距離を、深さ優先探索（DFS）や幅優先探索（BFS）などによって求める。
- 頂点 \(1\) からの最短距離が最も遠い頂点の一つを頂点 \(u\) とする。
- 頂点 \(u\) から各頂点への最短距離を求める。最も遠い頂点の一つを頂点 \(v\) とする。
- \(dist(u, v)\) が求める最大値である。\(dist(u, v)\) より最短距離が大きい \(2\) 頂点の組合せは存在しない。
詳しい証明については、
をご覧ください。
まとめ
最後に、出発頂点 \(u\)・終了頂点 \(v\) が求まったら、前述したように、深さ優先探索によって「\(N\) 頂点の巡回ルート」が決まります。
そこで、各頂点に書き込む整数は、次のようにすればよいです。
- \(E_i\)：頂点 \(i\) を初めて訪れた時刻
- ただし、頂点 \(u\) を出発する時刻を \(1\) とし、辺 \(1\) 本につき移動に \(1\) 単位時間かかるものとする
4. 具体例
例えば下図の場合、\(u = 9, v = 4\) で \(dist(u, v) = 6\) となり、これが最大です。
したがって、次のように巡回をすることで、書き込む整数の最大値を \(2 \times (9 - 1) - 6 + 1 = 11\) にすることができます。
5. 読者への課題
最後に、この問題に関連して、次のような問題があります。
\(N\) 頂点の木があり、\(i\) \((1 \leq i \leq N-1)\) 個目の辺は頂点 \(A_i\) と頂点 \(B_i\) を結んでいる。
コンテスタントの出力は \(E = (E_1, E_2, \cdots, E_N)\) だった。
木の情報 \(N, A_i, B_i\)、コンテスタントの出力 \(E_i\) が与えられるので、出力がこの問題の条件を満たすかどうか判定してください。
つまり、D 問題「Miracle Tree」の正誤判定ジャッジを作れますかという問題です。計算量 \(O(N \log N)\) で解くことができるので、是非考えてみましょう。
6. サンプルコード
C++ における解答例は、次の通りです。
投稿日時:
最終更新: