No.2035 Tunnel
タグ : / 解いたユーザー数 120
作問者 :
milkcoffee
/ テスター :
nok0
riano
問題文
$N$ 個のマスが一直線に並んでいます。マスには $1$ から $N$ まで番号が割り当てられており、各マスには高々 $1$ つの駒が置かれています。
最初の各マスの情報は文字列 $S$ で与えられ、$S_i=$ # のときはマス $i$ に駒が $1$ つあること、$S_i=$ . のときはマス $i$ に何もないことを表します。
駒の置かれているマスが少なくとも $1$ つ存在することが保証されます。
あなたは魔法を繰り返し使うことで、マス上にある全ての駒を取り除きたいです。
魔法を $1$ 回使うと、マス上の駒は以下のような規則で一斉に移動します。
- マス $N$ にある駒は取り除かれる。
- マス $i$ ($1 \leq i \leq N-1$)にある駒は、 魔法が使われる直前にマス $(i+1)$ に駒がないときに限りマス $(i+1)$ に移動する。そうでない場合は動かない。
入力
$N$ $S$
- $1 \leq N \leq 3 \times 10^5$
- $N$ は整数である
- $S$ は
#か.からなる長さ $N$ の文字列 - $S$ は
#を $1$ つ以上含む
出力
全ての駒が取り除かれるのは魔法を何回使ったときかを整数で出力してください。
サンプル
サンプル1
入力
3 ##.
出力
4
##. (最初):マス $1$ とマス $2$ に駒が $1$ つずつある。
#.# ( $1$ 回目):マス $2$ にあった駒はマス $3$ へ移動する。マス $1$ の駒は移動しない。
.#. ( $2$ 回目):マス $3$ にあった駒は取り除かれる。マス $1$ にあった駒はマス $2$ へ移動する。
..# ( $3$ 回目):マス $2$ にあった駒はマス $3$ へ移動する。
... ( $4$ 回目):マス $3$ にあった駒は取り除かれる。このとき全ての駒が取り除かれたことになる。
サンプル2
入力
5 ....#
出力
1
$1$ 回目の魔法でマス $5$ の駒が取り除かれます。
サンプル3
入力
8 #.##..##
出力
9
#.##..## (最初)
.##.#.#. ( $1$ 回目)
.#.#.#.# ( $2$ 回目)
..#.#.#. ( $3$ 回目)
...#.#.# ( $4$ 回目)
....#.#. ( $5$ 回目)
.....#.# ( $6$ 回目)
......#. ( $7$ 回目)
.......# ( $8$ 回目)
........ ( $9$ 回目)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。