All提出
https://atcoder.jp/contests/abc102/submissions?f.User=peroon
- 最後の2つの提出を見比べてみると
- どちらも2重のforなのでO(N2)に見える
- カット位置の単調増加を利用して、forの初期位置に前回のforの結果を利用
- TLEにならなくなり、通った
学び
- 単調増加の性質がないか考える。あったら利用する
- 左から右に探すことが多いので、結構見かけそう
2020/10/30
- TLEと言ってるのでEqual Cutの話だね
- https://atcoder.jp/contests/abc102/submissions/3814666
- 真ん中の切れ目全探索&左右の適切な切る位置は二分探索で直感的に良さそう
- ちゃんと証明するには公式解説放送をどうぞ