perogram

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

提出

atcoder.jp

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

学び

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