AT_arc109_f [ARC109F] 1D Kingdom Builder

[problemUrl]: https://atcoder.jp/contests/arc109/tasks/arc109_f すぬけ君は、一列に並んだ無限個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ整数が振られていて、任意の整数 $ 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` を含むことが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ s $ $ t $

すぬけ君が置く必要のあるコマの数の最小値を出力せよ。

### 制約 - $ 1\ \leq\ n\ \leq\ 10^5 $ - $ |s|\ =\ |t|\ =\ n $ - $ s $ は `w` と `b` のみからなる - $ t $ は `o` と `_` のみからなる - $ t $ は `o` を $ 1 $ 文字以上含む ### Sample Explanation 1 コマを置かなくてはならない白マスと黒マスをそれぞれ `W` と `B` で表して、 コマを置かなくてもよい白マスと黒マスをそれぞれ `w` と `b` で表すことにします。 盤面は次のようになります。 ``` ...wwwwwwWbBbbbbb... ``` 次の順番で置くと $ 2 $ 回で条件を満たせます。 ``` ...wwwwwwWbBbbbbb... 2 1 ``` 先に白マスに駒を置くと $ 3 $ 回以上の操作が必要になることに注意してください。 ``` ...wwwwwwWbBbbbbb... 123 ``` ### Sample Explanation 2 次の順番で置くと $ 3 $ 回で条件を満たせます。 ``` ...wwwwwWwwWbbbbb... 1 32 ``` ### Sample Explanation 3 次の順番で置くと $ 5 $ 回で条件を満たせます。 ``` ...wwwwwbBwBwBwBbbbbbb... 12 3 4 5 ```