概要

送信順によって変化する置換 \(C\) のもとで、各エージェントが成功するために必要なパスワード \(S\) は一意に決まります。
したがって、すべての送信順を DFS で調べながら、「同じ \(S\) を要求する成功候補」が最大で何回現れるかを数えます。

考察

ある時点で装置の変換規則が置換 \(C\) であるとします。

エージェント \(i\) の認証コードは \(T_i\) なので、認証が成功する条件は

\[ (C_{S_1}, C_{S_2}, \dots, C_{S_L}) = T_i \]

です。

これは各位置 \(j\) について

\[ C_{S_j} = T_{i,j} \]

であることを意味します。

\(C\) は置換なので逆写像 \(C^{-1}\) が存在します。したがって、エージェント \(i\) がこの時点で成功するためのパスワードは一意に

\[ S_j = C^{-1}(T_{i,j}) \]

と決まります。

つまり、現在の \(C\) とエージェント \(i\) が決まれば、「このエージェントを成功させるために必要な \(S\)」も一意に決まります。

例えば、\(K=3\) で

\[ C = (2,3,1) \]

つまり \(1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 1\) だとします。
このとき \(C^{-1}\) は

\[ 2 \mapsto 1, 3 \mapsto 2, 1 \mapsto 3 \]

です。

もし \(T_i = (2,1,3)\) なら、成功に必要な \(S\) は

\[ (C^{-1}(2), C^{-1}(1), C^{-1}(3)) = (1,3,2) \]

になります。

---

ここで重要なのは、パスワード \(S\) は最初に一度だけ決めて、その後変更できないことです。

したがって、ある送信順において複数のエージェントを成功させるには、それぞれの時点で要求されるパスワードがすべて同じである必要があります。

つまり、ある送信順に対して、

• エージェント \(i\) をその時点で成功させるための候補 \(S\)
• それがメモ \(B\) と矛盾しないか

を調べ、同じ候補 \(S\) が何回出てくるかを数えればよいです。

---

素朴にパスワード \(S\) を全探索すると、未確定位置が多い場合に最大で

\[ K^L \]

通りあり、\(K \leq 8, L \leq 200\) なので不可能です。

一方で、エージェント数は

\[ N \leq 8 \]

と小さいため、送信順は最大でも

\[ 8! = 40320 \]

通りです。

そこで、パスワードを全探索するのではなく、送信順を全探索し、その中で「成功に必要なパスワード」を逆算します。

アルゴリズム

DFS で送信順を全探索します。

状態として、

• すでに送信したエージェント集合 mask
• 現在の置換 \(C\)

を持ちます。

初期状態では、

\[ C_x = x \]

です。

DFS の各状態で、まだ送信していないエージェント \(i\) を次に選びます。

1. エージェント \(i\) が成功可能か調べる

現在の置換が \(C\) のとき、成功に必要なパスワード候補は

\[ S_j = C^{-1}(T_{i,j}) \]

です。

ただし、この \(S\) はメモ \(B\) と一致していなければなりません。

\(B_j \neq 0\) の位置では \(S_j = B_j\) が必要です。
これは

\[ C_{B_j} = T_{i,j} \]

と同値です。

そのため、固定済みの位置については、候補列全体を作る前に矛盾を確認できます。

同じ値 \(x\) が \(B\) の固定位置に複数回出てくる場合、それらすべてについて \(T_{i,j}\) は同じ値でなければなりません。
そうでなければ、どんな \(C\) でも成功不可能です。

コードでは各エージェントについて事前に、

constraints[i]

として

\[ C_x = v \]

であるべき条件をまとめています。

現在の \(C\) がこの条件を満たすなら、実際に

\[ S = C^{-1}(T_i) \]

を作ります。

2. 同じ候補 \(S\) の出現回数を数える

現在の DFS の経路は、ある送信順の途中までを表しています。

そこで辞書 counts を使って、

counts[S] = これまでの送信順で候補 S が出てきた回数

を管理します。

もし今回のエージェント \(i\) によって候補 \(S\) が得られたなら、

counts[S] += 1

します。

この値が、現在の送信順においてパスワード \(S\) を選んだときに成功する人数です。

したがって、counts[S] がこれまでの最大値を超えたら答えを更新します。
同じ最大値なら、辞書順で小さい \(S\) を採用します。

3. 置換を更新して再帰する

エージェント \(i\) への送信後、成功・失敗に関係なく置換は更新されます。

新しい置換は

\[ C' = A_i \circ C \]

です。

つまり各 \(x\) について

\[ C'_x = A_{i,C_x} \]

になります。

この新しい \(C'\) で DFS を続けます。

再帰から戻ったら、counts の変更を元に戻します。

---

DFS の流れを擬似コードで書くと次のようになります。

dfs(mask, C):
    if 全員送信済み:
        return

    for i in 未送信のエージェント:
        if 現在の C でエージェント i の固定条件を満たす:
            S = C^{-1}(T_i)
            counts[S] += 1
            答えを更新

        dfs(mask に i を追加, A_i ∘ C)

        counts[S] を元に戻す

---

最後に、もし一度も成功候補が現れなかった場合、最大成功人数は \(0\) です。

この場合はどのパスワードを選んでも最大値 \(0\) を達成できます。
よって、メモ \(B\) に従う辞書順最小のパスワード、つまり未確定位置をすべて \(1\) にしたものを出力します。

計算量

送信順の途中状態数は

\[ \sum_{r=0}^{N} {}_NP_r \]

です。

これは \(O(N!)\) とみなせます。

各遷移で、

• 固定条件の確認に \(O(K)\)
• 候補パスワードの生成に \(O(L)\)

かかります。

したがって、

• 時間計算量: \(O(NL + N!(K+L))\)
• 空間計算量: \(O(N(L+K) + DK)\)

です。

ここで \(D\) は DFS 中に現れる異なる置換の個数で、最大でも

\[ D \leq \min(K!, \sum_{r=0}^{N} {}_NP_r) \]

です。

制約では \(N,K \leq 8\), \(L \leq 200\) なので十分高速です。

実装のポイント

• 入力は \(1\) 始まりですが、実装では扱いやすいように \(0\) 始まりに変換しています。

• 置換 \(C\) は C[x] = C_x という配列として持ちます。

• 置換の合成 \(A_i \circ C\) は、各 \(x\) について A_i[C[x]] です。

• 現在の \(C\) に対する逆置換 \(C^{-1}\) は何度も使うため、キャッシュしています。

• Python では bytes と translate を使うことで、列全体の変換を高速に行っています。

• bytes の辞書順比較は整数列の辞書順比較と一致するため、辞書順最小の更新にもそのまま使えます。

• DFS では counts を更新したあと、再帰から戻ると必ず元に戻す必要があります。これはバックトラックの基本です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p = 0
    N, K, L = data[p], data[p + 1], data[p + 2]
    p += 3

    B_raw = data[p:p + L]
    p += L
    B = [x - 1 if x != 0 else -1 for x in B_raw]

    base_table = bytes(range(256))

    T = []
    Atrans = []

    for _ in range(N):
        T.append(bytes([x - 1 for x in data[p:p + L]]))
        p += L

        a = [x - 1 for x in data[p:p + K]]
        p += K

        arr = bytearray(base_table)
        for i, v in enumerate(a):
            arr[i] = v
        Atrans.append(bytes(arr))

    fixed = [(idx, b) for idx, b in enumerate(B) if b >= 0]

    constraints = []
    for i in range(N):
        req = [-1] * K
        ok = True
        ti = T[i]
        for idx, b in fixed:
            v = ti[idx]
            if req[b] == -1:
                req[b] = v
            elif req[b] != v:
                ok = False
                break

        if not ok:
            constraints.append(None)
        else:
            constraints.append(tuple((s, req[s]) for s in range(K) if req[s] != -1))

    identity = bytes(range(K))
    inv_cache = {identity: base_table}

    def get_inv_table(C):
        tab = inv_cache.get(C)
        if tab is not None:
            return tab

        inv = [0] * K
        for i, v in enumerate(C):
            inv[v] = i

        arr = bytearray(base_table)
        for i in range(K):
            arr[i] = inv[i]

        tab = bytes(arr)
        inv_cache[C] = tab
        return tab

    sys.setrecursionlimit(1000000)

    full_mask = (1 << N) - 1
    counts = {}

    best = 0
    best_s = None

    def dfs(mask, C):
        nonlocal best, best_s

        if mask == full_mask:
            return

        for i in range(N):
            bit = 1 << i
            if mask & bit:
                continue

            added = False
            cand = None
            prev = 0

            cons = constraints[i]
            if cons is not None:
                ok = True
                for s, v in cons:
                    if C[s] != v:
                        ok = False
                        break

                if ok:
                    cand = T[i].translate(get_inv_table(C))
                    prev = counts.get(cand, 0)
                    now = prev + 1
                    counts[cand] = now

                    if now > best:
                        best = now
                        best_s = cand
                    elif now == best and (best_s is None or cand < best_s):
                        best_s = cand

                    added = True

            dfs(mask | bit, C.translate(Atrans[i]))

            if added:
                if prev:
                    counts[cand] = prev
                else:
                    del counts[cand]

    dfs(0, identity)

    if best_s is None:
        ans = [b + 1 if b >= 0 else 1 for b in B]
    else:
        ans = [x + 1 for x in best_s]

    print(best)
    print(*ans)

if __name__ == "__main__":
    main()

---

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