結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 ロロット
|
| 提出日時 | 2025-12-25 00:56:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 254 ms / 5,000 ms |
| コード長 | 7,326 bytes |
| 記録 | |
| コンパイル時間 | 2,732 ms |
| コンパイル使用メモリ | 161,212 KB |
| 実行使用メモリ | 26,344 KB |
| スコア | 9,995,214 |
| 平均クエリ数 | 47.86 |
| 最終ジャッジ日時 | 2025-12-25 01:03:52 |
| 合計ジャッジ時間 | 31,100 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
// Solved by Gemini3.0
// 確率での重み付け
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;
struct Candidate {
string s;
double p;
};
// Hit & Blow Calculation
pair<int, int> get_hit_blow(const string& s, const string& q) {
int h = 0;
int b = 0;
for (int i = 0; i < 5; ++i) {
if (s[i] == q[i]) h++;
}
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (i == j) continue;
if (s[i] == q[j]) b++;
}
}
return {h, b};
}
bool has_distinct_digits(const string& s) {
int mask = 0;
for (char c : s) {
int d = c - '0';
if ((mask >> d) & 1) return false;
mask |= (1 << d);
}
return true;
}
int main() {
auto start_time = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
vector<Candidate> candidates;
candidates.reserve(30240);
for (int i = 0; i < 100000; ++i) {
string s = to_string(i);
while (s.length() < 5) s = "0" + s;
if (has_distinct_digits(s)) {
candidates.push_back({s, 1.0});
}
}
static mt19937 rng(12345);
shuffle(candidates.begin(), candidates.end(), rng);
set<string> found_strings;
while (found_strings.size() < 30) {
sort(candidates.begin(), candidates.end(), [](const Candidate& a, const Candidate& b) { return a.p > b.p; });
if (candidates.empty()) break;
// --- Selection Strategy ---
string best_q = candidates[0].s;
// Check if we need to run heuristic
// If the top candidate is significantly better than the second, just take it.
// This avoids "over-thinking" and missing a likely hit.
bool skip_heuristic = false;
if (candidates.size() > 1) {
// Ratio of top probability to second top
if (candidates[0].p > 1.6 * candidates[1].p) {
skip_heuristic = true;
}
} else {
skip_heuristic = true;
}
if (!skip_heuristic) {
// Time Budget Calculation
auto now = chrono::high_resolution_clock::now();
double elapsed_sec = chrono::duration<double>(now - start_time).count();
double remaining_time = 4.90 - elapsed_sec;
int estimated_remaining_queries = max(1, (int)((30 - found_strings.size()) * 1.5) + 5);
double time_budget = remaining_time / estimated_remaining_queries;
if (time_budget < 0.005) time_budget = 0.0;
if (time_budget > 0.001) {
// Identify top candidates group
double max_p = candidates[0].p;
vector<string> top_candidates;
for (const auto& c : candidates) {
// Tighter threshold: only consider candidates extremely close to max_p
if (c.p >= max_p * 0.98) {
top_candidates.push_back(c.s);
} else {
break;
}
if (top_candidates.size() >= 100) break;
}
if (top_candidates.size() > 1) {
double min_expected_size = 1e18;
int sample_size = min((int)candidates.size(), 2000);
vector<string> sample;
sample.reserve(sample_size);
if (sample_size == (int)candidates.size()) {
for (const auto& c : candidates) sample.push_back(c.s);
} else {
for (int i = 0; i < sample_size; ++i) {
int idx = uniform_int_distribution<int>(0, candidates.size() - 1)(rng);
sample.push_back(candidates[idx].s);
}
}
int K_missing = 30 - found_strings.size();
auto loop_start_time = chrono::high_resolution_clock::now();
for (const string& q_cand : top_candidates) {
auto current_time = chrono::high_resolution_clock::now();
double current_elapsed = chrono::duration<double>(current_time - loop_start_time).count();
if (current_elapsed > time_budget) break;
map<pair<int, int>, int> buckets;
for (const string& s : sample) {
buckets[get_hit_blow(s, q_cand)]++;
}
double expected_size = 0;
for (auto const& [hb, count] : buckets) {
double prob_hit_bucket = 1.0 - pow(1.0 - (double)count / sample_size, K_missing);
expected_size += count * prob_hit_bucket;
}
if (expected_size < min_expected_size) {
min_expected_size = expected_size;
best_q = q_cand;
}
}
}
}
}
string q = best_q;
cout << q << endl;
vector<pair<int, int>> response(30);
int cnt_5_0 = 0;
map<pair<int, int>, int> response_counts;
for (int i = 0; i < 30; ++i) {
if (!(cin >> response[i].first >> response[i].second)) return 0;
if (response[i] == make_pair(5, 0)) cnt_5_0++;
response_counts[response[i]]++;
}
bool q_is_newly_found = false;
if (cnt_5_0 > (int)found_strings.size()) {
found_strings.insert(q);
q_is_newly_found = true;
}
if (found_strings.size() == 30) break;
// Update Weights
int previously_found_count = found_strings.size() - (q_is_newly_found ? 1 : 0);
if (response_counts.count({5, 0})) {
response_counts[{5, 0}] -= previously_found_count;
if (response_counts[{5, 0}] <= 0) response_counts.erase({5, 0});
}
map<pair<int, int>, double> weight_sums;
for (const auto& c : candidates) {
if (found_strings.count(c.s) && c.s != q) continue;
weight_sums[get_hit_blow(c.s, q)] += c.p;
}
vector<Candidate> next_candidates;
next_candidates.reserve(candidates.size());
for (auto& c : candidates) {
if (found_strings.count(c.s) && c.s != q) continue;
pair<int, int> hb = get_hit_blow(c.s, q);
double bucket_count = response_counts.count(hb) ? response_counts[hb] : 0;
if (bucket_count > 0 && weight_sums[hb] > 0) {
c.p *= (bucket_count / weight_sums[hb]);
if (c.p > 1e-15 && !(c.s == q && q_is_newly_found)) {
next_candidates.push_back(c);
}
}
}
candidates = next_candidates;
double sum_p = 0;
for (const auto& c : candidates) sum_p += c.p;
if (sum_p > 0) {
double scale = (30 - found_strings.size()) / sum_p;
for (auto& c : candidates) c.p *= scale;
}
}
return 0;
}