単調増加を見抜いてしゃくとり方をするとO(N^2) -> O(N)になった

atcoder

All提出

https://atcoder.jp/contests/abc102/submissions?f.User=peroon

  • 最後の2つの提出を見比べてみると
  • どちらも2重のforなのでO(N2)に見える
  • カット位置の単調増加を利用して、forの初期位置に前回のforの結果を利用
  • TLEにならなくなり、通った

学び

  • 単調増加の性質がないか考える。あったら利用する
    • 左から右に探すことが多いので、結構見かけそう

2020/10/30