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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-14 19:42:58
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 625 ms / 5,000 ms
• コード長: 6,970 bytes
• コンパイル時間: 2,364 ms
• コンパイル使用メモリ: 206,080 KB
• 実行使用メモリ: 26,228 KB
• スコア: 9,991,211
• 平均クエリ数: 87.89
• 最終ジャッジ日時: 2025-12-25 01:33:38
• 合計ジャッジ時間: 61,622 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

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

ソースコード

// By Gemini 3 Pro

/**
 * 30 Parallel Mixed Hit & Blow Solver
 * Optimized using entropy-based filtering.
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <random>
#include <chrono>

using namespace std;

// Represents the response pair
struct Result {
    int h, b;
    bool operator<(const Result& other) const {
        if (h != other.h) return h < other.h;
        return b < other.b;
    }
    bool operator==(const Result& other) const {
        return h == other.h && b == other.b;
    }
    bool operator!=(const Result& other) const {
        return !(*this == other);
    }
};

// Calculate Hit and Blow between two strings
Result calc_hb(const string& secret, const string& query) {
    int h = 0;
    int b = 0;
    for (int i = 0; i < 5; ++i) {
        if (secret[i] == query[i]) {
            h++;
        }
    }
    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};
}

// Check if string has unique digits
bool has_unique_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;
}

// Generate all valid strings
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;
        if (has_unique_digits(cur)) {
            s.push_back(cur);
        }
    }
    return s;
}

int main() {
    // Fast I/O
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    // Initial candidates
    vector<string> candidates = generate_all_candidates();
    int found_count = 0;
    const int TOTAL_TARGETS = 30;

    // Random engine for sampling
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    while (found_count < TOTAL_TARGETS) {
        string query_str;

        // Strategy: Pick a query that maximizes entropy (splits candidates well).
        // Since O(N^2) is too slow for 30000 candidates every turn, we sample.
        if (candidates.empty()) {
             // Should not happen theoretically unless all found
            break;
        }

        // Sampling size for choosing the best query
        int sample_size = 30; 
        if (candidates.size() < 50) sample_size = candidates.size();

        double best_score = 1e18; // Minimize collision score (sum of squares)
        string best_query = candidates[0];

        // Pick random candidates to test as queries
        vector<string> query_samples;
        if (candidates.size() <= sample_size) {
            query_samples = candidates;
        } else {
            vector<int> indices(candidates.size());
            for(size_t i=0; i<candidates.size(); ++i) indices[i] = i;
            shuffle(indices.begin(), indices.end(), rng);
            for(int i=0; i<sample_size; ++i) query_samples.push_back(candidates[indices[i]]);
        }

        for (const string& q_cand : query_samples) {
            // Calculate distribution of results against all candidates
            // We use a flat array map for speed: index = h * 6 + b
            // h in 0..5, b in 0..5. Max index 35.
            int counts[36] = {0};
            
            for (const string& cand : candidates) {
                Result r = calc_hb(cand, q_cand);
                counts[r.h * 6 + r.b]++;
            }

            // Calculate score: sum of squares (collision probability)
            // Lower is better (more uniform distribution)
            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_cand;
            }
        }

        query_str = best_query;

        // Output Query
        cout << query_str << endl; // endl flushes

        // Read Response
        vector<Result> response;
        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.push_back({h, b});
        }

        // Check for termination
        if (current_fives == TOTAL_TARGETS) {
            return 0;
        }
        
        // Did we find a new string?
        bool is_hit = (current_fives > found_count);
        if (is_hit) {
            found_count = current_fives;
            // Remove the found string from candidates
            // (Since we selected query_str from candidates, we can just remove it)
            // Note: If we selected query_str from outside candidates, we'd need to be careful,
            // but the logic above picks from candidates.
            // Actually, we filter candidates below, so we just need to ensure 
            // the found string isn't considered "unknown" anymore.
        }

        // Build the "Active Response Bag" (excluding known (5,0)s)
        // Since we don't know exactly which old responses map to which pairs (except (5,0)),
        // we utilize the property: Valid candidates MUST produce a (H,B) that exists in the returned bag.
        
        // Count frequencies in response
        int response_counts[36] = {0};
        for (const auto& r : response) {
            response_counts[r.h * 6 + r.b]++;
        }
        
        // Decrement (5,0) count by the number of found strings
        // Because "Found" strings always return (5,0)
        response_counts[5 * 6 + 0] -= found_count;
        
        // If the query was a HIT just now, it accounts for one of the (5,0)s we just removed.
        // If the query was NOT a hit, it must produce a response present in the remaining bag.
        
        vector<string> next_candidates;
        next_candidates.reserve(candidates.size());

        for (const string& cand : candidates) {
            if (cand == query_str) {
                // If it was a hit, it's found (already handled by found_count logic implicitly for termination).
                // If it wasn't a hit, it's not the answer.
                // In either case, we don't need to keep the query string in our search space for *other* strings.
                continue; 
            }

            Result r = calc_hb(cand, query_str);
            int idx = r.h * 6 + r.b;

            // Filter: The result r must exist in the "Active Response Bag"
            // The active bag contains responses from the UNFOUND hidden strings.
            if (response_counts[idx] > 0) {
                next_candidates.push_back(cand);
            }
        }

        candidates = next_candidates;
    }

    return 0;
}