D - 回転暗号の解読 / Decryption of the Rotation Cipher Editorial by admin Editorial for printing
gpt-5.5-high概要
すべての暗号文と原文の組 \((i,j)\)、およびシフト量 \(r\) ごとの不一致数を管理しておきます。
各クエリでは、変更の影響を受ける不一致数だけを差分更新し、その後、各シフト量について最小重みマッチングをビット DP で求めます。
考察
暗号文 \(i\) と原文 \(j\) をシフト量 \(r\) で比較したときの不一致数を
\[ cost[i][j][r] \]
とします。
この値は、
\[ C_i[p] = 0 \]
である、つまり読み取れている位置 \(p\) についてのみ、
\[ S_i[p] \neq T_j[(p+r) \bmod M] \]
となる個数です。
ここでは実装上、位置は \(0\)-indexed で考えます。
固定されたシフト量 \(r\) について考えると、やるべきことは次のようになります。
- 暗号文 \(1,2,\dots,N\) に対して
- 原文 \(1,2,\dots,N\) を重複なく割り当てる
- 割り当てたときのコストの合計を最小化する
つまり、\(N \times N\) のコスト表 \(cost[i][j][r]\) に対する割当問題です。
\(N \leq 5\) と非常に小さいため、これはビット DP で十分高速に解けます。
素朴に毎回、
- すべてのシフト量 \(r\)
- すべての対応関係
- すべての文字位置
を調べると、各クエリごとにかなり重くなります。
特に、不一致数を毎回最初から計算すると、同じ比較を何度も繰り返すことになります。
そこで、
\[ cost[i][j][r] \]
を常に最新の状態で保持しておきます。
1 文字だけ変更されたとき、その変更が影響するのは一部の \(cost\) だけです。
各クエリでは、その差分だけを \(O(NM)\) 程度で更新します。
アルゴリズム
1. 不一致数テーブルを持つ
次の 3 次元配列を持ちます。
\[ cost[i][j][r] \]
これは、暗号文 \(i\) と原文 \(j\) をシフト量 \(r\) で対応させたときの不一致数です。
初期状態では、全ての \(i,j,r\) について実際に文字列を比較して求めます。
2. 答えを求める
各シフト量 \(r\) について、最小の対応を求めます。
ビット DP を使います。
\[ dp[mask] \]
を、「すでに割り当てた原文の集合が mask であるときの最小コスト」とします。
mask のビット数を \(k\) とすると、次に割り当てる暗号文は \(k\) 番目です。
遷移は、まだ使っていない原文 \(j\) を選んで、
\[ dp[mask \cup \{j\}] = \min( dp[mask \cup \{j\}], dp[mask] + cost[k][j][r] ) \]
です。
最終的に、
\[ dp[(1<<N)-1] \]
がシフト量 \(r\) における最小コストです。
全ての \(r\) についてこれを計算し、その最小値が答えです。
3. クエリの処理
クエリ 1: 1 i p x
暗号文 \(S_i[p]\) の文字が変わります。
この位置が読み取り不能、つまり \(C_i[p]=1\) なら、そもそも比較対象ではないので \(cost\) は変化しません。
読み取れている場合、各原文 \(j\)、各シフト量 \(r\) について、
\[ T_j[(p+r) \bmod M] \]
と比較されます。
変更前の文字を old、変更後の文字を new、比較相手の文字を ch とすると、
ch == oldなら、以前は一致していたが変更後は不一致になるので \(+1\)ch == newなら、以前は不一致だったが変更後は一致するので \(-1\)- それ以外なら、不一致のままなので変化なし
として差分更新します。
クエリ 2: 2 i p b
ノイズ情報 \(C_i[p]\) が変わります。
1 から 0 になる、つまり新たに読み取れるようになった場合は、その位置の比較結果を \(cost\) に加えます。
逆に 0 から 1 になる、つまり読み取り不能になった場合は、その位置の比較結果を \(cost\) から引きます。
各原文 \(j\)、各シフト量 \(r\) について、
\[ S_i[p] \neq T_j[(p+r) \bmod M] \]
なら、加算または減算します。
クエリ 3: 3 j p x
原文 \(T_j[p]\) の文字が変わります。
この文字は、シフト量 \(r\) のとき、暗号文側の位置
\[ q = (p-r) \bmod M \]
と比較されます。
したがって、各暗号文 \(i\)、各シフト量 \(r\) について位置 \(q\) を求め、もし \(C_i[q]=0\) なら差分更新します。
変更前の文字を old、変更後の文字を new、比較相手の暗号文の文字を ch とすると、
ch == oldなら、以前は一致していたが変更後は不一致になるので \(+1\)ch == newなら、以前は不一致だったが変更後は一致するので \(-1\)- それ以外なら変化なし
です。
計算量
- 時間計算量:
初期化に \(O(N^2M^2)\)
各クエリについて、差分更新に \(O(NM)\)、答えの再計算に \(O(MN2^N)\)
よって全体で
$\( O(N^2M^2 + Q(MN + MN2^N)) \)$
です。
\(N \leq 5\) なので \(2^N\) は小さく、また \(MQ \leq 5 \times 10^4\) なので十分高速です。
- 空間計算量: \(O(N^2M)\)
主に cost[i][j][r] を保持するための領域です。
実装のポイント
入力の
C_i[p]は、問題文では0が読み取り可能、1が読み取り不能です。
実装では扱いやすいように、0を1、1を0に変換して保持しています。文字は
aからzを整数 \(0\) から \(25\) に変換しておくと、比較が高速になります。シフトによる位置計算では、実装は \(0\)-indexed です。
暗号文位置 \(p\) に対応する原文位置は
$\( (p+r) \bmod M \)$
です。
- クエリ 3 では、原文位置 \(p\) に対応する暗号文位置は
$\( (p-r) \bmod M \)$
になります。
コードでは、\(r\) を増やすごとに位置を 1 つずつ戻すことで、毎回の剰余計算を避けています。
ビット DP の遷移は毎回同じ形なので、あらかじめ「暗号文 \(i\) を割り当てる段階で使う遷移」を列挙しておくと実装が少し高速になります。
ソースコード
import sys
def main():
input = sys.stdin.buffer.readline
N, M, Q = map(int, input().split())
S = []
R = []
for _ in range(N):
S.append([c - 97 for c in input().strip()])
R.append([1 if c == 48 else 0 for c in input().strip()])
T = [[c - 97 for c in input().strip()] for _ in range(N)]
cost = [[[0] * M for _ in range(N)] for __ in range(N)]
doubled_T = [t + t for t in T]
for i in range(N):
si = S[i]
read_pos = [p for p, v in enumerate(R[i]) if v]
for j in range(N):
td = doubled_T[j]
arr = cost[i][j]
for r in range(M):
cnt = 0
for p in read_pos:
if si[p] != td[p + r]:
cnt += 1
arr[r] = cnt
full = 1 << N
full_mask = full - 1
popcnt = [0] * full
for mask in range(1, full):
popcnt[mask] = popcnt[mask >> 1] + (mask & 1)
trans_by_i = []
for i in range(N):
trans = []
for mask in range(full):
if popcnt[mask] == i:
rem = full_mask ^ mask
while rem:
lb = rem & -rem
j = lb.bit_length() - 1
trans.append((mask, mask | lb, j))
rem -= lb
trans_by_i.append(trans)
INF = 10 ** 9
def calc_answer():
ans = INF
cst = cost
trans_all = trans_by_i
last = full - 1
for r in range(M):
dp = [INF] * full
dp[0] = 0
for i in range(N):
row = cst[i]
for mask, nmask, j in trans_all[i]:
v = dp[mask] + row[j][r]
if v < dp[nmask]:
dp[nmask] = v
if dp[last] < ans:
ans = dp[last]
return ans
out = []
for _ in range(Q):
parts = input().split()
typ = parts[0][0] - 48
if typ == 1:
i = int(parts[1]) - 1
p = int(parts[2]) - 1
new = parts[3][0] - 97
old = S[i][p]
if old != new:
if R[i][p]:
cost_i = cost[i]
for j in range(N):
arr = cost_i[j]
tj = T[j]
idx = p
for r in range(M):
ch = tj[idx]
if ch == old:
arr[r] += 1
elif ch == new:
arr[r] -= 1
idx += 1
if idx == M:
idx = 0
S[i][p] = new
elif typ == 2:
i = int(parts[1]) - 1
p = int(parts[2]) - 1
new_read = 1 if parts[3][0] == 48 else 0
old_read = R[i][p]
if old_read != new_read:
sp = S[i][p]
cost_i = cost[i]
if new_read:
for j in range(N):
arr = cost_i[j]
tj = T[j]
idx = p
for r in range(M):
if sp != tj[idx]:
arr[r] += 1
idx += 1
if idx == M:
idx = 0
else:
for j in range(N):
arr = cost_i[j]
tj = T[j]
idx = p
for r in range(M):
if sp != tj[idx]:
arr[r] -= 1
idx += 1
if idx == M:
idx = 0
R[i][p] = new_read
else:
j = int(parts[1]) - 1
p = int(parts[2]) - 1
new = parts[3][0] - 97
old = T[j][p]
if old != new:
for i in range(N):
arr = cost[i][j]
si = S[i]
ri = R[i]
q = p
for r in range(M):
if ri[q]:
ch = si[q]
if ch == old:
arr[r] += 1
elif ch == new:
arr[r] -= 1
q -= 1
if q < 0:
q = M - 1
T[j][p] = new
out.append(str(calc_answer()))
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
posted:
last update: