7K12 blog

猫でも分かるアルゴリズム解説

全国統一プログラミング王決定戦本戦 A - Abundant Resources

f:id:tkr987:20200803063854p:plain

https://atcoder.jp/contests/nikkei2019-final/submissions/15652985

  • 累積和にすることで区間和をO(1)で処理できる
  • 半開区間で処理することで[l, l+range)の累積和が答えになる

f:id:tkr987:20200803064535p:plain

制約から各kの答えを O(N)で処理しなければならない。例えばk=500のとき[0, 500)から[N-500, N)までの区間全て調べないといけないが、全て計算していては各kについて O(N^2)の計算量になってしまう。累積和を使うことで各区間合計が O(1)で取得できるので、各kの答えを O(N)で得ることが出来る。半開区間なので区間右端がNまで許されることに注意する。