\(\mathrm{cost}[i][j][k]\) を \(S_i\) と \(T_j\) のシフト量 \(k\) での不一致数とします。

全ての \((i,j,k)\) についての \(\mathrm{cost}\) を求めることは \(O(N^2M^2)\) でできます。

求める答えは \(\min_P \min_k \sum_{i=1}^{N}\mathrm{cost}[i][P_i][k]\) です。ここで \(\min\) は \(P\) は \((1,2,\dots,N)\) の並び替えである数列 \(P\) 全てについてを取ります。これは、全ての \((i,j,k)\) で \(\mathrm{cost}\) がわかっているとき、数式の通り計算することで \(O(N!NM)\) で求めることができます。

クエリ 1,2 では \(\mathrm{cost}[i][*][*]\) が、クエリ 3 では \(\mathrm{cost}[*][j][*]\) が変化しますが、変化した文字にのみ注目することで各変化は \(O(1)\) で計算でき、全体で \(O(NM)\) で更新できます。

よって以上より、\(O(N^2M^2+QN!NM)\) でこの問題を解くことができます。

実装例 (C++)

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

int calc[5][5][500];

int main(){
  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 i=0; i<n; i++) cin >> t[i];
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<m; k++){
        for(int p=0; p<m; p++){
          if(c[i][p] == '0' && s[i][p] != t[j][(p+k)%m]){
            calc[i][j][k]++;
          }
        }
      }
    }
  }
  
  for(int _=0; _<q; _++){
    int type, i, p;
    char x;
    cin >> type >> i >> p >> x;
    i--, p--;
    if(type == 1){
      for(int j=0; j<n; j++){
        for(int k=0; k<m; k++){
          if(c[i][p] == '0' && s[i][p] != t[j][(p+k)%m]){
            calc[i][j][k]--;
          }
          if(c[i][p] == '0' && x != t[j][(p+k)%m]){
            calc[i][j][k]++;
          }
        }
      }
      s[i][p] = x;
    }else if(type == 2){
      for(int j=0; j<n; j++){
        for(int k=0; k<m; k++){
          if(c[i][p] == '0' && s[i][p] != t[j][(p+k)%m]){
            calc[i][j][k]--;
          }
          if(x == '0' && s[i][p] != t[j][(p+k)%m]){
            calc[i][j][k]++;
          }
        }
      }
      c[i][p] = x;
    }else if(type == 3){
      int j = i;
      for(int i=0; i<n; i++){
        for(int k=0; k<m; k++){
          if(c[i][(p-k+m)%m] == '0' && s[i][(p-k+m)%m] != t[j][p]){
            calc[i][j][k]--;
          }
          if(c[i][(p-k+m)%m] == '0' && s[i][(p-k+m)%m] != x){
            calc[i][j][k]++;
          }
        }
      }
      t[j][p] = x;
    }
    
    int ans = 1e9;
    vector<int>perm(n);
    for(int i=0; i<n; i++){
      perm[i] = i;
    }
    do{
      for(int k=0; k<m; k++){
        int tans = 0;
        for(int i=0; i<n; i++){
          tans += calc[i][perm[i]][k];
        }
        ans = min(ans, tans);
      }
    }while(next_permutation(perm.begin(), perm.end()));
    cout << ans << endl;
  }
}

実装例 (Python)

import itertools

N, M, Q = map(int, input().split())
S = []
C = []
for _ in range(N):
  S.append(list(input()))
  C.append(list(input()))
T = [list(input()) for _ in range(N)]

# calc[i][j][k] = S[i] とrot(T,r) の差
calc = [[[0]*M for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    for k in range(M):
      for p in range(M):
        if C[i][p] == '0' and S[i][p] != T[j][(p+k)%M]:
          calc[i][j][k] += 1

for _ in range(Q):
  t, i, p, x = input().split()
  i = int(i) - 1
  p = int(p) - 1
  if t == '1':
    for j in range(N):
      for k in range(M):
        if C[i][p] == '0' and S[i][p] != T[j][(p+k)%M]:
          calc[i][j][k] -= 1
        if C[i][p] == '0' and x != T[j][(p+k)%M]:
          calc[i][j][k] += 1
    S[i][p] = x
  elif t == '2':
    for j in range(N):
      for k in range(M):
        if C[i][p] == '0' and S[i][p] != T[j][(p+k)%M]:
          calc[i][j][k] -= 1
        if x == '0' and S[i][p] != T[j][(p+k)%M]:
          calc[i][j][k] += 1
    C[i][p] = x
  elif t == '3':
    j = i
    for i in range(N):
      for k in range(M):
        if C[i][(p-k)%M] == '0' and S[i][(p-k)%M] != T[j][p]:
          calc[i][j][k] -= 1
        if C[i][(p-k)%M] == '0' and S[i][(p-k)%M] != x:
          calc[i][j][k] += 1
    T[j][p] = x

  ans = 10**18
  for perm in itertools.permutations(range(N)):
    for k in range(M):
      ans = min(ans, sum(calc[i][perm[i]][k] for i in range(N)))
  print(ans)