/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1500 点
問題文
A, B, C からなる文字列は、どの連続する 2 文字も異なるとき、良い 文字列であると呼ばれます。例えば、ABABAB や ABC は良い文字列であり、ABBA や AABBCC は良い文字列ではありません。
2 つの長さ N の 良い 文字列 S, T が与えられます。
1 回の操作で、あなたは S から任意の 1 文字を選び、A, B, C のいずれかであるような別の文字に変えることができます。ただし、操作後も S は 良い 文字列でなければなりません。
S を T に変化させるには、最小で何回の操作が必要でしょうか。 なお、これは必ず有限回の操作で可能であることが証明できます。
制約
- 1\le N \le 5\cdot 10^5
- S は
A,B,Cからなる長さ N の 良い 文字列である。 - T は
A,B,Cからなる長さ N の 良い 文字列である。
入力
入力は以下の形式で標準入力から与えられる。
N S T
出力
S を T に変化させるために必要な最小の操作回数を出力せよ。
入力例 1
4 CABC CBAC
出力例 1
6
6 回の操作で目標を達成する例を以下に示します。
CABC \to BABC \to BCBC \to BCAC \to ACAC \to ABAC \to CBAC
この場合には、少なくとも 6 回の操作が必要であることが示せます。
入力例 2
10 ABABABABAB BABABABABA
出力例 2
15
Score : 1500 points
Problem Statement
A string, consisting of letters A, B, and C, is called good, if every two consecutive letters are different. For example, strings ABABAB and ABC are good, while ABBA and AABBCC aren't.
You are given two good strings S and T of length N.
In one operation, you can choose any letter of S, and change it to another letter among A, B, and C, so that S remains good.
What's the smallest number of operations needed to transform S into T? We can prove that it can always be done in a finite number of operations.
Constraints
- 1\le N \le 5\cdot 10^5
- S is a good string of length N consisting of
A,B, andC - T is a good string of length N consisting of
A,B, andC
Input
Input is given from Standard Input in the following format:
N S T
Output
Output the smallest number of operations needed to transform S into T.
Sample Input 1
4 CABC CBAC
Sample Output 1
6
Here is one possible sequence of operations of length 6:
CABC \to BABC \to BCBC \to BCAC \to ACAC \to ABAC \to CBAC
It can be shown that 6 operations are necessary for this case.
Sample Input 2
10 ABABABABAB BABABABABA
Sample Output 2
15