概要
問題文 → ■
公式解説 → なさそう？（ここ の PDF にアクセスできず。）
自分の提出 → ■
解法
$O(n2^n)$ 時間解法
まずは、順位表が連長圧縮されていない場合の解法を考えます。
この場合には、トーナメント表の部分木ごとの問題を葉側から解いていく木 DP により解くことができます。
例えば、$[0, 8)$ の $8$ 人からなるトーナメントを考えましょう。これに対する最適な変更は、次のようにして調べることができます。
- $[0,4)$ 内での優勝者が、$[0,8)$ においても優勝する場合
- $[4,8)$ 内での優勝者が、$[0,8)$ においても優勝する場合
これらの場合の最適解の計算を行うためには、次の形の部分問題を扱えればよいです。
- $[0,4)$ 内での最適な順位表を、この中の優勝者がさらに順位を $0$ 個・$1$ 個上げるという前提で求める
- $[4,8)$ 内での最適な順位表を、この中の優勝者がさらに順位を $0$ 個・$1$ 個上げるという前提で求める
このようにして、ある問題が、同タイプの部分問題の計算結果から計算できるため、DP により解を計算できます。より具体的には、
- $[L,R)$ 内での最適な順位表を、この中の優勝者がさらに順位を $k$ 個上げるという前提で求めたもの：$\dp[L, R, k]$
として、小さな区間（$R – L = 1$ となる区間）から順に計算していけばよいです。$[L,R)$ としては、その部分だけでトーナメントの勝者が一意に決まるような区間（$[2^ki, 2^k(i+1))$ の形の区間）$O(2^n)$ 個が対象となり、計算量は $O(n2^n)$ となります。
$O(n^2m)$ 時間解法
$[L,R)$ 内で順位表が定数列であれば $\dp[L,R,-]$ は $O(n)$ 時間で計算できることを利用します。つまり、次のようにします。
- 求めるべきは $\dp[0, 2^n]$ である。
- $\dp[L,R]$ の計算が必要となった場合、
- 順位表が $[L,R)$ 内で定数列であればこれを $O(n)$ 時間で計算する
- そうでなければ、$M = (L+R)/2$ として、$\dp[L,M]$, $\dp[M, R]$ を再帰的に計算する
このアルゴリズムにおいて、各 $i$ に対して、$R – L = 2^i$ となる区間の計算対象が $O(m)$ 個であることから、アルゴリズム全体は $O(n^2m)$ 時間で動作することが分かります。
