概要

各暗号文と各原文について、全シフト量での不一致数を前計算・更新し、
各クエリ後に「シフト量固定 + 1対1対応（置換）」の最小コストを全探索して答える問題です。

考察

この問題の最適化対象は次の2段階です。

1. 共通シフト量 \(r\) を決める
   
2. 暗号文 \(i\) と原文 \(j\) の対応（1対1）を決める

ここで、暗号文 \(i\) と原文 \(j\) をシフト \(r\) で比べた不一致数を \(D[i][j][r]\) と置くと、求める値は

[ \min{0 \le r < M} \ \min{\text{置換 } \pi} \sum_{i=0}^{N-1} D[i][\pi(i)][r] ]

になります。

---

素朴に毎回ゼロから計算すると、
- 各 \(D[i][j][r]\) を作るのに \(O(M)\) - 組み合わせは \(N^2M\) 個
で重く、さらにクエリごとにやると間に合いません。

ただし制約を見ると
- \(N \le 5\)（とても小さい） - \(M,Q \le 500\), かつ \(MQ \le 5\times 10^4\)

なので方針は以下が有効です：

• \(N\) が小さいので、対応の全列挙（\(N!\)）は可能
• 変更は1文字だけなので、影響する行/列の \(D\) だけ再計算すればよい

この「小さい \(N\) を全探索、大きめの \(M\) は差分再計算」がポイントです。

アルゴリズム

1. 不一致数テーブルの管理

3次元配列 D[i][j][r] を持ちます。

• 意味：暗号文 i と原文 j をシフト r で比較した不一致数
• 比較対象は C[i][p]=='0' の位置 p のみ

recompute_pair(i,j) でこの1ペア分を \(O(M^2)\) で再計算します。
（位置 p を回し、各シフト r で T[j][(p+r)%M] と比較）

2. クエリ更新

• 1 i p x（S更新）: 暗号文 i に関係する全 j を再計算
• 2 i p b（C更新）: 同上
• 3 j p x（T更新）: 原文 j に関係する全 i を再計算

つまり、毎回再計算するのは高々 \(N\) ペアだけです。

3. 答えの計算

各クエリ後、次を計算：

• 各シフト r について
  • 各置換 pm（N!個）について [ \sum_i D[i][pm[i]][r] ]
  • その最小値を best(r) とする
• 全 r の最小を出力

置換は事前に next_permutation で全列挙して保存しておきます。

計算量

• 時間計算量:
  
  • 初期構築：\(O(N^2M^2)\)
    
  • 1クエリの更新：高々 \(N\) ペア再計算なので \(O(NM^2)\)
    
  • 1クエリの答え計算：\(O(M \cdot N! \cdot N)\)
    
  • よって 1クエリあたり
    [ O(NM^2 + M\cdot N!\cdot N) ] 制約下（\(N\le5\)）で十分高速です。
• 空間計算量:
  [ O(N^2M) ] （主に D）

実装のポイント

• 入力は1-indexedだが、実装は0-indexedに直す（--a, --p）。

• 更新前後で値が同じなら再計算をスキップして無駄を減らす。

• type=3 だけ a が「原文番号 j」になる点に注意。

• C[i][p]=='1'（読めない位置）は不一致判定に含めない。ここがWAの典型ポイントです。

  ソースコード

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

static const int INF = 1e9;

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] >> C[i];
    }
    for (int j = 0; j < N; j++) cin >> T[j];

    // D[i][j][r]: mismatches between cipher i and plain j with shift r
    vector<vector<vector<int>>> D(N, vector<vector<int>>(N, vector<int>(M, 0)));

    auto recompute_pair = [&](int i, int j) {
        vector<int> &arr = D[i][j];
        fill(arr.begin(), arr.end(), 0);
        for (int p = 0; p < M; p++) {
            if (C[i][p] == '1') continue;
            char sc = S[i][p];
            for (int r = 0; r < M; r++) {
                int tp = p + r;
                if (tp >= M) tp -= M;
                if (sc != T[j][tp]) arr[r]++;
            }
        }
    };

    auto recompute_i_allj = [&](int i) {
        for (int j = 0; j < N; j++) recompute_pair(i, j);
    };
    auto recompute_j_alli = [&](int j) {
        for (int i = 0; i < N; i++) recompute_pair(i, j);
    };

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) recompute_pair(i, j);
    }

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

    for (int qi = 0; qi < Q; qi++) {
        int type, a, p;
        char x;
        cin >> type >> a >> p >> x;
        --a; --p;

        if (type == 1) {
            if (S[a][p] != x) {
                S[a][p] = x;
                recompute_i_allj(a);
            }
        } else if (type == 2) {
            if (C[a][p] != x) {
                C[a][p] = x;
                recompute_i_allj(a);
            }
        } else { // type == 3
            int j = a;
            if (T[j][p] != x) {
                T[j][p] = x;
                recompute_j_alli(j);
            }
        }

        int ans = INF;
        for (int r = 0; r < M; r++) {
            int best = INF;
            for (const auto &pm : perms) {
                int sum = 0;
                for (int i = 0; i < N; i++) sum += D[i][pm[i]][r];
                if (sum < best) best = sum;
            }
            if (best < ans) ans = best;
        }
        cout << ans << '\n';
    }

    return 0;
}

---

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