結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー LNG
提出日時 2025-12-25 13:33:09
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 932 ms / 5,000 ms
コード長 6,578 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,592 ms
コンパイル使用メモリ 209,940 KB
実行使用メモリ 26,072 KB
スコア 9,985,153
平均クエリ数 148.47
最終ジャッジ日時 2025-12-25 13:34:43
合計ジャッジ時間 88,578 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//ビームサーチを実装させた

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

using namespace std;

typedef uint8_t ResultCode;

struct Guess {
    int8_t d[5];
    int16_t mask;
};

vector<Guess> all_patterns;
double log_table[30241];

// HB計算 (ビット演算最適化)
inline ResultCode get_hb_code(const Guess& q, const Guess& t) {
    int h = (q.d[0] == t.d[0]) + (q.d[1] == t.d[1]) + (q.d[2] == t.d[2]) + (q.d[3] == t.d[3]) + (q.d[4] == t.d[4]);
    int b = __builtin_popcount(q.mask & t.mask) - h;
    return (ResultCode)(h * 6 + b);
}

void precompute() {
    for (int i = 0; i <= 99999; i++) {
        int tmp = i, m = 0;
        int8_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 = (int16_t)m;
            for (int j = 0; j < 5; j++) g.d[j] = digs[j];
            all_patterns.push_back(g);
        }
    }
    for (int i = 0; i <= 30240; i++) log_table[i] = (i <= 1) ? 0 : log2(i);
}

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

    precompute();
    int N = all_patterns.size();
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    vector<int> candidates;
    for (int i = 0; i < N; i++) candidates.push_back(i);

    vector<bool> is_solved(N, false);
    int solved_total = 0;

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

        if (candidates.size() <= (size_t)(30 - solved_total)) {
            for (int c : candidates) if (!is_solved[c]) { best_guess_idx = c; break; }
        } else if (solved_total == 0 && candidates.size() == (size_t)N) {
            // 初手固定: 01234
            best_guess_idx = 1234; // all_patterns内の01234のインデックス(要計算だが01234は優秀)
            for(int i=0; i<N; ++i) if(all_patterns[i].d[0]==0 && all_patterns[i].d[1]==1 && all_patterns[i].d[2]==2 && all_patterns[i].d[3]==3 && all_patterns[i].d[4]==4) { best_guess_idx = i; break; }
        } else {
            // --- 適応型ビームサーチ ---
            int sample_size = (candidates.size() > 1200) ? 800 : (int)candidates.size();
            vector<int> samples;
            if (candidates.size() <= (size_t)sample_size) {
                samples = candidates;
            } else {
                // 重複なしサンプリング
                vector<int> temp_c = candidates;
                shuffle(temp_c.begin(), temp_c.end(), rng);
                samples.assign(temp_c.begin(), temp_c.begin() + sample_size);
            }

            struct BeamNode { double score; int idx; };
            vector<BeamNode> beam;
            
            // 探索範囲: 候補が減るほど深く探す
            int search_limit = (candidates.size() > 5000) ? 800 : 3000;
            
            for (int i = 0; i < search_limit; i++) {
                // 80%は候補内から、20%は全域から探索
                int q_idx = (i < search_limit * 0.8) ? candidates[rng() % candidates.size()] : rng() % N;
                if (is_solved[q_idx]) continue;

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

                double entropy = 0;
                for (int j = 0; j < 36; j++) {
                    if (counts[j] > 0) entropy -= (double)counts[j] * log_table[counts[j]];
                }

                // 微調整: エントロピー + Minimax補正 + 候補ボーナス
                double score = entropy;
                score -= log_table[max_bucket] * 0.05; // わずかにMinimaxを混ぜる
                
                // クエリが候補そのものである場合、直接当たる期待値を加算
                if (find(candidates.begin(), candidates.end(), q_idx) != candidates.end()) {
                    score += 0.01; 
                }

                beam.push_back({score, q_idx});
            }
            sort(beam.begin(), beam.end(), [](const BeamNode& a, const BeamNode& b){ return a.score > b.score; });

            // 2. Look-ahead
            int beam_width = (candidates.size() < 200) ? 30 : 10;
            double best_final_score = -1e18;

            for (int i = 0; i < min((int)beam.size(), beam_width); i++) {
                int q_idx = beam[i].idx;
                int counts[36] = {0};
                for (int s_idx : samples) counts[get_hb_code(all_patterns[q_idx], all_patterns[s_idx])]++;

                double future_e = 0;
                for (int j = 0; j < 36; j++) {
                    if (counts[j] > 1) future_e -= (double)counts[j] * log_table[counts[j]];
                }
                
                // 重み付け: 終盤ほど先読みを信じる
                double weight = (candidates.size() < 100) ? 0.4 : 0.2;
                double total_score = beam[i].score + (future_e * weight);
                
                if (total_score > best_final_score) {
                    best_final_score = total_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;

        // 返答処理
        int res_freq[36] = {0};
        for (int i = 0; i < 30; i++) {
            int h, b; cin >> h >> b;
            if (h == -1) return 0;
            res_freq[h * 6 + b]++;
        }

        if (res_freq[30] == 30) break;

        if (res_freq[30] > solved_total && !is_solved[best_guess_idx]) {
            is_solved[best_guess_idx] = true;
        }
        solved_total = res_freq[30];

        // 候補絞り込み
        vector<int> next_c;
        next_c.reserve(candidates.size());
        for (int c_idx : candidates) {
            if (is_solved[c_idx]) continue;
            ResultCode code = get_hb_code(all_patterns[best_guess_idx], all_patterns[c_idx]);
            if (res_freq[code] > 0 && code != 30) next_c.push_back(c_idx);
        }
        candidates = move(next_c);
    }
    return 0;
}
0