The Extreme Slalom

The Extreme Slalom
牟田、松崎、野田、泉
問題の成績
• サブミット数：0
• アクセプト数：0
– 入力時間：2006/10/16 22:25←予想通りでした
• この問題の作成方針が最終防衛ラインという
設定なので、まぁしょうがないかな、でも最後
に差をつけてトップを取るために読んではお
いてね。
問題の概要
• 入力：線分の列 {L1,L2, … Ln}
– ただし線分同士が交差することはない
• 出力：指定された順序で線分を通る最短距離
– 赤：サンプル例
– 青：最短パス
この長さを出力
２
１
４
３
問題の解法
• 解析解法
• 近似解法
解析解法（通過する点）
• 最短経路のパスにおいて、最初と最後の線
分以外の端点以外で直進と反射以外の形で
折れ曲がらない
– 証明概要：最短パスが端点以外で直進と反射以
外の形で折れ曲がると仮定するとより短いパス
が存在（実は交差がないという条件も必要）
青：最短
赤：非最短
解析解法（始点／終点）
• 最短経路のパスにおいて、最初と最後の線
分で端点以外で垂直ではなく斜めに交わるこ
とはない
– 証明概要：最短パスが端点以外で斜めに交わる
と仮定するとより短いパスが存在
（実は交差がないという条件も必要）
青：最短
赤：非最短
解析解法（アルゴリズム）
• 結局端点 or 直進 or 反射 or 垂直のどれか
• どの端点を通るか全探査＆
どう反射するか全探査
• あとはその長さの中で最短パスを調べる
（DPを使えば効率的に計算可能）
近似解法（１）
• とりあえず線分の中点を結ぶ
• 適当に折れ線になっている（垂直以外で終わ
る）箇所を見つけ直線化して短くする
• 停止するまで続ける
近似解法（２）
• それぞれの線分上に５点とる
• その離散点上で最短パスを求める
• 最短パスの両側の点までに線分を短くする
– 以上手順を再帰的に適応
図形問題について
• 解析解法は２００行程度
• 近似解法は１００行程度
• 近似解法は実は書くことは簡単
• 関数がどのような形になっているか
– 今回は凸性のため近似が可能でした
• 近似できるかどうかを見切れ！

Download Report