F1 - Full Color[Easy]

2 secs 1024 MB

概要

ちょっと難しめの典型問題です．
特別な知識がなくても工夫をすれば解くことができます．

問題原案：@Machoniump

[Easy] にはたくさんの解法が考えられます．

想定していた模範解答は「尺取り法」です．
適切な実装を行えば同一のコードで [Easy] と [Hard] の双方に正答することができます．

尺取り法の詳細については読者様自身の学習に委ねますが，一例としていくつかの記事をご紹介します．

実は，この問題とほぼ同一の問題が過去に AtCoder にて出題されていました．
そちらもご参照ください。

ある程度の経験があれば，「尺取り法」というアルゴリズムを知らなくてもまず「区間を全探索する」という解法は思いつくはずです．
[Easy] はこれによって AC することが可能です．

[Hard] を解くためには計算量を落とす必要がありますが，「区間 $[l, r]$ と区間 $[l, r+1]$ では違いは電球一個分だけである」といったような基本的な性質に気づくことで，大幅に処理を減らすことができます．

一例をご紹介します．(本質は尺取り法そのものです．)

$l=1, r=1$ から始めて，以下の二つを順に $r > N$ となるまで繰り返します．

$r-l$ の最大値が答えになります．

実装例は「別解」を参照してください．

別解:

$\\$

最初に問題概要を聞いた時は「たぶん既出だろうな...」と思いながらも記憶にはなかったのでそのまま問題文を書いてしまったのですが，あとからちゃんと調べたところやっぱり既出だったみたいです...
典型中の典型のような問題なので大目に見てもらえると嬉しいです。。

解説が一気に雑になっているようにも見えるでしょうが，おそらくここで新たに説明するよりも既存の情報の方がより充実しているだろうという思惑によるものです。(言い訳です)

ちなみに先述した「細長いお菓子」は全く同じコードで AC できるようです。
これには流石に驚きました。