AtCoder Beginner Contest 210 [ C - Colorful Candies ]をPythonで解く(300点、⬜️灰色diff)
問題
解法
いわゆる「しゃくとり法」で解ける問題。
数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。
わけだけど、ベタに作ると計算量が多すぎる。
- 範囲の左端と右端を決定し、色数を計算。
- 色数が最大か?比較して、最大なら保存。
- 色数から左端の要素を削除して、左端を一個すすめる。
- 右端を一個伸ばして、右端の色を追加。(1と同じ処理だが2週目以降は処理が1個)
と、こんな感じで、左を1個進めて、右も1個進める。
という、しゃくとり虫的な動きで処理をする。