問題一覧 > 通常問題

No.2035 Tunnel

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : milkcoffeemilkcoffee / テスター : rianoriano nok0nok0
8 ProblemId : 7823 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-09 18:14:49

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。