ABC469 C - Cantrip

[river0525]

問題の感想や気づきを投稿・共有するスペースです

[sec6890]

k=1のときから順に答えよとのことなので、まずk=1から考えます。
残り食べられる個数を変数として持ちます。cntとしましょう。k=1なので初期値はcnt=1です。
食べた数は変数ansとして持ちます。最初、ans=0です。
先頭のお菓子を食べます。ansを1増やします。cntを1減らします。もしお菓子が当たりならcntを1増やします。
cnt>0である限り次々お菓子を食べていきます。cnt==0となったらそのときのansが答えです。
ではk=2はどうするか。k=1の時と比べてcntの初期値が1増えますが、
k=1のときにもう食べられなくなったところから、「実はもう1個食べられるよ」として上記処理を続ければ良いです。
k=3のときは、k=2のときにもう食べられなく（以下略）

というわけで文字列sを左から順に見ていけばよいので O(N)です。