# CODE FESTIVAL 2017 Final C - Time Gap

# 概要

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

# 思考

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

ここで30分終了

  • 仕方がないので愚直解を作って投げる
  • TLE

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

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

# 提出

# 気づいたこと・感想

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