JAG2015模擬地区予選K：Optimal Tournament
問題↓
jag2015autumn.contest.atcoder.jp
問題概要
- N人でトーナメントを行います。
- 各人には強さAiが与えられていて、iとjが戦った時コスト|Ai - Aj|が発生し、必ず強さの大きいほうが勝ちます。
- トーナメント表の深さをK以下にしたいときコストの総和の最小値を出力して下さい。
- N<=1000
- K<=50
解法
- とりあいず考えてみるとトーナメント表は強さでソートした順に並べたほうが良いことに気づく。
- すると区間DPで解けそうだと思う。
- dp[k+1][ l ][ r ] = min( l <= x < r ){ dp[k][l][x] + dp[k][x+1][r] + A[r] - A[l] };
- ところがこれはどっからどう見ても O(KN^3)である。
（本番ではここで詰みました）
Monge
- 偉大なるスパソ様の力を借りて頑張って理解する。
- 証明ができないので直感的に自分の理解したっぽいことを書いてきます。
- 今回の問題で重要なのは以下の事柄
- 任意の ( i <= j ), ( k <= l ) について
f( i, l ) + f( j, k ) >= f( i, k ) + f( j, l ) が成り立つ時 f はMongeであるという。
- (f*g)(i,j) := min{i≦s<j} { f(i,s) + g(s+1,j) } において
f と g が Monge のとき (f*g) も Monge。
つまり区間の真ん中をぶった切ってその左と右を足したもの - 2においてK(i,j) を min{i≦s<j} { f(i,s) + g(s+1,j) } を満たす sとするとK(i,j)は単調増加する。
K(i,j) <= K(i,j+1) <= K(i+1,j+1)
二次元の単調増加は左<=右,下<=上が成り立っているって感じ
- の３つよりMongeを利用してDPを高速化します。
- dp[k+1][ l ][ r ] = min( l <= x < r ){ dp[k][l][x] + dp[k][x+1][r] + A[r] - A[l] };
- とはすなわち
- (f*g)(i,j) := min{i≦s<j} { f(i,s) + g(s+1,j) }
- これを
f(i,s) = dp[k][i][s] - A[i]
g(s+1,j) = dp[k][s+1][j] + A[j]
として表すと - (f*g)(i,j) := min{i≦s<j} { (dp[k][i][s] - A[i]) + (dp[k][s+1][j] + A[j] }
- となる。
- ここで2を見ると、f と g が Mongeのとき f*g も Monge だと言っています。
- dp[k][i][i]の値は0なのでAiの値によってこの関数の値は変動します。
ところがAiに関してみても+A[k]+A[l] or -A[i]-A[j] してるだけなのでかわりません。よって不等式が=で成り立つので1を満たしこれら全部のMongeがいえます。 - Mongeが言えると3も成り立ち嬉しいことがさらに続きます。
- 命題２．Monge性の遺伝
- X(i,j) = min(i≦s<j) { X(i,s) + X(s+1,j) } + w(i,j)
- という式があったとき、関数wがmongeで単調だとXもMongeである。
- というのがありますが、今回関数wは存在しないので
任意のi,jに関して w(i,j) = 0
と考えるとMongeで単調なのは明らか。 - 命題３．Knuth-Yao speedup
- 命題3は上の条件（wがMongeで単調)を満たす時、
上のdpをO(N^2)で解ける - やったぜ
- 具体的に、dpの式をどう変えるかというと↓こんな感じ
- dp[k][i][i]=0
K[i][i]=i
dp[k+1][ l ][ r ] = min( K(l,r-1) <= x <= K(l+1,r) ){ dp[k][l][x] + dp[k][x+1][r] + A[r] - A[l] };
K[l][r] = 上記を満たす x - あれ？見る区間が代わっただけで結局計算量変わってなくね？
と思うのですが、xの見る範囲が限定されるためこれでO(N^2)になるそうです。 - 実装は普通のDPをちょっと変えるだけなので簡単。
ソースコード
感想
もんげええええええええええええええええええええええええええええええええええええええ
