概要

送信順によって暗号変換規則 \(C\) が変わるため、各エージェントが「成功するために必要な元パスワード \(S\)」は順番依存で変化します。
ただし \(N \le 8\) と小さいので、全送信順を全探索し、各順序で達成可能な成功人数の最大値と辞書順最小の \(S\) を求め、最後に全体最適を選べます。

考察

重要な観察は次です。

• ある送信順を固定すると、各ステップでの変換規則 \(C\) は確定する。
• エージェント \(i\) がその時点で成功する条件は $\( (C_{S_1},\dots,C_{S_L}) = T_i \)\( なので、各位置 \)j\( で \)\( S_j = C^{-1}(T_{i,j}) \)\( が必要。 つまり、そのエージェント成功に必要な \)S\( は長さ \)L$ の1つの完全なパターンとして定まる。

このとき固定順序に対して：

• 各送信ステップ \(p\) に「成功用パターン」\(P_p\) ができる。
• 実際に選ぶ \(S\) は1つだけなので、成功するのは \(S\) と完全一致する \(P_p\) を持つエージェント群。
• よって、その順序での最大成功人数は
  「\(B\) と両立する（確定文字に矛盾しない）パターンの中で、同一パターンの最大出現回数」。

素朴に「どのエージェント集合を成功させるか」を状態DPすると、位置ごとの整合性や順序依存が複雑で実装も難しくなります。
本解法は \(N!\) 全探索（最大 \(8!=40320\)）で十分間に合うため、こちらが安全です。

アルゴリズム

1. 入力を 0-index 化（値域を \(0..K-1\)、\(B_j=0\) は \(-1\) に変換）。
2. エージェント順列を全列挙する。
3. 各順列について：
   • 初期変換 \(C\) を恒等置換にする。
   • 順にエージェントを処理：
     • 現在の \(C\) の逆写像 \(\mathrm{inv}\) を作る。
     • そのエージェントの必要パターンを
       \(P_p[j]=\mathrm{inv}[T_{i,j}]\) で作る。
     • 送信後更新 \(C \leftarrow A_i \circ C\)（コードでは newC[x] = A[i][C[x]]）。
   • 得られた \(N\) 個の \(P_p\) について、
     • \(B\) と矛盾しないものだけ候補。
     • 同一パターンの個数を数えて最大値 localBest を得る。
     • 同数なら辞書順最小パターンを採用。
   • もし候補が1つもなければ成功人数は 0。
     このとき辞書順最小の許容 \(S\) は「\(B_j\) が未確定なら 0（=値1）を入れる」。
4. 全順列の結果を比較し、
   • 成功人数最大
   • 同点なら辞書順最小の \(S\) を最終答えにする。
5. 1-index に戻して出力。

計算量

• 時間計算量: \(O(N! \cdot N \cdot (K + L) + N! \cdot N^2 \cdot L)\)
  実質的には \(O(N! \cdot N^2 \cdot L)\)（\(N \le 8\) なので十分高速）
• 空間計算量: \(O(N \cdot L + K)\)（順列ごとの作業領域含む）

実装のポイント

• 置換合成の向きに注意：更新は \(C' = A_i \circ C\)。

• 成功条件は \(S_j = C^{-1}(T_{i,j})\) なので、毎ステップで逆写像を作るのが簡単。

• 辞書順比較は vector<int> 同士の比較（C++ の辞書順比較）を使うと楽。

• 成功人数0の場合でも、問題は辞書順最小の実現可能 \(S\) を要求するので必ず処理する。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, L;
    cin >> N >> K >> L;

    vector<int> B(L);
    for (int j = 0; j < L; j++) {
        cin >> B[j];
        --B[j]; // 0->-1, 1..K -> 0..K-1
    }

    vector<vector<int>> T(N, vector<int>(L));
    vector<vector<int>> A(N, vector<int>(K));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < L; j++) {
            cin >> T[i][j];
            --T[i][j];
        }
        for (int x = 0; x < K; x++) {
            cin >> A[i][x];
            --A[i][x];
        }
    }

    int ALL = 1 << N;

    // precompute composed permutation for each subset mask in "send order":
    // starting C = id, for each bit i in ascending index if in mask, C = A_i o C
    vector<array<int,8>> Cmask(ALL);
    for (int m = 0; m < ALL; m++) {
        for (int x = 0; x < K; x++) Cmask[m][x] = x;
    }
    for (int m = 1; m < ALL; m++) {
        int b = __builtin_ctz(m);
        int pm = m ^ (1 << b);
        for (int x = 0; x < K; x++) {
            Cmask[m][x] = A[b][ Cmask[pm][x] ];
        }
    }

    // need[mask][i][v] : for state mask (already sent set), if send i next, then S_j must be v
    // v in 0..K-1, or -1 impossible
    static int8_t need[1<<8][8][8];
    for (int mask = 0; mask < ALL; mask++) {
        for (int i = 0; i < N; i++) {
            for (int v = 0; v < K; v++) need[mask][i][v] = -1;
            if (mask & (1 << i)) continue;
            // inverse of Cmask[mask]
            int inv[8];
            for (int x = 0; x < K; x++) inv[Cmask[mask][x]] = x;
            for (int t = 0; t < K; t++) {
                need[mask][i][t] = (int8_t)inv[t];
            }
        }
    }

    // good[mask][j]: among agents in mask, all required S_j equal and compatible with B_j
    vector<vector<char>> good(ALL, vector<char>(L, 1));
    for (int mask = 0; mask < ALL; mask++) {
        for (int j = 0; j < L; j++) {
            int val = -2; // unset
            bool ok = true;
            for (int i = 0; i < N; i++) if (mask & (1 << i)) {
                int req = need[mask ^ (1 << i)][i][ T[i][j] ]; // careful? actually state before sending i within topological?
                // Not valid like this. For mask-only feasibility, requirement depends on prefix state, not just final set.
                // So we cannot do this precompute this way.
            }
        }
    }

    // We'll do DP over sequences with constraints aggregated incrementally.
    // For each mask, keep:
    // dp[mask] = max successes achievable by some order consisting exactly of mask agents (success counted within those sends),
    // and for each position j, required value req[mask][j] if that best is achievable; but multiple possibilities.
    // Need lexicographic minimal S among global optimum -> handle via two-phase:
    // 1) compute best possible success count with DP feasibility per mask and position constraints as bitsets.
    //    For each mask, we keep all possible "requirement patterns"? too huge.
    // Alternative: since N<=8, brute force all orders (40320) and for each derive feasible S and success count.
    // For each order, success set determined by S; but S can be chosen to maximize successes in that fixed order.
    // For fixed order, each agent at step p imposes for each j a value r_{p,j} = inv(C_before)(T_i[j]).
    // Need choose S_j (respecting B) to maximize count of p such that all j match r_{p,j}.
    // That means each agent corresponds to full length pattern R_p[1..L]. Agent succeeds iff S equals that pattern exactly.
    // So with one S, in a fixed order, successful agents are those p whose pattern equals S.
    // Therefore max success in that order is max frequency of an identical feasible pattern among agents in that order,
    // but pattern itself independent of order position via C_before so depends on prefix.
    // N small => for each permutation, compute transformed patterns P_i (length L), then count duplicates feasible with B.
    // pick max count; and lexicographically smallest pattern among achieving max.
    // Global max over permutations.

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);

    int bestCnt = -1;
    vector<int> bestS(L, 0);

    sort(idx.begin(), idx.end());
    do {
        array<int,8> C{};
        for (int x = 0; x < K; x++) C[x] = x;

        vector<vector<int>> P(N, vector<int>(L));
        for (int p = 0; p < N; p++) {
            int i = idx[p];
            int inv[8];
            for (int x = 0; x < K; x++) inv[C[x]] = x;
            for (int j = 0; j < L; j++) {
                P[p][j] = inv[T[i][j]];
            }
            array<int,8> nC{};
            for (int x = 0; x < K; x++) nC[x] = A[i][C[x]];
            C = nC;
        }

        // count identical feasible patterns
        int localBest = 0;
        vector<int> localS(L, K); // sentinel large
        for (int a = 0; a < N; a++) {
            bool feasible = true;
            for (int j = 0; j < L; j++) {
                if (B[j] != -1 && B[j] != P[a][j]) { feasible = false; break; }
            }
            if (!feasible) continue;
            int cnt = 0;
            for (int b = 0; b < N; b++) {
                if (P[b] == P[a]) cnt++;
            }
            if (cnt > localBest) {
                localBest = cnt;
                localS = P[a];
            } else if (cnt == localBest && cnt > 0) {
                if (P[a] < localS) localS = P[a];
            }
        }

        // if no feasible pattern from agents, can still choose any S but success 0
        if (localBest == 0) {
            vector<int> s(L);
            for (int j = 0; j < L; j++) s[j] = (B[j] == -1 ? 0 : B[j]);
            localS = s;
        }

        if (localBest > bestCnt) {
            bestCnt = localBest;
            bestS = localS;
        } else if (localBest == bestCnt) {
            if (localS < bestS) bestS = localS;
        }

    } while (next_permutation(idx.begin(), idx.end()));

    cout << bestCnt << "\n";
    for (int j = 0; j < L; j++) {
        if (j) cout << ' ';
        cout << (bestS[j] + 1);
    }
    cout << "\n";
    return 0;
}

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