AGC009 - B Tournament - Senの競技プログラミング備忘録

問題概要

N人の人でトーナメントして、引き分けなしの勝負をした。最終的に勝ったのは人1である。人2～人N(2 <= N <= 10^5)のそれぞれ負けた相手を与えるので、それを満たすトーナメント表を考える。その中で、トーナメントの深さが一番小さいものの深さを答えよ。

ACするまで

1. 勝った人が親になるように木構造を作ろう。
2. 親の子供の数を $n$ とすると、親は最小でも $n$ 試合をして勝つ必要がある。
3. 子供の、頂点1(最終的な勝利者は人1なので)からの距離を求めて、それが子供の必要な試合数？ -> 違う！　ここまでgdgdして1h経過
4. 頂点1からの距離は試合数に直結しない！(頂点からの距離 <= 試合数)なぜなら、子供の中でも1試合で済まないものもある。(例えば、子供が2つの孫を持ち、それぞれの孫から続く部分木が非常に長いときは、2つの孫について2試合で終わる、というわけではない！)
5. 木DPをする。
6. AC

考察

親からの深さが必要な試合数だと思えるが、ACするまでの4番のとおり、親からの深さはあくまで下から抑えられるだけで、答えとはなりえない。

経験から得られるべき、そしてだろう知見として、

dp[i] := iの頂点で勝てる試合試合を済ます、つまり人iについて勝つべき人との試合を全部消化し終えたときにかかる試合の数

とDPを組める。

この時、更新はつぎのようなルーチンで行える。

1. 自分が勝つべき相手の中で、その相手のかかる試合数が少ないものから順に試合をする。(<b>勝つべき相手のうち、かかる試合数が多いものは、その相手が彼の勝つべき相手に全員勝つまで待たないといけないため</b>、その待ち試合数を最小化する)
2. シミュレーションするにあたって、今何試合されたかの変数cntにする。
3. 試合数が少ない順に勝つべき相手と試合をする。試合相手がいる限り4と5を繰り返す。
4. もし、その時cntよりも勝つべき相手が勝てるべき試合を全部終えるまでにかかる時間が長いなら、その試合が終わるまで待つ(cntの値をdp[nxt]にする)
5. その勝つべき相手と一戦を交えるので、cnt++する。
6. cntこそが今見てる人の勝つ試合を全部終えた時のかかる試合数の最小なので、dp[cur]を更新

これを実装すれば通る。計算量は、それぞれの頂点が子供として現れるのはたかだか $O(N)$ なので、それのソートで $O(N log N)$ かかる。これが計算量のボトルネックとなってる。