review-H

Problem H
Get out!
オリジナル問題
作成者：三廻部大
問題の概要
 ある点から円を避けながら直線に進む
 ある関数でコストが決まる
 円への最近点でコストがかかる
 コストをできるだけ小さくしたい
 角度差の最小は 10^-5
一大事件発生 (1)
 状況説明
 残り時間1時間半ごろ
 皆あまり解けていない
 E, F, Hは解く人いないだろうなぁ
Problem Hｷﾀｰｰｰｰ(ﾟ∀ﾟ)ｰｰｰｰｰｰｰ
一大事件発生 (1)
 状況説明
 残り時間1時間半ごろ
 皆あまり解けていない
 E, F, Hは解く人いないだろうなぁ
 その名はponzu !!!
一大事件発生 (2)
 実行すると Wrong Answer
 ガックリ…
 出力を見てみる.
0.1000.100-1.000-1.000302.0000.000…
一大事件発生 (3)
 出力を見てみる
 0.1000.100-1.000-1.000302.0000.000…
 改行がない!!!
0.100
0.100
-1.000
-1.000
302.000
0.000
….
0.100
0.100
No way to escape
No way to escape
302.000
0.000
…
-1はNo way to escapeだよぉ
アルゴリズムの説明
 Ponzuの解はそれ以外は完璧！
 というわけで, せっかくなのでアルゴリズムの
説明をよろしくお願いします
サンプルインプット
ジャッジより (1)
 問題の解釈はそれほど難しくない
 数式の意味するところが難しいけど
 やることも見えてくる
 ぶつからないところについて調べる
 あるところで脱出できれば, 改善していく
 与えられたコストの関数は凸
 だけど, 図形だから避けた？
ジャッジより (2)
 解法は？
 ぶつからない区間を求める
 これは問題Cとほぼ同じやりかた
 区間の中で解を探索
 二分探索, 黄金分割法
 モンテカルロ？
 もちろん, 駄目.
 10^-5単位で調べるのは無理.
 できないように, ジャッジデータ作ってますから. 残念
実際のジャッジデータ
0.000012度
左の図を,
- 90度
- 180度
- 57.2957795度 = 1rad
- 1.5rad
- 1.33333rad
回転
コスト0にはならない

Download Report