結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2025-12-14 19:46:17 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,707 bytes |
| 記録 | |
| コンパイル時間 | 2,106 ms |
| コンパイル使用メモリ | 201,380 KB |
| 実行使用メモリ | 26,228 KB |
| スコア | 9,291,800 |
| 平均クエリ数 | 80.28 |
| 最終ジャッジ日時 | 2025-12-25 01:40:33 |
| 合計ジャッジ時間 | 377,066 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 93 TLE * 7 |
ソースコード
// By Gemini 3 Pro 2nd attempt
/**
* 30 Parallel Mixed Hit & Blow Solver (High Accuracy Ver.)
* * Strategy:
* 1. Maintain a set of possible candidates for the *remaining* hidden strings.
* 2. Select the next query by minimizing the sum of squared group sizes (Entropy Maximization).
* - If candidates are few (< 2000), evaluate ALL candidates as potential queries.
* - If many, sample a larger subset (e.g., 200) to estimate the best query.
* 3. Filter candidates based on the "Bag" of responses, carefully excluding
* the (5,0) responses generated by already-found strings.
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>
#include <map>
using namespace std;
// Holds Hit & Blow result
struct Result {
int h, b;
bool operator==(const Result& other) const {
return h == other.h && b == other.b;
}
};
// Calculate Hit & Blow
Result calc_hb(const string& secret, const string& query) {
int h = 0;
int b = 0;
// Hit count
for (int i = 0; i < 5; ++i) {
if (secret[i] == query[i]) h++;
}
// Blow count
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (i != j && secret[i] == query[j]) b++;
}
}
return {h, b};
}
// Generate valid strings (digits 0-9, unique, length 5)
vector<string> generate_all_candidates() {
vector<string> s;
for (int i = 0; i <= 99999; ++i) {
string cur = to_string(i);
while (cur.length() < 5) cur = "0" + cur;
// Check uniqueness
int mask = 0;
bool ok = true;
for (char c : cur) {
int d = c - '0';
if ((mask >> d) & 1) {
ok = false;
break;
}
mask |= (1 << d);
}
if (ok) s.push_back(cur);
}
return s;
}
int main() {
// Fast I/O
cin.tie(NULL);
ios_base::sync_with_stdio(false);
auto candidates = generate_all_candidates();
int total_targets = 30;
int found_count = 0;
// Random engine
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// Loop until all 30 strings are found
while (found_count < total_targets) {
// --- 1. Select the Best Query ---
string query_str;
// Dynamic sampling strategy
// If candidates are few, check all to be precise.
// If many, sample to save time (though 5s is generous, O(N^2) is still heavy at 30k).
int cand_size = candidates.size();
vector<string> query_pool;
if (cand_size <= 2000) {
// Full search
query_pool = candidates;
} else {
// Random sampling
int sample_size = 300;
vector<int> indices(cand_size);
for(int i=0; i<cand_size; ++i) indices[i] = i;
// Partial shuffle or just pick random
// Since we need just 300, random pick is faster than full shuffle
for(int i=0; i<sample_size; ++i) {
query_pool.push_back(candidates[rng() % cand_size]);
}
// Ensure at least one valid candidate is in the pool
if (query_pool.empty()) query_pool.push_back(candidates[0]);
}
double best_score = 1e18;
string best_query = query_pool[0];
// Evaluate each potential query in the pool
for (const string& q : query_pool) {
// We map (h, b) to index: h*6 + b (max 5*6+5 = 35)
int counts[36] = {0};
// Simulate response against all current candidates
for (const string& c : candidates) {
Result r = calc_hb(c, q);
counts[r.h * 6 + r.b]++;
}
// Calculate "Collision Score" (Sum of Squares)
// Minimizing this maximizes entropy (spreads candidates evenly)
long long score = 0;
for (int k = 0; k < 36; ++k) {
if (counts[k] > 0) {
score += (long long)counts[k] * counts[k];
}
}
if (score < best_score) {
best_score = score;
best_query = q;
}
}
query_str = best_query;
// --- 2. Perform Query ---
cout << query_str << endl; // flush
// --- 3. Read Response ---
// Frequency map of received (H, B) pairs
int response_counts[36] = {0};
int current_fives = 0;
for (int i = 0; i < total_targets; ++i) {
int h, b;
cin >> h >> b;
if (h == 5 && b == 0) current_fives++;
response_counts[h * 6 + b]++;
}
// Check completion
if (current_fives == total_targets) {
return 0;
}
// --- 4. Process Found Strings ---
bool is_new_hit = (current_fives > found_count);
if (is_new_hit) {
// We found a new string!
// Since candidates are distinct and we query one string, we found exactly one.
found_count = current_fives;
// The query itself was the answer. Remove it from candidates.
// (We will rebuild candidates anyway, but logically it's gone)
}
// --- 5. Filter Candidates ---
// IMPORTANT: The response contains 'found_count' instances of (5,0)
// that correspond to the strings we have ALREADY found (including potentially the one just found).
// These provide NO information about the remaining candidates.
// We must subtract them to see the distribution of the unknown strings.
response_counts[5 * 6 + 0] -= found_count;
vector<string> next_candidates;
next_candidates.reserve(candidates.size());
for (const string& cand : candidates) {
// If the candidate is the one we just queried:
// - If it was a hit, it's now 'found', so don't add to next_candidates.
// - If it was a miss, it's not in S, so don't add.
// So in both cases, exclude the query string itself.
if (cand == query_str) continue;
// Calculate what (H, B) this candidate would return for the current query
Result r = calc_hb(cand, query_str);
int idx = r.h * 6 + r.b;
// Check consistency:
// Does the remaining response bag contain this (H, B)?
if (response_counts[idx] > 0) {
next_candidates.push_back(cand);
}
}
candidates = next_candidates;
}
return 0;
}