ABC469 C - Cantrip

魔法の呪文

考え方

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

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

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

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

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

入力を受け取る。

n: 5
s: "oxoxo"

文字列を左から調べ、x が現れる位置を 1-indexed で result に入れる。

x は左から $2$ 文字目と $4$ 文字目にあるので、次のようになる。

result: {2, 4}

result の要素数が $N$ 個になるまで、最後の位置を表す $5$ で埋める。

result: {2, 4, 5, 5, 5}

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

特になし。