ABC469 C - Cantrip

考え方

手作業でシミュレーションしてみると何が起こるかすぐにわかる。

どれだけ当たりを引いても、手元にある袋の個数は変わらない（不変量）。
つまり、最初に $k$ 個袋を持っているなら、'x' を $k$ 個手にしたところで手元に当たりがなくなって終了。

よって、最初に $k$ 個袋を持っている場合は、前から $k$ 番目の 'x' がある位置が答え。
'x' が $k$ 個ない場合は答えは $n$。

文字列を前から見ていって、'x' の位置を配列に記録していき、長さが足りない分を $n$ で埋めればよい。

計算量は $O(N)$ である。

入力例1での動作

入力を受け取る。

n: 5
s: "oxoxo"

x は左から $2$ 文字目と $4$ 文字目にある。

最初に持つ袋の個数 $k$ ごとの答えは次のようになる。

したがって、出力する列は 2 4 5 5 5 となる。

注意点

問題文中の位置は 1-indexed だが、文字列 s の添字は 0-indexed である。
コード中で両者が入り混じるので、丁寧に確認しながら書く。

別解

特になし。