概要

修正後の \(s,t\) で作れる最大の非交差ペア数は、2 つの文字列の LCS（最長共通部分列） の長さです。

一見、修正の選び方が多そうですが、条件により実際に変更できる位置はほぼ両端だけに限られます。各文字列について可能な修正後の状態を高々 \(4\) 通り列挙し、それぞれに対して LCS を計算します。

考察

まず、ペアリングの条件を考えます。

ペア \((i,j)\) は \(s_i=t_j\) のときだけ作れ、さらに交差してはいけません。
これはつまり、\(s\) と \(t\) から同じ文字列を部分列として取り出すことと同じです。

したがって、修正後の文字列を \(a,b\) とすると、作れるペア数の最大値は

\[ \mathrm{LCS}(a,b) \]

になります。

---

次に、どのような修正が可能かを考えます。

文字列は 0, 1 のみからなります。
ある位置を反転した後、その位置は隣の文字すべてと異なっていなければなりません。

内部の位置は変更できない

位置 \(i\) が両隣を持つとします。

反転後の文字が両隣と異なるためには、反転前の文字が両隣と同じである必要があります。

つまり、変更前に

000

または

111

のように、同じ文字が \(3\) つ連続している必要があります。

しかし、問題文より最初の \(s,t\) には同じ文字が \(3\) 回連続する箇所はありません。

さらに、許される操作をしても、変更した位置は隣と異なるようになるため、新たに \(3\) 連続が生まれることもありません。

よって、内部の位置は一度も変更できません。

---

変更できるのは端だけ

端の位置は隣が \(1\) つしかありません。

例えば左端を変更する場合、変更後に右隣と異なっていればよいです。
これは、変更前に左端と右隣が同じである場合に限り可能です。

例：

00...

なら左端を反転して

10...

にできます。

一方、

01...

の場合、左端を反転すると

11...

となり、隣と同じになってしまうので不可能です。

したがって、長さが \(3\) 以上の文字列では、

• 左端は、先頭 \(2\) 文字が同じなら変更可能
• 右端は、末尾 \(2\) 文字が同じなら変更可能

です。

両端の変更は互いに独立なので、可能な修正後の文字列は高々 \(4\) 通りです。

---

長さが短い場合は少しだけ特殊です。

• 長さ \(1\) の場合
  隣が存在しないので、反転は常に可能です。
• 長さ \(2\) の場合
  もし \(2\) 文字が同じなら、左または右のどちらか一方を反転できます。
  ただし、一方を反転すると文字列は 01 または 10 になり、もう一方は反転できなくなります。

アルゴリズム

各文字列について、到達可能な状態を列挙します。

例えば文字列 \(u\) について、以下のように候補を作ります。

1. 元の文字列をコスト \(0\) で追加する
2. 長さ \(1\) の場合
   • 反転した文字列をコスト \(1\) で追加する
3. 長さ \(2\) の場合
   • \(u_0=u_1\) なら、左だけ反転・右だけ反転した文字列をコスト \(1\) で追加する
4. 長さ \(3\) 以上の場合
   • 先頭 \(2\) 文字が同じなら左端を反転可能
   • 末尾 \(2\) 文字が同じなら右端を反転可能
   • 可能な端の反転の組み合わせをすべて試す

これにより、各文字列について状態数は高々 \(4\) 個です。

その後、

• \(s\) 側の候補 \((a, c_a)\)
• \(t\) 側の候補 \((b, c_b)\)

をすべて試し、

\[ c_a+c_b \leq K \]

を満たすものについて \(\mathrm{LCS}(a,b)\) を計算します。

その最大値が答えです。

LCS は通常の動的計画法で求めます。
\(dp[j]\) を「現在見ている \(a\) の prefix と、\(b\) の先頭 \(j\) 文字との LCS 長」として、空間を \(O(|t|)\) に圧縮しています。

計算量

\(s\) の長さを \(n\)、\(t\) の長さを \(m\) とします。

各文字列の候補数は高々 \(4\) 個なので、LCS を計算する回数は高々 \(16\) 回です。

• 時間計算量: \(O(nm)\)
• 空間計算量: \(O(n+m)\)

制約で \(n \times m \leq 2 \times 10^6\) なので、十分高速に動作します。

実装のポイント

候補状態を生成するとき、同じ文字列が複数の方法で作られる可能性を考えて、同じ文字列に対しては最小コストだけを保持します。

また、操作回数は「高々 \(K\) 回」なので、候補状態の最小コストが \(K\) 以下であれば使えます。
余分に操作する必要はありません。

ソースコード

#include <bits/stdc++.h>
using namespace std;

static inline void flip_char(char &c) {
    c = (c == '0' ? '1' : '0');
}

vector<pair<string,int>> generate_states(const string& u) {
    vector<pair<string,int>> res;

    auto add = [&](const string& v, int cost) {
        for (auto &p : res) {
            if (p.first == v) {
                p.second = min(p.second, cost);
                return;
            }
        }
        res.push_back({v, cost});
    };

    int n = (int)u.size();
    add(u, 0);

    if (n == 1) {
        string v = u;
        flip_char(v[0]);
        add(v, 1);
    } else if (n == 2) {
        if (u[0] == u[1]) {
            string v = u;
            flip_char(v[0]);
            add(v, 1);

            v = u;
            flip_char(v[1]);
            add(v, 1);
        }
    } else {
        bool canL = (u[0] == u[1]);
        bool canR = (u[n - 2] == u[n - 1]);

        for (int mask = 1; mask < 4; mask++) {
            if ((mask & 1) && !canL) continue;
            if ((mask & 2) && !canR) continue;

            string v = u;
            int cost = 0;

            if (mask & 1) {
                flip_char(v[0]);
                cost++;
            }
            if (mask & 2) {
                flip_char(v[n - 1]);
                cost++;
            }

            add(v, cost);
        }
    }

    return res;
}

int lcs_length(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<int> dp(m + 1, 0);

    for (int i = 0; i < n; i++) {
        int prev = 0;
        for (int j = 0; j < m; j++) {
            int tmp = dp[j + 1];
            if (a[i] == b[j]) {
                dp[j + 1] = max(dp[j + 1], prev + 1);
            } else {
                dp[j + 1] = max(dp[j + 1], dp[j]);
            }
            prev = tmp;
        }
    }

    return dp[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    int K;
    cin >> s >> t >> K;

    auto ss = generate_states(s);
    auto tt = generate_states(t);

    int ans = 0;
    for (auto &[a, ca] : ss) {
        for (auto &[b, cb] : tt) {
            if (ca + cb <= K) {
                ans = max(ans, lcs_length(a, b));
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。