AT_arc109_f [ARC109F] 1D Kingdom Builder
题目描述
[problemUrl]: https://atcoder.jp/contests/arc109/tasks/arc109_f
Snuke 君正在玩一个由无限个格子组成的单行棋盘游戏。每个格子都有一个整数编号，对于任意整数 $i$，格子 $i$ 和格子 $i+1$ 都是相邻的。此外，每个格子要么是白色，要么是黑色。
棋盘上格子的颜色由一个长度为 $n$ 的字符串 $s$（仅包含字符 `w` 和 `b`）表示，具体规则如下：
- 对于每个 $i = 1, 2, \dots, n$，如果 $s$ 的第 $i$ 个字符为 `w`，则格子 $i$ 为白色；若为 `b`，则为黑色。
- 当 $i \leq 0$ 时，格子 $i$ 均为白色。
- 当 $i > n$ 时，格子 $i$ 均为黑色。
Snuke 君有无限多的白色棋子和黑色棋子。他会按照以下步骤将棋子逐一放置到棋盘上：
- (1) 选择任意颜色的棋子（白色或黑色）。
- (2) 在棋盘上寻找与已经放置的棋子相邻的、且与所选棋子颜色相同的空格子。
- (2a) 如果存在满足条件的格子，选一个格子并将棋子放置在上面。
- (2b) 如果不存在满足条件的格子，则从棋盘上所有与所选棋子颜色相同的空格子中任选一个，将棋子放置在上面。
最开始，棋盘上没有任何棋子。
现给出一个长度为 $n$ 的字符串 $t$（仅包含字符 `o` 和 `_`）。为了在所有满足条件（$t$ 中字符为 `o`）的格子上都放置一个棋子，至少需要放置多少个棋子？
（保证字符串 $t$ 中至少含有一个 `o`。）
输入格式
输入从标准输入给出，格式如下：
> $n$
> $s$
> $t$
输出格式
输出一个整数，表示 Snuke 君需要放置的最少棋子数量。
说明/提示
### 限制条件
- $1 \leq n \leq 10^5$
- $|s| = |t| = n$
- 字符串 $s$ 仅由 `w` 和 `b` 组成
- 字符串 $t$ 仅由 `o` 和 `_` 组成，且至少含有一个 `o`
### 样例解释 1
用 `W` 和 `B` 分别表示必须放置棋子的白格和黑格，用 `w` 和 `b` 表示不必放置棋子的白格和黑格，则棋盘情况如下：`...wwwwwwWbBbbbbb...`。按照以下顺序放置棋子，仅需 $2$ 次即可满足要求：
```
...wwwwwwWbBbbbbb...
2 1
```
注意，如果先在白格放置棋子，则至少需要 $3$ 次：
```
...wwwwwwWbBbbbbb...
123
```
### 样例解释 2
按照以下顺序放置棋子，需要 $3$ 次即可满足要求：
```
...wwwwwWwwWbbbbb...
1 32
```
### 样例解释 3
按照以下顺序放置棋子，需要 $5$ 次即可满足要求：
```
...wwwwwbBwBwBwBbbbbbb...
12 3 4 5
```
翻译由 ChatGPT-4.5 完成。