Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
すぬけ君は、一列に並んだ無限個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ整数が振られていて、任意の整数 i についてマス i と マス i+1 は隣り合っています。 また、それぞれのマスは白か黒で塗られています。
この盤面のマスの色は、長さ n の w
, b
からなる文字列 s によって以下のように表されます。
- i = 1, 2, \dots, n について、s の i 文字目が
w
であるときマス i は白色であり、b
であるときマス i は黒色である - i \leq 0 について、マス i は白色である
- i > n について、マス i は黒色である
すぬけ君は白いコマと黒いコマをそれぞれ無限個持っています。すぬけ君は次の手順でこれらのコマを盤面に置いていきます。
- (1) 好きな色のコマを選ぶ
- (2) すでにコマが置かれているマスと隣り合ったマスのうち、選んだコマと同じ色の空きマスを探す
- (2a) そのようなマスが存在する場合、そのうちひとつを選びコマを置く
- (2b) そのようなマスが存在しない場合、 選んだコマと同じ色の空きマスをひとつを選びコマを置く
最初、盤面にコマは置かれていません。
長さ n の o
, _
からなる文字列 t が与えられます。マス 1,..,n のうち、t の i 文字目が o
であるマス i すべてにコマを置くためには、最小でいくつコマを置く必要がありますか?
t が 1 文字以上の o
を含むことが保証されます。
制約
- 1 \leq n \leq 10^5
- |s| = |t| = n
- s は
w
とb
のみからなる - t は
o
と_
のみからなる - t は
o
を 1 文字以上含む
入力
入力は以下の形式で標準入力から与えられる。
n s t
出力
すぬけ君が置く必要のあるコマの数の最小値を出力せよ。
入力例 1
3 wbb o_o
出力例 1
2
コマを置かなくてはならない白マスと黒マスをそれぞれ W
と B
で表して、
コマを置かなくてもよい白マスと黒マスをそれぞれ w
と b
で表すことにします。
盤面は次のようになります。
...wwwwwwWbBbbbbb...
次の順番で置くと 2 回で条件を満たせます。
...wwwwwwWbBbbbbb... 2 1
先に白マスに駒を置くと 3 回以上の操作が必要になることに注意してください。
...wwwwwwWbBbbbbb... 123
入力例 2
4 wwww o__o
出力例 2
3
次の順番で置くと 3 回で条件を満たせます。
...wwwwwWwwWbbbbb... 1 32
入力例 3
9 bbwbwbwbb _o_o_o_o_
出力例 3
5
次の順番で置くと 5 回で条件を満たせます。
...wwwwwbBwBwBwBbbbbbb... 12 3 4 5
入力例 4
17 wwwwbbbbbbbbwwwwb __o__o_o_ooo__oo_
出力例 4
11
Score : 900 points
Problem Statement
Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer i, Square i and Square i+1 are adjacent. Additionally, each square is painted white or black.
A string s of length n consisting of w
and b
represents the colors of the squares of this board, as follows:
- For each i = 1, 2, \dots, n, Square i is white if the i-th character of s is
w
, and black if that character isb
; - For each i \leq 0, Square i is white;
- For each i > n, Square i is black.
Snuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:
- (1) Choose a piece of the color of his choice.
- (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.
- (2a) If there are such squares, choose one of them and put the piece on it;
- (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.
The board initially has no piece on it.
You are given a string t of length n consisting of o
and _
. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square i among Squares 1,..,n such that the i-th character of t is o
.
It is guaranteed that t has at least one occurrence of o
.
Constraints
- 1 \leq n \leq 10^5
- |s| = |t| = n
- s consists of
w
andb
. - t consists of
o
and_
. - t has at least one occurrence of
o
.
Input
Input is given from Standard Input in the following format:
n s t
Output
Print the minimum number of pieces Snuke needs to put on the board.
Sample Input 1
3 wbb o_o
Sample Output 1
2
Let us use W
to represent a white square that needs a piece on it, B
to represent a black square that needs a piece on it, w
to represent a white square that does not need a piece on it, and b
to represent a black square that does not need a piece on it.
We have the following board:
...wwwwwwWbBbbbbb...
If we put pieces in the following order, two pieces is enough:
...wwwwwwWbBbbbbb... 2 1
Note that if we put a piece on the white square first, we will need three or more pieces:
...wwwwwwWbBbbbbb... 123
Sample Input 2
4 wwww o__o
Sample Output 2
3
If we put pieces in the following order, three pieces is enough:
...wwwwwWwwWbbbbb... 1 32
Sample Input 3
9 bbwbwbwbb _o_o_o_o_
Sample Output 3
5
If we put pieces in the following order, five pieces is enough:
...wwwwwbBwBwBwBbbbbbb... 12 3 4 5
Sample Input 4
17 wwwwbbbbbbbbwwwwb __o__o_o_ooo__oo_
Sample Output 4
11