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と判定すればいい
学び
- 流されてから移動することで各操作を分離することができる
- 各問題を見たとき、二分探索で解けないかチェックしてみる