結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー LNG
提出日時 2025-12-25 15:09:53
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 261 ms / 5,000 ms
コード長 6,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,065 ms
コンパイル使用メモリ 204,392 KB
実行使用メモリ 26,228 KB
スコア 9,987,810
平均クエリ数 121.90
最終ジャッジ日時 2025-12-25 15:10:26
合計ジャッジ時間 30,591 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 alignas(16) Guess {
    uint32_t packed;
    uint16_t mask;
    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);
    int common = __builtin_popcount(q.mask & t.mask);
    return (ResultCode)(h * 6 + (common - h));
}

// 過去の質問とジャッジの返答を記録する構造体
struct QueryHistory {
    int guess_idx;
    int freq[36];
};

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

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

    // 1. 全パターン生成
    vector<Guess> all_patterns;
    all_patterns.reserve(30240);
    int first_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) first_guess_idx = g.id;
            all_patterns.push_back(g);
        }
    }

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

    vector<QueryHistory> history;
    vector<bool> has_been_guessed(30240, false);
    int solved_count = 0;

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

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

        // 次の推測の選択
        if (solved_count == 0 && history.empty()) {
            best_guess_idx = first_guess_idx;
        } else if (candidates.size() <= (size_t)(30 - solved_count)) {
            // 残りの候補を直接当てるフェーズ
            for (int c : candidates) {
                if (!has_been_guessed[c]) {
                    best_guess_idx = c;
                    break;
                }
            }
        } else {
            // 情報利得最大化 (Entropy法)
            double min_score = 1e18;
            
            // 候補が多い時はサンプリング、少ない時は全探索に近い探索を行う
            int num_trials = (candidates.size() > 2000) ? 500 : 1200;
            int sample_size = min((int)candidates.size(), 600);
            
            vector<int> samples;
            if (candidates.size() <= (size_t)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_trials; i++) {
                // 候補内から選ぶのを優先(80%)
                int q_idx = (rng() % 100 < 80) ? candidates[rng() % candidates.size()] : rng() % 30240;
                if (has_been_guessed[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 (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;
        has_been_guessed[best_guess_idx] = true;

        // 結果受信
        QueryHistory cur_h;
        cur_h.guess_idx = best_guess_idx;
        for (int i = 0; i < 36; i++) cur_h.freq[i] = 0;

        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0;
            if (h == -1) return 0;
            cur_h.freq[h * 6 + b]++;
        }
        
        solved_count = cur_h.freq[30]; // (5,0)の数
        if (solved_count == 30) break;
        history.push_back(cur_h);

        // 2. 厳密なフィルタリング
        // 候補 P が有効であるためには、「過去の全ての質問 q に対して、get_hb(q, P) の結果が
        // 当時のジャッジの返答リストに含まれている」必要がある。
        vector<int> next_candidates;
        for (int c_idx : candidates) {
            // すでに質問して(5,0)になったものは候補から外す
            if (has_been_guessed[c_idx]) {
                // ただし、まだ(5,0)リストに現れていない可能性（＝まだ正解扱いされていない）
                // を考慮し、(5,0)の累積数と一致するまでは保持する考え方もあるが、
                // 基本的に自分が投げた手は candidate から外して良い。
                continue;
            }

            bool possible = true;
            for (const auto& hist : history) {
                ResultCode code = get_hb_code(all_patterns[hist.guess_idx], all_patterns[c_idx]);
                if (hist.freq[code] == 0) {
                    possible = false;
                    break;
                }
            }
            if (possible) {
                next_candidates.push_back(c_idx);
            }
        }
        candidates = move(next_candidates);
    }

    return 0;
}
0