2010年 春合宿 2日目 「地域 (Regions)」

Report
2010/03/21 国立オリンピック記念青少年総合センター(JOI 春合宿)
地域 (Regions)
秋葉 拓哉
問題概要
• 辺に長さのついた木が与えられる
• 頂点を M 個のグループに分ける
• 各グループの直径の最大値を最小化せよ
元の木
M = 2 の場合
M = 3 の場合
最初の考察
M 個に分ける = M-1 本の辺を切る
部分点
点
20
40
N
1000
30000
M
2
2
100
30000
30000
• M = 2 とは,辺を 1 本だけ削除する場合
木の直径 (1/6)
• 木が与えられて,直径を計算する方法
– 辺の削除などはまだ考えない
• まず,適当な頂点を根にする
– 再帰的に計算する
木の直径 (2/6)
• 頂点 v 以下の部分木での直径 dia(v)
1. 頂点 v を通らない
2. 頂点 v を通る
木の直径 (3/6)
1. その頂点を通らない
– v の各子ノード x について
– dia(x) は dia(v) の候補
木の直径 (4/6)
2. 頂点 v を通る
– 頂点 v の各子 x, y について
– wv,x + len(x) + wv,y + len(y)
• len(v) = v 発 v 以下の最長経路
– 頂点 v の各子 x について
– len(v) = max x { wv,x + len(x) }
木の直径 (5/6)
• 動的計画法
– 頂点 v 以下の最長の経路 len(v)
– 頂点 v 以下の部分木での直径 dia(v)
len(v) = max x { wv,x + len(x) } ( x は v の子)
dia(v) = max {
max x, y { ( wv,x + len(x) ) + ( wv,y + len(y) ) }, ( x, y は v の子,x ≠ y)
max x { dia(x) } ( x は v の子)
}
O(N) で計算できる
木の直径 (6/6)
• 別の方法
1. ある頂点から最も遠い頂点 a を探す
2. 頂点 a から最も遠い頂点 b を探す
3. 頂点 a, b 間の距離が直径
• これでも O(N)
20 点の解法
• M = 2 なので,辺は 1 本しか切らない
• 全部の辺について,切断を試す
– ある辺を切った際にできる 2 つのグループの
直径を毎回求める
• O(n2) なので,n ≦ 1000 ならば間に合う
40 点の解法 (1/2)
• 解について二分探索をする
– 直径 D 以下の 2 つのグループに出来るか否か
を判定する問題に帰着
• 答えを x 以下にできれば,x < y なる y につ
いて,y 以下にもできる
– という性質から,二分探索ができる
40 点の解法 (2/2)
• 先程の DP を行う
– ある頂点 v で dia(v) > D となってしまうなら,v に繋が
る辺をどれか切る必要がある
– この際に, wv,x + len(x) が最も大きい x に繋がる辺を切
れば良いことが示せる
• 切断したら,残りの直径も求めて判定
– O(N log(答えの範囲) )
40 点の別解
• 動的計画法を頑張ると O(N)
– 複雑
• 直径となる経路に沿った DP で O(N)
– 切られる辺は必ず直径となる経路に含まれる
– 直径の DP をこれに沿って 2 方向に行う
100 点の解法
• 40 点の解法と同様に,二分探索 + DP
• 辺を切った後に,DP を続ける
– 切断した回数を数える
– 切断した回数 ≦ M - 1 であれば,OK

similar documents