Document

Nagashi Soumen
原案: 林崎
解答作成: 野田、林崎
英文: 八森
解説: 林崎
問題 (1)



夏なので流しそうめんをすることにしました
N人の参加者が三次元空間上の点
(xi,yi,zi) (1<i≦N) にいます
各々の参加者の所を
どれか一つの樋が通るように、
最大K本の樋を設置したい
問題 (2)

樋の設置には条件がある
□ 高さが単調減少
□ 枝分かれ・合流はナシ
□ 任意の形状に曲げられる


樋の長さの最小値を求めよ
N≦100, K≦4
解法


最短の時の樋は、誰かの所で開始し、
途中の参加者の間を直線でつなぎ、
誰かの所で終止する
ダメな解法例
□ 全探索
□ N人それぞれの所をどの樋が通るか、
のパターン(KN通り)を全列挙
□ どう見てもTLEです
想定解法 (1)

DP
□ 参加者をZ座標でソートしておく
□ 低い方から順に追加していく
□ i人目を樋kの一番上に追加した時の
樋の長さの合計値は、(追加前)
+ (i人目と樋kの一番上だった人との距離)

各樋の一番上の人以外はどうでもいい
□ 各樋の一番上の人、をステートとしたDP
想定解法 (2)

DP(a,b,c,d) (K=4の場合):
□ 各樋の一番上の人の番号がa,b,c,d
誰も属していない(樋が未設置)の場合は -1
 樋の順番は関係ないので、
a>b>c>d などとして正規化

□ a番以下の人の分は樋が設置済み
□ その場合の樋の合計長の最小値
想定解法 (3)

初期値
□ DP(-1,-1,-1,-1)

= 0, それ以外はinf
更新
□ i人目の追加の時には:

各(i-1,b,c,d)について:
• DP(i,b,c,d)=
min(DP(i,b,c,d), DP(i-1,b,c,d)+dist(i,i-1));
// 1番目の樋にi人目を追加する場合
• 2,3,4番目の樋についても同様
想定解法 (4)

細かいこと
□ Z座標が同じ人をつないではいけません

水平の樋は不可です
□ 樋は垂直になることがあります
□ 樋は全部使わないことがあります
想定解法 (5)

計算量
□ ステート数は NCK

個くらい = 4M個くらい
未使用樋が存在するので実際はもう少しだけ多い
□ 各ステートごとにO(K)の処理なので
全体の計算量はO(K*NCK)=16Mくらい
想定解法 (6)

実行時間
□ ジャッジの解答プログラム:
100人4樋、全参加者のZ座標が異なるデー
タで2～10秒 @ Core Duo 1.66GHz
□ DP表をmap<vector<int>,double>で
実装すると定数倍遅くなりTLEしました

Download Report