# CODE FESTIVAL 2017 Final C - Time Gap (opens new window)
# 概要
- つの都市がある
- i番目の都市との差が個与えられる
- 時差をとする
- つの都市で2つずつのペアを作り, その最小値をsとする
- sの最大値を求めよ
# 思考
- 最小値の最大値ということで二分探索を疑う
- 何で二分探索すれば良いのか分からない
- 実験してみる
- 何も分からない
ここで30分終了
- 仕方がないので愚直解を作って投げる
- TLE (opens new window)
方針が全く立たないので解説をみる
- 問題の言い換えをすると以下のようになる
- 演習場に等間隔に24個の点が並んでいる
- 人の人をいずれかの点に配置していく
- 番目の人と番目の人の距離をとする
- 最も近い2人の距離を最大化せよ
- 天才解法だ......
- これをもとに考えて実装
- ダメ
check()
の中では~まで存在する- min(, )を考えなければならない
- 追加してAC!
# 提出
# 気づいたこと・感想
- 解説を見る前に愚直実装をすると何か見えるかも
- 今回は座標圧縮してから探索
- 入力および解の範囲を確認したほうが良い
- 時計, 円周長といった循環するものは円で考えると良い
- 関数内で範囲が変化する場合もある
- 実装前に範囲を確認した方が良い