問題一覧 > 通常問題

No.2035 Tunnel

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 135
作問者 : milkcoffee / テスター : nok0 riano
お気に入りにしたユーザー ProblemId : 7823 / 自分の提出
問題文最終更新日: 2022-08-09 18:14:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 356 (順位表) の他の問題:

Problem Statement

There are $N$ squares arranged in a straight line. The squares are numbered from $1$ to $N$, and each square holds at most $1$ piece.
The initial state of the squares is given by a string $S$: $S_i=$ # means that square $i$ has $1$ piece, and $S_i=$ . means that square $i$ is empty.
It is guaranteed that there exists at least $1$ square with a piece on it.

You want to remove all the pieces from the squares by repeatedly using magic.
Each $1$ use of the magic moves the pieces on the squares simultaneously according to the following rules.

  • The piece on square $N$ is removed.
  • A piece on square $i$ ($1 \leq i \leq N-1$) moves to square $(i+1)$ only if square $(i+1)$ has no piece immediately before the magic is used. Otherwise, it does not move.
After how many uses of the magic are all the pieces removed?

Input

$N$
$S$

  • $1 \leq N \leq 3 \times 10^5$
  • $N$ is an integer.
  • $S$ is a string of length $N$ consisting of # and ..
  • $S$ contains at least $1$ #.

Output

Output, as an integer, the number of uses of the magic after which all the pieces are removed.

Sample

Sample 1
Input
3
##.
Output
4

##. (initial): Square $1$ and square $2$ each have $1$ piece.
#.# (use $1$): The piece on square $2$ moves to square $3$. The piece on square $1$ does not move.
.#. (use $2$): The piece on square $3$ is removed. The piece on square $1$ moves to square $2$.
..# (use $3$): The piece on square $2$ moves to square $3$.
... (use $4$): The piece on square $3$ is removed. At this point, all the pieces have been removed.

Sample 2
Input
5
....#
Output
1

Use $1$ of the magic removes the piece on square $5$.

Sample 3
Input
8
#.##..##
Output
9

#.##..## (initial)
.##.#.#. (use $1$)
.#.#.#.# (use $2$)
..#.#.#. (use $3$)
...#.#.# (use $4$)
....#.#. (use $5$)
.....#.# (use $6$)
......#. (use $7$)
.......# (use $8$)
........ (use $9$)

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。