perogram

C. Candies! 〜最後の状態だけが欲しい〜

Quiz

https://codeforces.com/contest/1189/problem/C

AC Code

https://codeforces.com/contest/1189/submission/56582743

観察

  • クエリ数が多いので、1クエリあたりO(1), O(logN)あたりで解かないと間に合わない
  • 愚直にシミュレーションしたら間に合わない
  • 途中の結果は不要で、最後の結果だけ欲しい
  • シミュレーションしたとして、どこかの段階で左右の和が10を超えたらキャンディが+1
  • その時、全体からは、数字が10減る

解法

  • 範囲和 / 10 が答え
  • 範囲和は累積和を持っておけばO(1)で求まる

ポイント

  • 最後の結果だけが欲しい場合、初期状態のみからO(1)で求まることがある