概要

パスワード \(S\) の埋め方と、エージェントへの送信順を自由に選び、認証成功人数を最大化します。
\(L\) は大きいですが \(N,K \leq 8\) と小さいため、送信順を全探索しつつ「その時点で成功するために必要な \(S\)」だけを候補として扱います。

考察

重要な点は、ある送信順を固定すると、各時点での変換規則 \(C\) はパスワード \(S\) に依存しないことです。

なぜなら、送信後の更新は認証の成否に関係なく必ず

\[ C' = A_i \circ C \]

で行われるからです。

したがって、送信順が決まれば、各エージェントへ送信する直前の \(C\) は一意に決まります。

---

ある時点で変換規則が \(C\)、送信相手がエージェント \(i\) だとします。

認証が成功する条件は、すべての位置 \(j\) について

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

となることです。

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

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

です。

例えば、現在の変換が

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

で、認証コードが \((3,1,1)\) なら、必要なパスワードは \((2,3,3)\) です。

ただし、この候補がメモ \(B\) の固定済み位置と矛盾している場合、その時点でそのエージェントを成功させることは不可能です。

---

つまり、送信順を \(1\) つ固定すると、各送信時点には

• 「このパスワードなら成功する」という候補 \(S\)
• あるいは「どんな有効な \(S\) でも成功不可能」

のどちらかが対応します。

そのため、固定した送信順に対して、同じ候補パスワードが何回現れるかを数えれば、そのパスワードを選んだときの成功人数が分かります。

例えば、ある送信順で候補が

\[ X, Y, X, Z, X \]

のように現れたなら、パスワード \(X\) を選ぶことで \(3\) 人成功できます。

---

素朴に全パスワードを試すと、未確定位置が多い場合に最大で

\[ K^L \]

通りあり、\(K=8, L=200\) では到底不可能です。

一方、送信順は最大でも

\[ 8! = 40320 \]

通りなので、送信順を全探索し、その中で現れる候補パスワードだけを調べれば十分です。

最適解で成功人数が \(1\) 以上なら、少なくともどこかの送信時点で成功しているため、そのパスワードは必ずこの方法で候補として現れます。

成功人数の最大値が \(0\) の場合は、どのパスワードでも成功できないので、メモ \(B\) を満たす辞書順最小のもの、つまり未確定位置をすべて \(1\) にしたものを出力すればよいです。

アルゴリズム

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

DFS の状態は次の通りです。

• すでに送信したエージェント集合 mask
• 現在の深さ depth
• 現在の変換規則 \(C\)
• ここまでの各送信時点での候補パスワード ID

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

1. 候補パスワードを求める

現在の \(C\) から逆写像 \(C^{-1}\) を作ります。

エージェント \(i\) をこの時点で成功させるために必要なパスワード \(U\) は

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

です。

この \(U\) が、メモ \(B\) の固定済み位置と矛盾していないかを確認します。

• 矛盾する場合：この時点で成功可能な有効パスワードはないので ID を -1 とする
• 矛盾しない場合：\(U\) を候補パスワードとして登録し、ID を得る

同じパスワードは unordered_map で同じ ID にまとめます。

2. 変換規則を更新する

エージェント \(i\) に送信した後の変換規則は

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

です。

コード上では

nextC[x] = Aperm[i][C[x]];

として計算しています。

3. 全員に送信し終えたら更新する

深さが \(N\) になったら、送信順が \(1\) つ完成しています。

この送信順において、各時点の候補パスワード ID が記録されています。

同じ ID が何回出現したかを数え、その最大値で bestCnt[id] を更新します。

つまり、bestCnt[id] は

パスワード ID id を選んだとき、ある送信順で最大何人成功できるか

を表します。

4. 答えを選ぶ

全探索後、すべての候補パスワードについて bestCnt を見ます。

• bestCnt が最大のものを選ぶ
• 同じ成功人数なら、辞書順最小のパスワードを選ぶ

もし最大成功人数が \(0\) なら、候補パスワードは使わず、メモ \(B\) の未確定位置をすべて \(1\) にしたものを出力します。

計算量

送信順の DFS 木の辺数を

\[ E = \sum_{r=1}^{N} {}_NP_r \]

とします。

\(N \leq 8\) なので、最大でも十分小さいです。

各辺で長さ \(L\) の候補パスワードを作るため、計算量はおおよそ次の通りです。

• 時間計算量: \(O(E(L+K) + N! \cdot N^2)\)
• 空間計算量: \(O(E \cdot L)\)

ここで、\(O(E \cdot L)\) は候補パスワードを文字列として保存するための領域です。

制約上、\(N=8, L=200\) でも十分間に合います。

実装のポイント

• 入力値は扱いやすいように \(0\) 始まりに変換しています。

• \(B_j=0\) の未確定位置はコード中では -1 として管理しています。

• 固定済み位置だけを fixedPos に保存しておくことで、候補パスワードが \(B\) と矛盾するかを効率よく確認できます。

• 候補パスワードは string にして unordered_map で ID 化しています。

  • 各要素は \(1\) から \(K\) の小さい値なので、文字として格納しても辞書順比較がそのまま使えます。

• ans == 0 の場合は、どのパスワードでも最大成功人数 \(0\) を達成できるため、辞書順最小になるように未確定位置をすべて \(1\) にします。

  ソースコード

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

int N, K, L;
vector<int> Bv, fixedPos;
vector<vector<int>> T;
vector<array<int, 8>> Aperm;

unordered_map<string, int> idMap;
vector<int> bestCnt;
array<int, 8> pathIds;

int getId(const array<int, 8>& invC, int agent) {
    const auto& Ti = T[agent];

    for (int pos : fixedPos) {
        if (invC[Ti[pos]] != Bv[pos]) return -1;
    }

    string s;
    s.resize(L);
    for (int j = 0; j < L; ++j) {
        s[j] = char(invC[Ti[j]] + 1);
    }

    auto it = idMap.find(s);
    if (it != idMap.end()) return it->second;

    int id = (int)bestCnt.size();
    bestCnt.push_back(0);
    idMap.emplace(std::move(s), id);
    return id;
}

void updateLeaf() {
    for (int a = 0; a < N; ++a) {
        int id = pathIds[a];
        if (id < 0) continue;

        bool seen = false;
        for (int b = 0; b < a; ++b) {
            if (pathIds[b] == id) {
                seen = true;
                break;
            }
        }
        if (seen) continue;

        int cnt = 0;
        for (int b = a; b < N; ++b) {
            if (pathIds[b] == id) ++cnt;
        }
        bestCnt[id] = max(bestCnt[id], cnt);
    }
}

void dfs(int depth, int mask, const array<int, 8>& C) {
    if (depth == N) {
        updateLeaf();
        return;
    }

    array<int, 8> invC{};
    for (int x = 0; x < K; ++x) {
        invC[C[x]] = x;
    }

    for (int i = 0; i < N; ++i) {
        if (mask & (1 << i)) continue;

        int id = getId(invC, i);
        pathIds[depth] = id;

        array<int, 8> nextC{};
        for (int x = 0; x < K; ++x) {
            nextC[x] = Aperm[i][C[x]];
        }

        dfs(depth + 1, mask | (1 << i), nextC);
    }
}

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

    cin >> N >> K >> L;

    Bv.resize(L);
    for (int j = 0; j < L; ++j) {
        int x;
        cin >> x;
        if (x == 0) {
            Bv[j] = -1;
        } else {
            Bv[j] = x - 1;
            fixedPos.push_back(j);
        }
    }

    T.assign(N, vector<int>(L));
    Aperm.resize(N);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < L; ++j) {
            cin >> T[i][j];
            --T[i][j];
        }
        for (int k = 0; k < K; ++k) {
            cin >> Aperm[i][k];
            --Aperm[i][k];
        }
    }

    long long edges = 0, p = 1;
    for (int r = 1; r <= N; ++r) {
        p *= (N - r + 1);
        edges += p;
    }

    idMap.max_load_factor(0.7);
    idMap.reserve((size_t)edges);

    array<int, 8> initC{};
    for (int x = 0; x < K; ++x) initC[x] = x;

    dfs(0, 0, initC);

    int ans = 0;
    string bestS;
    bool found = false;

    for (const auto& kv : idMap) {
        int cnt = bestCnt[kv.second];
        if (cnt > ans || (cnt == ans && cnt > 0 && (!found || kv.first < bestS))) {
            ans = cnt;
            bestS = kv.first;
            found = true;
        }
    }

    if (ans == 0) {
        bestS.resize(L);
        for (int j = 0; j < L; ++j) {
            bestS[j] = char((Bv[j] == -1 ? 0 : Bv[j]) + 1);
        }
    }

    cout << ans << '\n';
    for (int j = 0; j < L; ++j) {
        if (j) cout << ' ';
        cout << (int)(unsigned char)bestS[j];
    }
    cout << '\n';

    return 0;
}

---

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