概要

パスワード \(S\) の未確定部分の埋め方と \(N\) 人のエージェントへの送信順を最適に選び、認証成功数を最大化する問題です。\(N \leq 8\) という制約から、送信順の全探索（\(N!\) 通り）が可能です。

考察

重要な気づき①：送信順を固定すると各エージェントへの変換が確定する

送信順 \((\sigma_1, \sigma_2, \dots, \sigma_N)\) を決めると、\(m\) 番目のエージェントに送信する時点での累積変換 \(C^{(m)}\) が一意に定まります。

• \(C^{(1)} = \text{id}\)（恒等置換）
• \(C^{(m+1)} = A_{\sigma_m} \circ C^{(m)}\)

重要な気づき②：認証成功条件は \(S\) への制約に変換できる

エージェント \(\sigma_m\) の認証が成功する条件は、すべての位置 \(j\) で \(C^{(m)}_{S_j} = T_{\sigma_m, j}\) です。これは次と同値です：

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

つまり各エージェントの成功条件は、「\(S\) がある特定の列 \(R^{(m)}\) に等しい」という形になります。

重要な気づき③：複数のエージェントが同時に成功する条件

\(S\) は一度決めたら変えられないので、複数のエージェントが同時に成功するのは、それらのエージェントの要求列 \(R^{(m)}\) がすべて同一 の場合に限ります。

重要な気づき④：要求列が固定位置 \(B\) と矛盾しないか

\(B_j \neq 0\) の位置では \(S_j = B_j\) と固定されているため、\(R^{(m)}_j \neq B_j\) であればそのエージェントの認証は不可能です。

アプローチ

\(N \leq 8\) なので \(N! \leq 40320\) 通りの送信順を全探索できます。各送信順について、各エージェントの要求列を計算し、同じ要求列を持つエージェント数が最大になるものを探します。

アルゴリズム

1. 送信順の全列挙：\(N!\) 通りの順列をすべて試す。
2. 要求列の計算：各送信順に対して、累積変換 \(C^{(m)}\) を順に計算し、\(m\) 番目のエージェントの要求列 \(R^{(m)}_j = (C^{(m)})^{-1}(T_{\sigma_m, j})\) を求める。
3. 固定位置との整合性チェック：\(B_j \neq 0\) のとき \(R^{(m)}_j = B_j\) でなければ、そのエージェントは認証不可（無効とマーク）。
4. 同一要求列のグループ化：有効なエージェントの中で、同じ要求列を持つものの最大グループを求める。そのグループサイズが成功エージェント数。
5. 最大数と辞書順最小の追跡：全送信順を通じて、成功数の最大値と、その最大値を達成する要求列のうち辞書順最小のものを記録。
6. 成功数 0 の場合：固定位置は \(B_j\)、自由位置は \(1\)（最小値）で埋める。

計算量

• 時間計算量: \(O(N! \cdot N^2 \cdot L)\)
  • \(N! \leq 40320\) 通りの順列、各順列で \(N\) 個の要求列計算 \(O(NL)\)、\(N^2\) 組の要求列比較 \(O(N^2 L)\)
  • \(N=8, L=200\) で最大約 \(5 \times 10^8\) 程度の基本演算（C++ なら許容範囲）
• 空間計算量: \(O(N \cdot L)\)

実装のポイント

• 0-indexed 管理：入力値を \(-1\) して 0-indexed で統一し、出力時に \(+1\) する。

• 逆置換の計算：\(C^{(m)}\) から逆置換 \(C^{(m)}_{inv}\) を作り、要求列の計算を \(O(1)\)/要素で行う。

• 辞書順比較：C++ の vector 同士の < 演算子がそのまま辞書順比較になるため活用。

• next_permutation：順列の全列挙に STL の next_permutation を使い、実装を簡潔にする。

  ソースコード

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N,K,L;
    cin>>N>>K>>L;
    
    vector<int> B(L);
    for(int j=0;j<L;j++) cin>>B[j];
    
    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 k=0;k<K;k++){cin>>A[i][k]; A[i][k]--;}
    }
    
    int best_count=0;
    vector<int> best_S;
    
    vector<int> order(N);
    iota(order.begin(),order.end(),0);
    
    do {
        vector<int> C(K);
        iota(C.begin(),C.end(),0);
        
        vector<vector<int>> reqs;
        vector<bool> valid_flags;
        
        for(int m=0;m<N;m++){
            int agent=order[m];
            vector<int> C_inv(K);
            for(int k=0;k<K;k++) C_inv[C[k]]=k;
            
            vector<int> req(L);
            bool ok=true;
            for(int j=0;j<L;j++){
                req[j]=C_inv[T[agent][j]];
                if(B[j]!=0 && req[j]!=B[j]-1){
                    ok=false;
                    break;
                }
            }
            reqs.push_back(req);
            valid_flags.push_back(ok);
            
            // Update C: C' = A[agent] ∘ C
            vector<int> newC(K);
            for(int k=0;k<K;k++) newC[k]=A[agent][C[k]];
            C=newC;
        }
        
        // Group valid agents by requirement
        for(int m=0;m<N;m++){
            if(!valid_flags[m]) continue;
            int cnt=0;
            for(int m2=0;m2<N;m2++){
                if(!valid_flags[m2]) continue;
                if(reqs[m]==reqs[m2]) cnt++;
            }
            if(cnt>best_count||(cnt==best_count&&(best_S.empty()||reqs[m]<best_S))){
                best_count=cnt;
                best_S=reqs[m];
            }
        }
    } while(next_permutation(order.begin(),order.end()));
    
    if(best_count==0){
        best_S.resize(L);
        for(int j=0;j<L;j++){
            if(B[j]!=0) best_S[j]=B[j]-1;
            else best_S[j]=0;
        }
    }
    
    cout<<best_count<<"\n";
    for(int j=0;j<L;j++){
        cout<<best_S[j]+1<<" \n"[j==L-1];
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。