結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <random>
#include <chrono>
#include <cmath>

using namespace std;

// 文字列とそのビットマスク表現（高速化のため）
struct Candidate {
    string s;
    int mask; // 各数字が使われているかのビットマスク

    Candidate(string str) : s(str) {
        mask = 0;
        for (char c : str) {
            mask |= (1 << (c - '0'));
        }
    }
};

// HitとBlowを計算する関数
// __builtin_popcount はGCC/Clang拡張でビットカウントを高速に行う
pair<int, int> calc_hb(const Candidate& a, const Candidate& b) {
    int hits = 0;
    for (int i = 0; i < 5; ++i) {
        if (a.s[i] == b.s[i]) hits++;
    }
    // Blow = (共通する数字の数) - Hit
    int common = __builtin_popcount(a.mask & b.mask);
    return {hits, common - hits};
}

int main() {
    // 高速化
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 1. 全候補の生成
    // 資料における「油田の配置全体の集合 X」 に相当
    // 30,240通りしかないので全列挙可能 
    vector<Candidate> all_candidates;
    auto generate_all = [&]() {
        vector<Candidate> res;
        vector<int> used(10, 0);
        auto dfs = [&](auto&& self, string current) -> void {
            if (current.size() == 5) {
                res.emplace_back(current);
                return;
            }
            for (int i = 0; i <= 9; ++i) {
                if (!used[i]) {
                    used[i] = 1;
                    self(self, current + to_string(i));
                    used[i] = 0;
                }
            }
        };
        dfs(dfs, "");
        return res;
    };
    all_candidates = generate_all();

    // 現在の有効な候補集合（インデックスで管理）
    // 初期状態では、真の配置 x である確率は一様 [cite: 154]
    vector<int> active_candidates(all_candidates.size());
    iota(active_candidates.begin(), active_candidates.end(), 0);
    
    // 既に特定された正解のインデックス集合
    set<int> confirmed;
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    // 30個すべて見つけるまでループ
    while (true) {
        int remaining_targets = 30 - confirmed.size();
        
        // 残りの候補数が、未発見の正解数と一致したら、それらが正解
        if (active_candidates.size() == remaining_targets) {
            for (int idx : active_candidates) {
                cout << all_candidates[idx].s << endl;
                // ダミー入力読み飛ばし
                string d; for(int k=0; k<30; ++k) cin >> d >> d; 
            }
            return 0;
        }

        // 2. 相互情報量に基づく質問の選択 [cite: 224, 235]
        // 全候補を評価するのは重いため、ランダムにサンプリングして評価 [cite: 244]
        int best_query_idx = -1;
        
        if (active_candidates.size() <= remaining_targets) {
            best_query_idx = active_candidates[0];
        } else {
            // 評価する候補数
            int sample_size = min((int)active_candidates.size(), 50);
            vector<int> probes;
            sample(active_candidates.begin(), active_candidates.end(), back_inserter(probes), sample_size, rng);
            
            double max_entropy = -1.0;

            for (int q_idx : probes) {
                // シミュレーション: この質問qをしたとき、候補がどのような分布になるか
                // 資料の「占い結果の確率分布」[cite: 218] を計算
                int counts[6][6] = {0};
                for (int c_idx : active_candidates) {
                    pair<int, int> hb = calc_hb(all_candidates[c_idx], all_candidates[q_idx]);
                    counts[hb.first][hb.second]++;
                }
                
                // エントロピー H(Y) の計算 
                // バラつきが大きいほどエントロピーは高くなる
                double entropy = 0;
                double total = active_candidates.size();
                for(int h=0; h<6; ++h) {
                    for(int b=0; b<6; ++b) {
                        if (counts[h][b] > 0) {
                            double p = counts[h][b] / total;
                            entropy -= p * log2(p);
                        }
                    }
                }

                if (entropy > max_entropy) {
                    max_entropy = entropy;
                    best_query_idx = q_idx;
                }
            }
        }

        // 質問出力
        cout << all_candidates[best_query_idx].s << endl;

        // 3. 結果の受け取りと候補の絞り込み（事後確率の更新）[cite: 178]
        // 実際の結果Rを受け取る
        int response_counts[6][6] = {0};
        bool all_correct = true;
        for (int i = 0; i < 30; ++i) {
            int h, b;
            cin >> h >> b;
            response_counts[h][b]++;
            if (h != 5 || b != 0) all_correct = false;
        }

        if (all_correct) return 0; // 全て(5,0)なら終了

        // ルール: 既知の正解に対しては (5, 0) が返ってくる
        // これを除外して、未知の正解に対する分布を得る
        int expected_5_0 = confirmed.size();
        int actual_5_0 = response_counts[5][0];
        
        if (actual_5_0 > expected_5_0) {
            // 新しい正解が見つかった！
            confirmed.insert(best_query_idx);
            response_counts[5][0] -= actual_5_0; 
        } else {
            response_counts[5][0] -= expected_5_0;
        }

        // 尤度計算とフィルタリング [cite: 175, 250]
        // 返ってきた分布 `response_counts` と矛盾する候補を削除する
        vector<int> next_candidates;
        next_candidates.reserve(active_candidates.size());

        for (int c_idx : active_candidates) {
            if (confirmed.count(c_idx)) continue;

            // 候補 c が正解だと仮定したときの Hit/Blow
            pair<int, int> hb = calc_hb(all_candidates[c_idx], all_candidates[best_query_idx]);
            
            // その結果が、実際の返答リストに含まれていれば、尤度 > 0
            if (response_counts[hb.first][hb.second] > 0) {
                next_candidates.push_back(c_idx);
            }
        }

        active_candidates = next_candidates;
    }

    return 0;
}
0