結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

// HB結果を1バイトで保持 (h*6 + b)
typedef uint8_t ResultCode;

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

// 高速なヒット・ブロー計算
// mask を用いて Blow を高速に判定
inline ResultCode get_hb_code(const Guess& q, const Guess& t) {
    int h = 0;
    if (q.d[0] == t.d[0]) h++;
    if (q.d[1] == t.d[1]) h++;
    if (q.d[2] == t.d[2]) h++;
    if (q.d[3] == t.d[3]) h++;
    if (q.d[4] == t.d[4]) h++;

    int common = __builtin_popcount(q.mask & t.mask);
    int b = common - h;
    return (ResultCode)(h * 6 + b);
}

// 候補全体
vector<Guess> all_patterns;

void precompute_patterns() {
    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 = m;
            g.id = all_patterns.size();
            for (int j = 0; j < 5; j++) g.d[j] = digs[j];
            all_patterns.push_back(g);
        }
    }
}

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

    precompute_patterns();
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    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_count = 0;

    // 対数テーブル
    double log_table[30241];
    for (int i = 0; i <= 30240; i++) log_table[i] = (i <= 1) ? 0 : log2(i);

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

        // 候補が極端に少ない場合は、直接候補を当てるフェーズへ
        if (candidates.size() <= (size_t)(30 - solved_count)) {
            for (int c : candidates) {
                if (!is_solved[c]) { best_guess_idx = c; break; }
            }
        } 
        // 初手: 情報量を最大化しやすい 01234
        else if (solved_count == 0 && candidates.size() == 30240) {
            for(int i=0; i<(int)all_patterns.size(); ++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 {
            // エントロピーによる探索
            double max_entropy = -1.0;
            int search_limit = (candidates.size() > 5000) ? 500 : 1500;
            int sample_size = min((int)candidates.size(), 800);
            
            vector<int> samples;
            if (candidates.size() <= (size_t)sample_size) samples = candidates;
            else {
                // シャッフルして先頭を取ることで重複を防ぐ
                samples.reserve(sample_size);
                for(int i=0; i<sample_size; ++i) samples.push_back(candidates[rng() % candidates.size()]);
            }

            for (int i = 0; i < search_limit; i++) {
                // 候補から選ぶか全体から選ぶか (候補から選ぶ方が「当たり」を引く確率があるため優先)
                int q_idx = (i < search_limit * 0.8) ? 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 entropy = 0;
                for (int j = 0; j < 36; j++) {
                    if (counts[j] > 0) entropy -= (double)counts[j] * log_table[counts[j]];
                }

                // 候補内から選ぶ場合にボーナス（直接正解を見つける可能性）
                if (q_idx < (int)all_patterns.size() && !is_solved[q_idx]) {
                    entropy += 0.0001; 
                }

                if (entropy > max_entropy) {
                    max_entropy = entropy;
                    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;

        // --- 返答取得 ---
        array<int, 36> res_freq = {0};
        bool found_now = false;
        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0;
            if (h == -1) return 0;
            res_freq[h * 6 + b]++;
        }

        // すべて解決したかチェック
        if (res_freq[30] == 30) break;

        // 今回の推測が「新しく」正解したか確認
        if (res_freq[30] > solved_count && !is_solved[best_guess_idx]) {
            is_solved[best_guess_idx] = true;
        }
        solved_count = res_freq[30];

        // --- 候補の絞り込み (重要) ---
        // ターゲットが30個あるため、ある候補cがターゲットのいずれかであるためには、
        // get_hb_code(guess, c) の結果が、ジャッジが返した30個のリストの中に存在しなければならない。
        vector<int> next_candidates;
        next_candidates.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) {
                // (5,0)は解決済みとして除外済み、それ以外のコードが返答に含まれていれば残す
                if (code != 30) next_candidates.push_back(c_idx);
            }
        }
        candidates = move(next_candidates);
    }

    return 0;
}
0