CODE FESTIVAL 2017 Final C - Time Gap (opens new window)

概要

• $N+1$つの都市がある
• i番目の都市との差が$N$個与えられる
• 時差を$min(d, 24-d)$とする
• $N+1$つの都市で2つずつのペアを作り, その最小値をsとする
• sの最大値を求めよ

思考

• 最小値の最大値ということで二分探索を疑う
• 何で二分探索すれば良いのか分からない
• 実験してみる
• 何も分からない

ここで30分終了

• 仕方がないので愚直解を作って投げる
• TLE (opens new window)

方針が全く立たないので解説をみる

• 問題の言い換えをすると以下のようになる
  • 演習場に等間隔に24個の点が並んでいる
  • $N+1$人の人をいずれかの点に配置していく
  • $i$番目の人と$N+1$番目の人の距離を$D_i$とする
  • 最も近い2人の距離を最大化せよ
• 天才解法だ......
• これをもとに考えて実装
• ダメ
• check()の中では$0$~$24$まで存在する
• min($24-n$, $n$)を考えなければならない
• 追加してAC!

提出

• 提出 #7501474 (opens new window)

気づいたこと・感想

• 解説を見る前に愚直実装をすると何か見えるかも
  • 今回は座標圧縮してから探索
• 入力および解の範囲を確認したほうが良い
• 時計, 円周長といった循環するものは円で考えると良い
• 関数内で範囲が変化する場合もある
  • 実装前に範囲を確認した方が良い