2015 JAG Regional J : Longest Shortest Path
原案出しました。
この問題は考察が非人道的ですが、壁を突破した後にたどり着く解法は美しいものです。
今回は感想や小話を書いたり、中の人の議論ページにあるのをちょっと編集して貼り付けます。
感想や小話
解法を知りたい人はもう少し下を眺めてください
提案直前
- モチベーションとして、LP双対をとる問題を作りたかった
- 手本ポジションにHow to create a good gameという問題があるので、この問題と似たような状況で双対とって遊んでいれば面白そうなので遊ぼうとなる
- できた
- 下記解法(1)が見えたのでとりあえずMi_Sawaさんに相談
- 確かに双対をとった結果は同じということを確認し、解法(2)とかで解けますねーみたいな話をされる
- これはちゃんと理解できていなかったのでとりあえずそっちはMi_Sawaさんに任せることにする
- 簡単な例題を解いて照合するうちに変数yが1/nばかりをとることに気づく。
- これに沿って変形することで費用流一回で解けそうな何か(3)が錬成された
- Mi_Sawaさんに投げるとしばらくしたら証明してくれた。さすが。
8月
作問準備
- C++では下記(1),(2),(3)の解法はAtCoder上で通った。それぞれ(5sec, 5sec, 0.1sec)
- 妙に辺数が多いのはSimplex法( algorithm/SimplexMethodLP.cc at master · spaghetti-source/algorithm · GitHub)が思いのほか高速だったため。
- M=1000程度でも下手すると通るのではぐらい速度。Simplex法恐ろしい
- という事情でM=2000.
- ここまでやるとようやく30秒では終わらなくなったので呪縛から逃れる。
- その代償として、c,dの最大値を極限まで減らした。
- これはパス反復法の理論計算量を考えた時に、制約最大値を代入をしてもそこそこ信用できる程度の量にするため。
- ちなみに代入すると4億でした。実際には0.1secで終了します。
- このギャップを埋める入力は良く知らないので詳しいことをご存知の方は教えてください。
議論ページの解法などまとめ
貪欲っぽいのを落とす入力
4 5 L 1 4
1 2 2 2
1 3 4 4
2 3 1 1
2 4 4 4
3 4 2 2
L=1の場合、最適値は6. 2->3の辺の長さを1増やす
L=2の場合、最適値は6+1/3. 1->2と3->4の辺の長さに1/3足して2->3に2/3足す
L=5の場合、最適値は7+1/4. 1->2と3->4の辺の長さに5/4足す
このように、ある辺を一旦増加させても、Lを増やせば減少させる方がよいケースがある。
なので、そのような仮定に基づくアルゴリズムは落とされる。
これをある程度突破できる嘘解法はある?
解法
この問題で求めたいのは max_x min (辺にxの距離を足したs-tパス長)。
とりあえずmin...に対して双対をとるといわゆる牛ゲーになり、全体としてmaxだけでかける
(P1)
max p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0
さらに双対をとる
(P2)
min (sum d_e f_e) + y L
s.t. fはs->tに1流れるような流量保存則を満たす
c_e y - f_e >=0
f_e, y>=0
これでほぼ最小費用流の形が出る。
ここからいくつかの方針が考えられる。
(1) (P2)のyを固定したときの最適値をg(y)とおけば、
元の問題がLPであることを考慮すればg(y)は凸関数。
また、g(y)は最小費用流で求められる。 ~
最適解は0 < y <= 1に入ることを確認してから(これは証明の意味で。実際y=1であればもとの最短長に+Lする状況になるので、それは長すぎる。)三分探索をする。
(2)
ここの欄はMi_Sawaさんが書いてくれる予定です -> 詰めきったら (3) と同じになりました... (途中で考察を止めるといちおう少し違う形になるので書いておきます)
(P1)
max. p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0
であった.
答えの値を T 以上にできるかで二分探索することにすると,
(P1')
max. 0
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
p_s - p_t <= T
x_e >= 0
を得る. sum c_e x_e <= L を満たせるかで判定問題にすることにして,
(P1'')
max. -sum c_e x_e
s.t. p_u - p_v <= d_e + x_e ... 双対変数 f_e
p_s - p_t <= T ... 双対変数 α
x_e >= 0
と -L との大小を比較し, -L 以上な最大の T をとればよい.
双対をとると,
min. -αT + sum f_e d_e
s.t. f : s-t に α 流れるフロー
0 <= f <= c
0 <= α
だから, 容量 c, コスト d のグラフで, 単位流量あたりにコストが T 以下である間フローを流し,
(フローのコスト) - (フロー量)*T と -L との大小を比較すればよい.
この時の (flow, cost) は, CostPerformanceFlow の時の折れ線の折れている部分になる.
(flow, cost) な点で cost - flow * T を -L 以上にできるのは, T <= (cost + L) / flow のとき.
よって, 各点で min((cost+L)/flow, s-t shortest path) を取り, その max が答え.
さらに詰めると, 結局とこはるさんのと同じになる.
(3)
(P2)が出たところからさらに考察を進める。
yを 1/mで置き換え、f_eをf_e/mで置き換える。
これを整理すると
(P3)
min (sum d_e f_e + L) / m
s.t. fはs->tにm流れるように流量保存則を満たす
c_e >= f_e
f_e >= 0 , m > 0
f(m) := ((P3)の条件でのmin (sum d_e f_e + L) の値)とおけば
これはm流す最小費用流の最適値にLを足したものなので、区間で線形に増える。
したがって、f(m)が線形で増える区間[l,r]でf(m)=am+bであったとすると
f(m)/m = a + b/mより、最小値をとるとすれば端点(m=l,r)である(m=0はムシ)
なので、折れ線の端点のみの結果を見て比較すればよいので次をすればよい。
- 容量c, コストdの最小費用流に対する最短路反復法(Primal Dual)を走らせる
- 1反復ごとに(P3)の目的関数値をチェック
- それらの最小値が答え
その他
- この問題のおもしろいところは、
(3)の解法で出てくるグラフの容量は元のグラフのコストとなり、コストは元のグラフの距離となり、
逆のように感じるような設定になっているところ。
- 春コンのCost Performance Flowと似てる部分がそこそこある?
- ぱっと見て最短路反復法と思える人はいるか?いるとすればどのくらい思いつきやすいか?
- GCJ WF 2015 D にて類似の問題が出題されました(https://code.google.com/codejam/contest/5224486/dashboard#s=p3 )が、解説映像を見る限り少し違う方針に見える
- 公式analysisはまだ(9/15) : https://code.google.com/codejam/contests.html
- 準急さんが卒業してから出題するという説?