C. Magic Ship (Educational Codeforces Round 60)

Quiz

https://codeforces.com/contest/1117/problem/C

Submit

https://codeforces.com/contest/1117/submission/50138888

解法

  • 二分探索
  • 日数を固定(daysとする)したとき、まず流され、そのあと移動する
  • 流された後の位置とゴールのマンハッタン距離 <= days ならたどり着ける
  • 流されるシミュレーションは累積和で高速に求めればよい

Note

  • テスト5を見ると答えがかなり大きい
  • 二分探索するときのright=1e11では小さすぎて通らず、1e14で通った
  • 答えが最大になる場合を考えてみよう
    • y = 109
    • n = 100000
    • s = "DDD... (1つだけU) ... DDD"
    • この場合、1周して1だけ近づけるので、たどり着ける日は1014日後
    • なのでそれよりも大きい値で行けるか判定し、行けないなら-1と判定すればいい

学び

  • 流されてから移動することで各操作を分離することができる
  • 各問題を見たとき、二分探索で解けないかチェックしてみる