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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: LNG
• 提出日時: 2025-12-25 15:05:01
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 316 ms / 5,000 ms
• コード長: 6,459 bytes
• コンパイル時間: 2,271 ms
• コンパイル使用メモリ: 198,284 KB
• 実行使用メモリ: 25,972 KB
• スコア: 9,988,073
• 平均クエリ数: 119.27
• 最終ジャッジ日時: 2025-12-25 15:05:38
• 合計ジャッジ時間: 34,476 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>

using namespace std;

// 判定結果を1バイトで保持 (H*6 + B)
typedef uint8_t ResultCode;

struct alignas(16) Guess {
    uint32_t packed; // 4bit * 5 digits
    uint16_t mask;   // bitmask for digits 0-9
    uint8_t d[5];
    int id;
};

// 高速なHit/Blow判定
inline ResultCode get_hb_code(const Guess& q, const Guess& t) {
    uint32_t diff = q.packed ^ t.packed;
    int h = ((diff & 0xF0000u) == 0) +
            ((diff & 0x0F000u) == 0) +
            ((diff & 0x00F00u) == 0) +
            ((diff & 0x000F0u) == 0) +
            ((diff & 0x0000Fu) == 0);
    // 共通の数字の数 = __builtin_popcount(mask_a & mask_b)
    // Blow = 共通の数 - Hit
    int common = __builtin_popcount(q.mask & t.mask);
    return (ResultCode)(h * 6 + (common - h));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    mt19937 rng(42); // 再現性のための固定シード、または時間シード

    // 全パターンの生成 (30240通り)
    vector<Guess> all_patterns;
    all_patterns.reserve(30240);
    int start_guess_idx = -1;

    for (int i = 0; i <= 98765; i++) {
        int tmp = i, m = 0;
        uint8_t digs[5];
        bool ok = true;
        for (int j = 4; j >= 0; j--) {
            digs[j] = tmp % 10;
            if (m & (1 << digs[j])) { ok = false; break; }
            m |= (1 << digs[j]);
            tmp /= 10;
        }
        if (ok) {
            Guess g;
            g.mask = (uint16_t)m;
            g.id = (int)all_patterns.size();
            g.packed = 0;
            for (int j = 0; j < 5; j++) {
                g.d[j] = digs[j];
                g.packed = (g.packed << 4) | digs[j];
            }
            if (i == 1234) start_guess_idx = g.id; // "01234"
            all_patterns.push_back(g);
        }
    }

    vector<int> candidates;
    for (int i = 0; i < (int)all_patterns.size(); i++) candidates.push_back(i);
    
    vector<bool> is_solved(all_patterns.size(), false);
    int solved_total = 0;

    // 評価関数用のテーブル (x log x)
    static double score_table[30241];
    for (int i = 0; i <= 30240; i++) {
        score_table[i] = (i <= 1) ? 0 : (double)i * log2(i);
    }

    while (solved_total < 30) {
        int best_guess_idx = -1;

        if (solved_total == 0 && (int)candidates.size() == 30240) {
            best_guess_idx = start_guess_idx;
        } else if ((int)candidates.size() <= (30 - solved_total)) {
            // 残りの候補が正解数と一致すれば、順に答えるだけ
            for (int c : candidates) {
                if (!is_solved[c]) {
                    best_guess_idx = c;
                    break;
                }
            }
        } else {
            // 情報利得（エントロピー）が最大の推測を探す
            double min_score = 1e18;
            
            // 探索範囲の適応的決定
            int num_search = (candidates.size() > 5000) ? 400 : 1000;
            int sample_size = min((int)candidates.size(), 800);
            
            vector<int> samples;
            if ((int)candidates.size() <= sample_size) {
                samples = candidates;
            } else {
                for (int i = 0; i < sample_size; i++) 
                    samples.push_back(candidates[rng() % candidates.size()]);
            }

            for (int i = 0; i < num_search; i++) {
                // 候補から選ぶ確率を高める (正解を直接引く確率を上げる)
                int q_idx = (rng() % 100 < 70) ? candidates[rng() % candidates.size()] : rng() % all_patterns.size();
                if (is_solved[q_idx]) continue;

                int counts[36] = {0};
                for (int s_idx : samples) {
                    counts[get_hb_code(all_patterns[q_idx], all_patterns[s_idx])]++;
                }

                double score = 0;
                for (int j = 0; j < 36; j++) score += score_table[counts[j]];
                
                // 候補内の場合は、正解である可能性を考慮して微小なボーナス
                if (find(candidates.begin(), candidates.end(), q_idx) != candidates.end()) {
                    score -= 0.1; 
                }

                if (score < min_score) {
                    min_score = score;
                    best_guess_idx = q_idx;
                }
            }
        }

        if (best_guess_idx == -1) best_guess_idx = candidates[0];

        // --- 出力 ---
        for (int i = 0; i < 5; i++) cout << (int)all_patterns[best_guess_idx].d[i];
        cout << endl; // endlは内部でflushを呼び出す

        // --- 受信 ---
        int current_res_freq[36] = {0};
        bool found_any_new = false;
        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0;
            if (h == -1) return 0;
            current_res_freq[h * 6 + b]++;
        }

        // ヒット判定 (H=5, B=0 は code 30)
        solved_total = current_res_freq[30];
        if (solved_total == 30) break;

        // すでに発見済みの文字列を管理
        if (current_res_freq[30] > 0 && !is_solved[best_guess_idx]) {
            // ※厳密には「以前の推測」も含めて判定が必要だが、
            // 簡略化のため、今回の推測が正解の1つだったかを判定
            // (ジャッジ仕様により Si = q なら (5,0) になるため)
            // このコードでは「今回の推測が候補リストから消える」ことで管理
            is_solved[best_guess_idx] = true;
        }

        // --- フィルタリング ---
        // 候補 S が正解の1つであるためには、get_hb_code(best_guess, S) の結果が
        // ジャッジが返したレスポンス一覧の中に存在しなければならない。
        vector<int> next_candidates;
        for (int c_idx : candidates) {
            // 推測そのものは候補から外す（正解済みとして扱う）
            if (c_idx == best_guess_idx) continue;
            
            ResultCode code = get_hb_code(all_patterns[best_guess_idx], all_patterns[c_idx]);
            if (current_res_freq[code] > 0) {
                next_candidates.push_back(c_idx);
            }
        }
        candidates = move(next_candidates);
    }

    return 0;
}