競技プログラミング用 知識集積所
M - Candies
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
一見、子供を1人ずつ増やしながら、飴の個数ごとの配り方を継承するだけの動的計画法。
しかし、マスの数が最大で100×10^5=10^7個あり、1つのマスを埋めるのに最大10^5個の数を足し算しないといけない。
つまり、愚直にやるとTLEする。
しかし、マスの数が最大で100×10^5=10^7個あり、1つのマスを埋めるのに最大10^5個の数を足し算しないといけない。
つまり、愚直にやるとTLEする。
ということで、最大10^5個の数を足し算をしなくて済むように、sliding window法を使う。
以上……ではあるのだが、2つのアルゴリズムのコードが絡まる都合で、実装がとてもややこしい。
以上……ではあるのだが、2つのアルゴリズムのコードが絡まる都合で、実装がとてもややこしい。
