人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder Beginner Contest 210 [ C - Colorful Candies ]をPythonで解く(300点、⬜️灰色diff)

問題

atcoder.jp

解法

いわゆる「しゃくとり法」で解ける問題。
数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。
わけだけど、ベタに作ると計算量が多すぎる。

  1. 範囲の左端と右端を決定し、色数を計算。
  2. 色数が最大か?比較して、最大なら保存。
  3. 色数から左端の要素を削除して、左端を一個すすめる。
  4. 右端を一個伸ばして、右端の色を追加。(1と同じ処理だが2週目以降は処理が1個)

と、こんな感じで、左を1個進めて、右も1個進める。
という、しゃくとり虫的な動きで処理をする。

実装

参考

uchidama.hatenablog.com