/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君と青木君は、それぞれ左右のステップからなるダンスの振り付けを持っています。高橋君の振り付けは文字列 s 、青木君の振り付けは文字列 t で表され、各文字は 0（左ステップ）または 1（右ステップ）です。どちらの振り付けにも、同じステップが 3 回連続する箇所はありません。
本番前のリハーサルで、高橋君は高々 K 回、次の修正を行うことができます。
- s または t のある位置を 1 つ選び、そのステップを逆のステップに変更する。
- ただし、変更後、その位置のステップは、同じ振り付け内で隣り合うすべてのステップと異なっていなければならない。
リハーサル後、高橋君は s のステップと t のステップをいくつかペアにして「シンクロポイント」を作ります。ペアリングは次の条件をすべて満たす必要があります。
- 各ペアは、 s のある位置 i と t のある位置 j からなる。
- ペアにできるのは、 s_i = t_j である位置同士だけである。
- s の各位置、 t の各位置は、それぞれ高々 1 つのペアにしか使えない。
- ペア同士は交差してはならない。すなわち、ペア (i, j) と (i', j') について、 i < i' ならば j < j' でなければならない。
修正とペアリングを適切に行ったとき、作ることができるペアの個数の最大値を求めてください。
制約
- 1 \leq |s| \leq 2 \times 10^5
- 1 \leq |t| \leq 2 \times 10^5
- |s| \times |t| \leq 2 \times 10^6
- s は
0と1のみからなる文字列である。 - t は
0と1のみからなる文字列である。 - s には同じ文字が 3 回以上連続する箇所がない。
- t には同じ文字が 3 回以上連続する箇所がない。
- 0 \leq K \leq |s| + |t|
- K は整数である。
入力
s t K
- 1 行目には、
0と1からなる文字列 s が与えられる。 - 2 行目には、
0と1からなる文字列 t が与えられる。 - 3 行目には、修正を行える回数の上限を表す整数 K が与えられる。
出力
作ることができるペアの個数の最大値を整数で出力せよ。
入力例 1
0101 0011 1
出力例 1
3
入力例 2
01 10 0
出力例 2
1
入力例 3
010110100110110010101101001011 1010010110100110101100101101 5
出力例 3
24
入力例 4
001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011 110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100 40
出力例 4
100
入力例 5
0 1 2
出力例 5
1
Score : 433 pts
Problem Statement
Takahashi and Aoki each have a dance choreography consisting of left and right steps. Takahashi's choreography is represented by string s, and Aoki's choreography is represented by string t, where each character is 0 (left step) or 1 (right step). Neither choreography contains three consecutive occurrences of the same step.
During rehearsal before the performance, Takahashi can perform the following modification at most K times:
- Choose one position in s or t, and change that step to the opposite step.
- However, after the change, the step at that position must differ from all adjacent steps within the same choreography.
After rehearsal, Takahashi pairs up some steps from s and t to create "synchro points." The pairing must satisfy all of the following conditions:
- Each pair consists of a position i in s and a position j in t.
- Only positions where s_i = t_j can be paired.
- Each position in s and each position in t can be used in at most one pair.
- Pairs must not cross each other. That is, for pairs (i, j) and (i', j'), if i < i' then j < j' must hold.
Determine the maximum number of pairs that can be made by performing modifications and pairing optimally.
Constraints
- 1 \leq |s| \leq 2 \times 10^5
- 1 \leq |t| \leq 2 \times 10^5
- |s| \times |t| \leq 2 \times 10^6
- s is a string consisting only of
0and1. - t is a string consisting only of
0and1. - s does not contain three or more consecutive occurrences of the same character.
- t does not contain three or more consecutive occurrences of the same character.
- 0 \leq K \leq |s| + |t|
- K is an integer.
Input
s t K
- The first line contains the string s consisting of
0and1. - The second line contains the string t consisting of
0and1. - The third line contains an integer K, representing the upper limit on the number of modifications that can be made.
Output
Output the maximum number of pairs that can be made, as an integer.
Sample Input 1
0101 0011 1
Sample Output 1
3
Sample Input 2
01 10 0
Sample Output 2
1
Sample Input 3
010110100110110010101101001011 1010010110100110101100101101 5
Sample Output 3
24
Sample Input 4
001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011 110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100 40
Sample Output 4
100
Sample Input 5
0 1 2
Sample Output 5
1