E - 暗号変換装置とパスワード認証 / Cipher Conversion Device and Password Authentication Editorial by admin
Gemini 3.0 Flash (Thinking)概要
この問題は、パスワード \(S\) の構成と、エージェントへの送信順序を最適化して、認証成功人数を最大化する問題です。 送信順序を固定すると、各ステップでエージェントが認証されるために必要なパスワード \(S\) が一意に定まることを利用し、順序の全探索とパスワードの候補の管理を組み合わせることで解を導きます。
考察
1. 送信順と置換の遷移
エージェントの人数 \(N\) と置換のサイズ \(K\) はともに最大 8 と非常に小さいです。一方で、パスワードの長さ \(L\) は 200 まであります。 送信順序を \(\sigma = (\sigma_1, \sigma_2, \dots, \sigma_N)\) とすると、ステップ \(k\) における装置の置換 \(C^{(k)}\) は、それ以前に送信したエージェントの置換 \(A\) の合成によって一意に決まります。 - \(C^{(1)} = \text{id}\) （恒等置換） - \(C^{(k+1)} = A_{\sigma_k} \circ C^{(k)}\)
2. パスワード \(S\) の一意性
ステップ \(k\) でエージェント \(\sigma_k\) の認証を成功させるためには、各 \(j \in \{1, \dots, L\}\) について \(C^{(k)}_{S_j} = T_{\sigma_k, j}\) が成立する必要があります。 \(C^{(k)}\) は置換（全単射）であるため、その逆置換を \(D^{(k)}\) とすると、\(S_j = D^{(k)}_{T_{\sigma_k, j}}\) として \(S\) の各要素が一意に定まります。
この \(S\) が高橋君のメモ \(B\) と矛盾しない（\(B_j \neq 0\) ならば \(S_j = B_j\)）場合、この \(S\) は有効なパスワード候補となります。
3. 最適化の戦略
送信順序 \(\sigma\) は \(N! = 8! = 40320\) 通りあります。各順序において、認証を成功させたいエージェントを 1 人選ぶ（そのステップを \(k\) とする）と、パスワード \(S\) が一意に決まります。その \(S\) を用いたときに、同じ順序 \(\sigma\) 内の他のステップ \(m\) で認証が成功するかどうかは、\(C^{(m)}_{S_j} = T_{\sigma_m, j}\) がすべての \(j\) で成り立つかを確認するだけで判定できます。
アルゴリズム
置換のインデックス化: \(K!\) 通りのすべての置換を列挙し、それぞれに ID を振ります。また、ある置換 \(C\) にエージェント \(i\) の置換 \(A_i\) を合成した後の置換 ID を前計算しておきます。
パスワード候補の抽出: 各エージェント \(i\) と、装置のあり得る状態（置換 \(C\)）のすべてのペア \((i, C)\) について、認証を成功させるために必要なパスワード \(S\) を計算します。
- \(S\) がメモ \(B\) と矛盾しなければ、その \(S\) を保存します。
- 保存したすべての \(S\) を辞書順でソートし、重複を除いてユニークな ID を割り当てます。これにより、パスワードの比較を整数 ID の比較に置き換えられます。
送信順序の全探索: エージェントの順序 \(N!\) 通りを
next_permutation等で全探索します。- 各順序において、各ステップ \(k\) での置換 \(C^{(k)}\) を順次計算します。
- 各ステップ \(k\) でエージェント \(\sigma_k\) が認証可能（\(S\) が存在する）なら、その \(S\) の ID を記録します。
- 記録された \(S\) の ID ごとに、その順序で何人が認証成功するかをカウントします。
結果の更新: 最大人数を更新し、人数が同じ場合は \(S\) の ID が最小（＝辞書順最小）のものを保持します。
計算量
事前計算: \(O(N \cdot K! \cdot K)\) （遷移）および \(O(N \cdot K! \cdot L)\) （候補 \(S\) の作成）
ソート: \(O((N \cdot K!) \log (N \cdot K!) \cdot L)\)
全探索: \(O(N! \cdot N^2)\)
- \(N=8, K=8, L=200\) のとき、\(N! = 40320, K! = 40320\) です。
- \(N! \cdot N^2 \approx 4 \times 10^4 \cdot 64 \approx 2.5 \times 10^6\) となり、十分に高速です。
時間計算量: \(O(N \cdot K! \cdot (K+L) + (N \cdot K!) \log (N \cdot K!) \cdot L + N! \cdot N^2)\)
空間計算量: \(O(N \cdot K! \cdot L)\) （候補パスワードの保存）
実装のポイント
置換のハッシュ化: \(K \le 8\) なので、置換を 8 進数とみなして整数に変換すると、配列で高速に ID を管理できます。
辞書順最小の \(S\): 最大人数が 0 の場合、メモ \(B\) の不確定な部分をすべて最小の値（1）にしたものが辞書順最小の回答になります。
ID 管理: 候補となる \(S\) を ID 化する際、元の \(S\) の値を復元できるように
unique_Usのようなリストを保持しておきます。ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Array to map permutations to indices based on their base-8 representation
// Since K <= 8, 8^8 = 16777216 is sufficient.
int perm_to_idx_arr[16777216];
struct TempU {
int i, cp;
vector<uint8_t> U;
};
int main() {
// Faster I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, L;
if (!(cin >> N >> K >> L)) return 0;
// Read templates and information for each agent
vector<int> B(L);
for (int i = 0; i < L; ++i) {
cin >> B[i];
B[i]--; // Convert to 0-indexed, -1 means unassigned
}
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]--; // 0-indexed
}
for (int j = 0; j < K; ++j) {
cin >> A[i][j];
A[i][j]--; // 0-indexed
}
}
// Generate all permutations of {0, ..., K-1}
vector<vector<int>> all_perms;
vector<int> p(K);
iota(p.begin(), p.end(), 0);
int K_fact = 0;
for (int i = 0; i < 16777216; ++i) perm_to_idx_arr[i] = -1;
do {
all_perms.push_back(p);
int id = 0;
for (int x : p) id = (id << 3) | x;
perm_to_idx_arr[id] = K_fact++;
} while (next_permutation(p.begin(), p.end()));
// Pre-calculate the transformation update: C' = A_i ∘ C
vector<vector<int>> next_C_idx(N, vector<int>(K_fact));
for (int i = 0; i < N; ++i) {
for (int cp = 0; cp < K_fact; ++cp) {
int next_id = 0;
for (int x = 0; x < K; ++x) {
next_id = (next_id << 3) | A[i][all_perms[cp][x]];
}
next_C_idx[i][cp] = perm_to_idx_arr[next_id];
}
}
// Pre-calculate possible passwords U for each (agent i, transformation cp)
vector<TempU> all_consistent;
all_consistent.reserve(N * K_fact);
for (int i = 0; i < N; ++i) {
for (int cp = 0; cp < K_fact; ++cp) {
const auto& C = all_perms[cp];
bool ok = true;
// Consistency check: S_j must satisfy C(S_j) = T_{i,j}.
// If S_j is fixed to B_j, then C(B_j) = T_{i,j} must hold.
for (int j = 0; j < L; ++j) {
if (B[j] != -1 && C[B[j]] != T[i][j]) {
ok = false;
break;
}
}
if (ok) {
vector<int> D(K);
for (int x = 0; x < K; ++x) D[C[x]] = x; // D is the inverse of C
vector<uint8_t> U(L);
for (int j = 0; j < L; ++j) U[j] = (uint8_t)D[T[i][j]];
all_consistent.push_back({i, cp, U});
}
}
}
// Sort consistent passwords to assign unique IDs based on lexicographical order
sort(all_consistent.begin(), all_consistent.end(), [](const TempU& a, const TempU& b) {
return a.U < b.U;
});
vector<vector<int>> consistent_id(N, vector<int>(K_fact, -1));
vector<vector<uint8_t>> unique_Us;
unique_Us.reserve(all_consistent.size());
int current_id = -1;
for (int i = 0; i < (int)all_consistent.size(); ++i) {
if (i == 0 || all_consistent[i].U != all_consistent[i - 1].U) {
current_id++;
unique_Us.push_back(all_consistent[i].U);
}
consistent_id[all_consistent[i].i][all_consistent[i].cp] = current_id;
}
// Iterate through all permutations of agents to find the maximum authentication count
int max_auth = 0;
int best_S_id = -1;
vector<int> agent_p(N);
iota(agent_p.begin(), agent_p.end(), 0);
// Initial identity permutation index
int id_val = 0;
for (int x = 0; x < K; ++x) id_val = (id_val << 3) | x;
int id_perm_idx = perm_to_idx_arr[id_val];
do {
int curr_C = id_perm_idx;
vector<int> agent_ids(N);
for (int k = 0; k < N; ++k) {
agent_ids[k] = consistent_id[agent_p[k]][curr_C];
curr_C = next_C_idx[agent_p[k]][curr_C];
}
for (int k = 0; k < N; ++k) {
int id = agent_ids[k];
if (id == -1) continue;
// Avoid redundant counts for the same ID in one agent permutation
bool already_checked = false;
for (int m = 0; m < k; ++m) {
if (agent_ids[m] == id) {
already_checked = true;
break;
}
}
if (already_checked) continue;
int cnt = 0;
for (int m = 0; m < N; ++m) {
if (agent_ids[m] == id) cnt++;
}
if (cnt > max_auth) {
max_auth = cnt;
best_S_id = id;
} else if (cnt == max_auth && max_auth > 0) {
// Since IDs represent lexicographical rank, pick the smaller ID
if (id < best_S_id) {
best_S_id = id;
}
}
}
} while (next_permutation(agent_p.begin(), agent_p.end()));
// Output the results
cout << max_auth << "\n";
if (max_auth == 0) {
// If no agent can be authenticated, the smallest S is B with unknown values as 1
for (int i = 0; i < L; ++i) {
cout << (B[i] == -1 ? 1 : B[i] + 1) << (i == L - 1 ? "" : " ");
}
cout << "\n";
} else {
// Output the lexicographically smallest S achieving max_auth
for (int i = 0; i < L; ++i) {
cout << (int)unique_Us[best_S_id][i] + 1 << (i == L - 1 ? "" : " ");
}
cout << "\n";
}
return 0;
}
この解説は gemini-3-flash-thinking によって生成されました。
posted:
last update: