Skip to content
Sign in

往復すごろく (Round Sugoroku)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

JOI 高校の葵は新しいすごろくを購入した．このすごろくは \(N+2\) 個のマスが横一列に並んだ形をしている．これらのマスには，左端のマスから右端のマスへと順に，\(0\) から \(N+1\) までの番号がついている．初め，マス \(0\) とマス \(N+1\) には X が，マス \(i\) (\(1 \leqq i \leqq N\)) には \(S_i\) が書かれている．ただし，\(S_i\) は文字 . または # である．

葵はこのすごろくと \(1\) つの駒を使って遊んでいる．初め，駒はマス \(A\) (\(1 \leqq A \leqq N\)) に右を向いた状態で置かれている．ただし，\(S_A\) は文字 . である．葵は \(1\) 秒経つごとに，駒を向いている方向へ \(1\) マス移動させる．

このすごろくには次のようなルールが設定されている．

  • X が書かれたマスに駒が乗ると，駒の向きは反転する．
  • . が書かれたマスに駒が乗ったとしても，何も起こらない．
  • # が書かれたマスに駒が乗ると，駒の向きは反転する．このとき，このマスに書かれた文字を . に変更する．したがって，その後はこのマスに駒が乗ったとしても向きは反転しない．

なお，駒の反転や文字の変更にかかる時間は無視できる．

すごろくと駒の初めの状態が与えられたとき，# が書かれたマスがすべてなくなるまでに要する時間を求めるプログラムを作成せよ．

Constraints

  • \(2 \leqq N \leqq 200\,000\)．
  • \(1 \leqq A \leqq N\)．
  • \(S_i\) は文字 . または # である (\(1 \leqq i \leqq N\))．
  • \(S_A\) は文字 . である．
  • \(S_i\) が文字 # であるような \(i\) (\(1 \leqq i \leqq N\)) が少なくとも \(1\) つ存在する．

Subtasks

  1. (\(40\) 点) \(N \leqq 3\,000\)．
  2. (\(60\) 点) 追加の制約はない．

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(A\)
\(S\)

ただし，\(S\) は長さ \(N\) の文字列で，その \(i\) 文字目 (\(1 \leqq i \leqq N\)) は \(S_i\) である．

Output

標準出力に，# が書かれたマスがすべてなくなるまでに何秒かかるかを \(1\) 行で出力せよ．

Examples

Sample input 1
7 3
.#.#..#
Sample output 1
8

時間が経過するにつれてすごろくの状態は次のように変化する．ただし，右向きの駒が置かれたマスを >，左向きの駒が置かれたマスを < で表す．

  1.  X.#>#..#X
  2.  X.#.<..#X
  3.  X.#<...#X
  4.  X.>....#X
  5.  X..>...#X
  6.  X...>..#X
  7.  X....>.#X
  8.  X.....>#X
  9.  X......<X

したがって，\(8\) 秒で # が書かれたマスがすべてなくなるので，\(8\) を出力する．

Sample input 2
4 1
.#.#
Sample output 2
7

時間が経過するにつれてすごろくの状態は次のように変化する．

  1.  X>#.#X
  2.  X.<.#X
  3.  X<..#X
  4.  >...#X
  5.  X>..#X
  6.  X.>.#X
  7.  X..>#X
  8.  X...<X

したがって，\(7\) 秒で # が書かれたマスがすべてなくなるので，\(7\) を出力する．

Sample input 3
6 6
#####.
Sample output 3
35

Notes

JOI 2021 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source