概要

各暗号文 \(i\) と各原文 \(j\) について、シフト量 \(r\) ごとの不一致数をあらかじめ管理します。
変更クエリでは、変わった1文字（または1マスク位置）の影響だけを差分更新し、その後、全シフト量と全対応を試して最小値を求めます。

考察

暗号文 \(i\) と原文 \(j\) をシフト量 \(r\) で比較したときの不一致数を

\[ cost[i][j][r] \]

として持つことを考えます。

0-indexed で考えると、暗号文の位置 \(p\) は原文の位置

\[ (p+r) \bmod M \]

と対応します。

したがって、

\[ cost[i][j][r] = \sum_{p=0}^{M-1} [C_i[p]=\texttt{0}] [S_i[p] \ne T_j[(p+r)\bmod M]] \]

です。

ここで \([条件]\) は、条件が真なら \(1\)、偽なら \(0\) を表します。

---

固定されたシフト量 \(r\) に対しては、暗号文 \(i\) にどの原文を割り当てるかを決めればよいです。
これは \(N\) 個の対応を決める問題ですが、制約で

\[ N \leq 5 \]

なので、全順列を試せます。

つまり答えは

\[ \min_{0 \leq r < M} \min_{\pi} \sum_{i=0}^{N-1} cost[i][\pi(i)][r] \]

です。

---

素朴に各クエリ後に、すべてのシフト量・すべての対応・すべての文字位置を毎回比較すると、

\[ O(Q \cdot M \cdot N! \cdot N \cdot M) \]

となり重すぎます。

そこで、各ペア・各シフト量の不一致数 cost を保持しておきます。
1回の変更では1文字または1つのマスク位置しか変わらないため、その位置が関係する cost だけを差分更新すれば十分です。

アルゴリズム

1. 初期状態の cost を計算する

全ての \(i, j, r\) について、全位置 \(p\) を調べて不一致数を数えます。

for i
  for j
    for r
      for p
        if C[i][p] == '0' and S[i][p] != T[j][(p+r)%M]
          cost[i][j][r]++

2. 原文の割り当て順列を列挙しておく

\(N \leq 5\) なので、原文の割り当ては高々

\[ 5! = 120 \]

通りです。

例えば順列 p に対して、暗号文 \(i\) に原文 p[i] を割り当てると考えます。

3. 答えを求める

各シフト量 \(r\) と各順列 p について、

\[ \sum_i cost[i][p[i]][r] \]

を計算し、その最小値を答えにします。

4. クエリ処理

クエリ1: 1 i p x

暗号文 \(S_i[p]\) の文字を変更します。

この変更が影響するのは、暗号文 \(i\) の位置 \(p\) を使う比較だけです。
ただし、\(C_i[p]=\texttt{1}\) の場合は比較対象外なので cost は変わりません。

\(C_i[p]=\texttt{0}\) のとき、すべての原文 \(j\)、シフト量 \(r\) について、

\[ tp = (p+r) \bmod M \]

として、

\[ cost[i][j][r] \mathrel{+}= [x \ne T_j[tp]] - [old \ne T_j[tp]] \]

と更新します。

クエリ2: 2 i p b

マスク \(C_i[p]\) を変更します。

1 から 0 になる場合は、その位置が新たに比較対象になるので、不一致なら \(+1\) します。
0 から 1 になる場合は、比較対象から外れるので、不一致なら \(-1\) します。

古い状態で比較対象なら oldActive = 1、そうでなければ 0、
新しい状態も同様に newActive とすると、

\[ cost[i][j][r] \mathrel{+}= (newActive - oldActive) \cdot [S_i[p] \ne T_j[(p+r)\bmod M]] \]

です。

クエリ3: 3 j p x

原文 \(T_j[p]\) の文字を変更します。

原文の位置 \(p\) が、シフト量 \(r\) のとき暗号文のどの位置と対応するかを逆算します。

\[ sp = (p-r+M) \bmod M \]

です。

したがって、すべての暗号文 \(i\)、シフト量 \(r\) について、
\(C_i[sp]=\texttt{0}\) の場合だけ、

\[ cost[i][j][r] \mathrel{+}= [S_i[sp] \ne x] - [S_i[sp] \ne old] \]

と更新します。

計算量

• 時間計算量: \(O(N^2M^2 + Q(NM + MN!N))\)
  • 初期 cost 計算: \(O(N^2M^2)\)
  • 各クエリの差分更新: \(O(NM)\)
  • 各クエリ後の答え計算: \(O(MN!N)\)
• 空間計算量: \(O(N^2M + N!N)\)

\(N \leq 5\)、\(M Q \leq 5 \times 10^4\) なので十分高速です。

実装のポイント

• 入力は 1-indexed ですが、実装では 0-indexed に直すと扱いやすいです。

• シフト量 \(r\) の比較では、暗号文位置 \(p\) に対応する原文位置は (p + r) % M です。

• 原文側を変更するクエリでは逆向きに考え、対応する暗号文位置を (p - r + M) % M で求めます。

• cost を更新してから、実際の文字列 S, C, T を変更します。古い値と新しい値の差分を使うためです。

  ソースコード

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

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

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<string> S(N), C(N), T(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        cin >> C[i];
    }
    for (int j = 0; j < N; j++) cin >> T[j];

    vector<vector<vector<int>>> cost(N, vector<vector<int>>(N, vector<int>(M, 0)));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int r = 0; r < M; r++) {
                int cnt = 0;
                for (int p = 0; p < M; p++) {
                    if (C[i][p] == '0' && S[i][p] != T[j][(p + r) % M]) {
                        cnt++;
                    }
                }
                cost[i][j][r] = cnt;
            }
        }
    }

    vector<vector<int>> perms;
    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 0);
    do {
        perms.push_back(perm);
    } while (next_permutation(perm.begin(), perm.end()));

    auto answer = [&]() -> int {
        int ans = INT_MAX;
        for (int r = 0; r < M; r++) {
            for (const auto& p : perms) {
                int sum = 0;
                for (int i = 0; i < N; i++) {
                    sum += cost[i][p[i]][r];
                }
                ans = min(ans, sum);
            }
        }
        return ans;
    };

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int i, p;
            char x;
            cin >> i >> p >> x;
            --i;
            --p;

            char old = S[i][p];
            if (old != x && C[i][p] == '0') {
                for (int j = 0; j < N; j++) {
                    for (int r = 0; r < M; r++) {
                        int tp = (p + r) % M;
                        int before = (old != T[j][tp]);
                        int after = (x != T[j][tp]);
                        cost[i][j][r] += after - before;
                    }
                }
            }
            S[i][p] = x;
        } else if (type == 2) {
            int i, p;
            char b;
            cin >> i >> p >> b;
            --i;
            --p;

            char old = C[i][p];
            if (old != b) {
                int oldActive = (old == '0');
                int newActive = (b == '0');
                for (int j = 0; j < N; j++) {
                    for (int r = 0; r < M; r++) {
                        int tp = (p + r) % M;
                        int mis = (S[i][p] != T[j][tp]);
                        cost[i][j][r] += (newActive - oldActive) * mis;
                    }
                }
            }
            C[i][p] = b;
        } else {
            int j, p;
            char x;
            cin >> j >> p >> x;
            --j;
            --p;

            char old = T[j][p];
            if (old != x) {
                for (int i = 0; i < N; i++) {
                    for (int r = 0; r < M; r++) {
                        int sp = (p - r + M) % M;
                        if (C[i][sp] == '0') {
                            int before = (S[i][sp] != old);
                            int after = (S[i][sp] != x);
                            cost[i][j][r] += after - before;
                        }
                    }
                }
            }
            T[j][p] = x;
        }

        cout << answer() << '\n';
    }

    return 0;
}

---

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