#1141630 (C++23) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: ロロット
• 提出日時: 2025-12-25 00:39:29
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 4,636 ms / 5,000 ms
• コード長: 5,689 bytes
• コンパイル時間: 1,826 ms
• コンパイル使用メモリ: 158,264 KB
• 実行使用メモリ: 26,228 KB
• スコア: 9,991,580
• 平均クエリ数: 84.20
• 最終ジャッジ日時: 2025-12-25 00:50:10
• 合計ジャッジ時間: 371,435 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 100

ソースコード

// Solved by Gemini3.0
// 候補を確率の高いものを優先してもらいました。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <random>

using namespace std;

// Function to calculate Hit and Blow
pair<int, int> get_hit_blow(const string& s, const string& q) {
    int h = 0;
    int b = 0;
    // s and q are guaranteed to be distinct digit strings of length 5
    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;
}

string select_best_query(const vector<string>& candidates, int K) {
    if (candidates.empty()) return "";
    if (candidates.size() == 1) return candidates[0];

    // Random sample size
    int N = candidates.size();
    int sample_size = min(N, 200); 
    // Heuristic: smaller sample size for speed, 60 is usually enough to find a good one.
    
    vector<string> queries_to_test;
    queries_to_test.reserve(sample_size);
    
    if (sample_size == N) {
        queries_to_test = candidates;
    } else {
        // Random sampling
        // Use static generator to avoid re-seeding
        static mt19937 rng(12345);
        
        // We can just pick random indices
        set<int> picked_indices;
        while (picked_indices.size() < sample_size) {
            picked_indices.insert(uniform_int_distribution<int>(0, N - 1)(rng));
        }
        for (int idx : picked_indices) {
            queries_to_test.push_back(candidates[idx]);
        }
    }
    
    string best_q = queries_to_test[0];
    double min_score = 1e18; // We want to minimize expected remaining candidates
    
    // Debug: Check score of candidates[0] specifically
    double first_cand_score = -1.0;
    string first_cand = candidates[0];

    for (const string& q : queries_to_test) {
        map<pair<int, int>, int> bucket_counts;
        for (const string& c : candidates) {
            bucket_counts[get_hit_blow(c, q)]++;
        }
        
        double current_score = 0;
        
        for (auto const& [hb, count] : bucket_counts) {
            double prob_hit = 1.0 - pow(1.0 - (double)count / N, K);
            current_score += count * prob_hit;
        }
        
        if (q == first_cand) {
            first_cand_score = current_score;
        }
        
        if (current_score < min_score) {
            min_score = current_score;
            best_q = q;
        }
    }
    
    // If candidates[0] was not in sample, calculate it manually for comparison
    if (first_cand_score < 0) {
        map<pair<int, int>, int> bucket_counts;
        for (const string& c : candidates) {
            bucket_counts[get_hit_blow(c, first_cand)]++;
        }
        double current_score = 0;
        for (auto const& [hb, count] : bucket_counts) {
            double prob_hit = 1.0 - pow(1.0 - (double)count / N, K);
            current_score += count * prob_hit;
        }
        first_cand_score = current_score;
    }

    cerr << "Best: " << best_q << " (" << min_score << ") vs First: " << first_cand << " (" << first_cand_score << ") N=" << N << endl;
    
    return best_q;
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    
    vector<string> 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);
        }
    }

    set<string> found_strings;
    // We need to find 30 strings.
    
    while (found_strings.size() < 30) {
        int K = 30 - found_strings.size();
        
        string q = select_best_query(candidates, K);
        
        if (q.empty()) break; // Should not happen
        
        // Output query
        cout << q << endl;
        
        // Read response
        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) {
            cin >> response[i].first >> response[i].second;
            if (response[i] == make_pair(5, 0)) {
                cnt_5_0++;
            }
            response_counts[response[i]]++;
        }
        
        bool q_is_found = false;
        if (cnt_5_0 > (int)found_strings.size()) {
            found_strings.insert(q);
            q_is_found = true;
        }
        
        if (found_strings.size() == 30) {
            break;
        }
        
        if (response_counts.count({5, 0})) {
             response_counts[{5, 0}] -= cnt_5_0;
             if (response_counts[{5, 0}] <= 0) {
                 response_counts.erase({5, 0});
             }
        }
        
        // Filter candidates
        vector<string> next_candidates;
        next_candidates.reserve(candidates.size());
        
        for (const string& c : candidates) {
            if (found_strings.count(c)) continue;
            if (c == q) continue; 
            
            pair<int, int> hb = get_hit_blow(c, q);
            
            if (response_counts.count(hb)) {
                next_candidates.push_back(c);
            }
        }
        
        candidates = next_candidates;
    }
    
    return 0;
}