絶滅

どうでもいい

ARC099 - C

C - Minimization

問題ページ


N = 12, K = 4 の例で考える.

f:id:my316g:20180721124804p:plain

ちょっと考えると最終的な数列は全要素 1 になることが分かる.

数列を左端から長さ K の区間を用いて一つ被るようにしながら覆っていく回数を調べる.

f:id:my316g:20180721125057p:plain

この場合は 4 回.

で,この回数が答えになる.

というのも,1 の位置がわかったら 1 が含まれる区間 (例なら緑 or 紫) に対して操作を実行したあと,両端に向かって操作を実行していけば所望の数列が得られるから.

Submission #2873687 - AtCoder Regular Contest 099

editorial にはやたら難しいこと書いてあったけど本番の考察はこんなもんで十分な気がする.