D - 回転暗号の解読 / Decryption of the Rotation Cipher Editorial by admin Editorial for printing
gemini-3-flash-thinking概要
\(N\) 個の不完全な暗号文と \(N\) 個の原文が与えられます。すべてのペアに共通の「巡回シフト量 \(r\)」と、暗号文と原文の「1対1の対応関係」を適切に選んだときの、文字の不一致数の合計の最小値を求める問題です。また、文字の書き換えクエリが \(Q\) 回発生するため、各更新ごとに最小値を計算する必要があります。
考察
1. 問題の分解
この問題は、以下の2つの要素に分解できます。 - 不一致数の計算: 特定の暗号文 \(i\) と原文 \(j\) をシフト量 \(r\) で対応させたときの不一致数 \(D_{i,j,r}\) を求める。 - 最小重み完全マッチング: シフト量 \(r\) を固定したとき、暗号文と原文をどうペアリングすれば合計不一致数が最小になるかを求める。
2. 制約の活用
制約を見ると \(N \leq 5\) と極めて小さく、\(M, Q \leq 500\) です。 \(N\) が小さいため、固定された \(r\) における「最小重み完全マッチング」は、ビットDPや全探索（\(N!\) 通り）で高速に解くことができます。一方、シフト量 \(r\) は \(M\) 通りあるため、各クエリで \(O(M \times (\text{マッチング計算}))\) の処理を行うことになります。
3. クエリへの効率的な対応
各クエリで全ての \(D_{i,j,r}\) を再計算すると間に合いません。しかし、1箇所の文字が変わったときに影響を受ける \(D_{i,j,r}\) は限定的です。 - 暗号文 \(S_i\) の文字が変わった場合：その \(i\) に関する \(D_{i,j,r}\) のみを更新する（\(N \times M\) 個）。 - 原文 \(T_j\) の文字が変わった場合：その \(j\) に関する \(D_{i,j,r}\) のみを更新する（\(N \times M\) 個）。 このように、差分更新を行うことでクエリごとの計算量を抑えることができます。
アルゴリズム
1. 前計算
最初に、すべての \(i, j, r\) について不一致数 \(D_{i,j,r}\) を計算し、テーブルに保持しておきます。 $\(D_{i,j,r} = \sum_{p=0}^{M-1} [C_{i,p} = \text{'0'} \text{ かつ } S_{i,p} \neq T_{j,(p+r) \bmod M}]\)$
2. クエリ処理（差分更新）
文字が変更された際、その文字が関与する \(D_{i,j,r}\) の値を書き換えます。 例えば、暗号文 \(S_i\) の位置 \(p\) が \(x\) に変わった場合、各 \(j, r\) について、 - 変更前の文字 \(S_{i,p}\) が \(T_{j,(p+r) \bmod M}\) と異なっていたなら、カウントを \(-1\) する。 - 変更後の文字 \(x\) が \(T_{j,(p+r) \bmod M}\) と異なっているなら、カウントを \(+1\) する。 という操作を \(O(N \times M)\) で行います。
3. 最小値の計算（ビットDP）
各クエリの最後に、現在の \(D_{i,j,r}\) を用いて答えを求めます。
すべての \(r \in [0, M-1]\) について以下を行います：
- dp[mask] を「原文の集合 mask を既に使用したときの、最初の popcount(mask) 個の暗号文に対する不一致数の最小合計」としてビットDPを行う。
- \(N=5\) なので、状態数は \(2^5 = 32\) です。
- dp[(1 << N) - 1] がその \(r\) における最小値となります。
全 \(r\) の中での最小値が、そのクエリに対する回答です。
計算量
- 前計算: \(O(N^2 M^2)\)
- クエリごとの更新: \(O(NM)\)
- クエリごとの最小値計算: \(O(M \cdot N 2^N)\)
- 全体: \(O(N^2 M^2 + Q(NM + M N 2^N))\)
\(N=5, M=500, Q=500\) を代入すると、全体で約 \(5 \times 10^7\) 回程度の演算となり、制限時間内に十分収まります。
実装のポイント
巡回シフトのインデックス: 原文 \(T_j\) の参照位置は \((p+r) \bmod M\) です。逆に \(T_j\) の位置 \(p\) を変更した際に影響を受ける \(S_i\) の位置 \(p'\) は、\((p' + r) \equiv p \pmod M\) より \(p' = (p - r + M) \bmod M\) となります。
高速化: \(N\) が非常に小さいため、ビットDPの部分は
__builtin_popcountなどを使用して簡潔に記述できます。入出力: クエリ数が多いため、
std::cin.tie(nullptr); std::ios::sync_with_stdio(false);等で高速化しておくと安全です。ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/**
* Problem Summary:
* We are given N ciphertexts (S_i, C_i) and N plaintexts T_j, all of length M.
* For a common shift amount r (0 <= r < M), find a 1-to-1 matching sigma
* between {1..N} and {1..N} that minimizes the total mismatch count:
* sum_{i=1}^N mismatch(S_i, C_i, T_{sigma(i)}, r)
*
* Mismatch for a pair (S_i, C_i) and T_j with shift r:
* sum_{p=0}^{M-1} [C_i[p] == '0' and S_i[p] != T_j[(p+r) % M]]
*
* There are Q updates to S_i, C_i, or T_j. Output the minimum total mismatch
* after each update.
*
* Constraints:
* N <= 5, M <= 500, Q <= 500, MQ <= 5*10^4.
*
* Complexity:
* Precalculation: O(N^2 * M^2)
* Update: O(N * M)
* Minimum mismatch calculation: O(M * N * 2^N)
* Total complexity: O(N^2 * M^2 + Q * (NM + M * N * 2^N))
* With N=5, M=500, Q=500, MQ=5*10^4, this is roughly 10^7-10^8 operations.
*/
int D[5][5][500];
string S[5], C[5], T[5];
int N, M, Q;
int dp[32];
int main() {
// Fast I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> M >> Q)) return 0;
// Read initial ciphertexts
for (int i = 0; i < N; ++i) {
cin >> S[i] >> C[i];
}
// Read initial plaintexts
for (int j = 0; j < N; ++j) {
cin >> T[j];
}
// Precalculate D[i][j][r]: mismatch count between S_i and T_j with shift r
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int r = 0; r < M; ++r) {
int count = 0;
for (int p = 0; p < M; ++p) {
if (C[i][p] == '0' && S[i][p] != T[j][(p + r) % M]) {
count++;
}
}
D[i][j][r] = count;
}
}
}
// Process Q queries
for (int q = 0; q < Q; ++q) {
int type;
cin >> type;
if (type == 1) {
// Update S_i[p] to x
int i, p;
char x;
cin >> i >> p >> x;
--i; --p;
char old_x = S[i][p];
S[i][p] = x;
// Only affects D[i][j][r] for the updated i
if (C[i][p] == '0') {
for (int j = 0; j < N; ++j) {
for (int r = 0; r < M; ++r) {
if (old_x != T[j][(p + r) % M]) D[i][j][r]--;
if (x != T[j][(p + r) % M]) D[i][j][r]++;
}
}
}
} else if (type == 2) {
// Update C_i[p] to b
int i, p;
char b;
cin >> i >> p >> b;
--i; --p;
char old_b = C[i][p];
C[i][p] = b;
// Only affects D[i][j][r] for the updated i
if (old_b != b) {
for (int j = 0; j < N; ++j) {
for (int r = 0; r < M; ++r) {
if (old_b == '0') {
// Was counted, now ignored
if (S[i][p] != T[j][(p + r) % M]) D[i][j][r]--;
} else {
// Was ignored, now counted
if (S[i][p] != T[j][(p + r) % M]) D[i][j][r]++;
}
}
}
}
} else if (type == 3) {
// Update T_j[p] to x
int j, p;
char x;
cin >> j >> p >> x;
--j; --p;
char old_x = T[j][p];
T[j][p] = x;
// Affects D[i][j][r] for the updated j
for (int i = 0; i < N; ++i) {
for (int r = 0; r < M; ++r) {
// Find the position in S_i that corresponds to T_j[p]
int p_in_S = (p - r + M) % M;
if (C[i][p_in_S] == '0') {
if (S[i][p_in_S] != old_x) D[i][j][r]--;
if (S[i][p_in_S] != x) D[i][j][r]++;
}
}
}
}
// Find the global minimum over all possible shifts r
int min_total = 1e9;
for (int r = 0; r < M; ++r) {
// Find minimum weight perfect matching for fixed r using bitmask DP
for (int mask = 0; mask < (1 << N); ++mask) dp[mask] = 1e9;
dp[0] = 0;
for (int mask = 0; mask < (1 << N); ++mask) {
if (dp[mask] == 1e9) continue;
int i = __builtin_popcount((unsigned int)mask);
if (i == N) continue;
// Match the i-th ciphertext with an available j-th plaintext
for (int j = 0; j < N; ++j) {
if (!((mask >> j) & 1)) {
int next_mask = mask | (1 << j);
if (dp[next_mask] > dp[mask] + D[i][j][r]) {
dp[next_mask] = dp[mask] + D[i][j][r];
}
}
}
}
if (min_total > dp[(1 << N) - 1]) min_total = dp[(1 << N) - 1];
}
cout << min_total << "\n";
}
return 0;
}
この解説は gemini-3-flash-thinking によって生成されました。
posted:
last update: