結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

// 高速化のため型を小さく
typedef uint8_t ResultCode;

struct Guess {
    uint8_t d[5]; // char/uint8_tで十分
    int mask;
};

// 全パターン保持用
vector<Guess> all_patterns;

// ヒット・ブロー判定
// インライン展開とビット演算で極限まで高速化
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++;
    // maskのANDをとってビット数を数える = 共通して含まれる数字の個数 (Hit + Blow)
    int common = __builtin_popcount(q.mask & t.mask);
    // return値: h * 6 + b (b = common - h)
    return (ResultCode)(h * 6 + (common - h));
}

int main() {
    // 入出力高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 乱数生成
    mt19937 rng(5489); // 固定シードで再現性を確保しつつ適度なランダム性

    // 1. 全パターン生成 (約30240通り)
    all_patterns.reserve(30240);
    for (int i = 0; i <= 99999; 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 = m;
            for(int j=0; j<5; j++) g.d[j] = digs[j];
            all_patterns.push_back(g);
        }
    }

    // 候補リスト（インデックスで管理）
    vector<int> candidates;
    candidates.reserve(all_patterns.size());
    for (int i = 0; i < (int)all_patterns.size(); i++) candidates.push_back(i);

    // 解決済みフラグ管理
    vector<bool> is_solved(all_patterns.size(), false);
    vector<int> solved_indices; // 既に特定した文字列のインデックス
    int solved_count = 0;

    // メインループ
    // 30個すべて見つけるまで
    while (solved_count < 30) {
        int best_guess_idx = -1;
        int cand_size = (int)candidates.size();

        // --- クエリ決定フェーズ ---

        // 戦略:
        // 1. 候補が極端に多い場合(>2000): 計算コストが高いのでランダムに選ぶ（それでも十分減る）
        // 2. それ以外: 候補の中から、もっとも「候補集合を均等に分割できる質問」を選ぶ
        //    ※ log計算を避けるため、Σ(count^2) [衝突数の二乗和] を最小化する戦略をとる
        
        if (cand_size > 2000) {
            // ランダムに選ぶ (candidatesの中から選ぶのが重要)
            best_guess_idx = candidates[rng() % cand_size];
        } else {
            long long min_score = -1; // スコアは小さいほうが良い(衝突が少ない)

            // 評価に使うサンプルの間引き
            // 候補が多いときは全探索すると遅いので、質問候補(Q)と評価対象(S)を間引く
            int check_limit_q = (cand_size > 500) ? 50 : cand_size; // 質問候補数
            int check_limit_s = (cand_size > 500) ? 200 : cand_size; // 比較対象数

            // ランダムに質問候補を選ぶためのインデックス配列作成
            vector<int> q_indices;
            if (cand_size <= check_limit_q) {
                q_indices = candidates;
            } else {
                q_indices.reserve(check_limit_q);
                for(int i=0; i<check_limit_q; i++) q_indices.push_back(candidates[rng() % cand_size]);
            }

            // 評価用サンプルを選ぶ
            vector<int> s_indices;
            if (cand_size <= check_limit_s) {
                s_indices = candidates;
            } else {
                s_indices.reserve(check_limit_s);
                for(int i=0; i<check_limit_s; i++) s_indices.push_back(candidates[rng() % cand_size]);
            }
            
            // 探索
            for (int q_idx : q_indices) {
                int counts[36] = {0};
                
                // サンプルに対してHB判定を行い分布をとる
                for (int s_idx : s_indices) {
                    counts[get_hb_code(all_patterns[q_idx], all_patterns[s_idx])]++;
                }

                // スコア計算: Σ (count^2)
                // これが小さいほど、分布がバラけている（＝良い質問）
                long long current_score = 0;
                for (int j = 0; j < 36; j++) {
                    if (counts[j] > 1) { // 0か1なら足す必要なし
                        current_score += (long long)counts[j] * counts[j];
                    }
                }

                if (min_score == -1 || current_score < min_score) {
                    min_score = current_score;
                    best_guess_idx = q_idx;
                }
            }
        }

        // 万が一決まらなかった場合のフェイルセーフ（通常ここには来ない）
        if (best_guess_idx == -1) best_guess_idx = candidates[0];


        // --- クエリ出力 ---
        const auto& best_guess = all_patterns[best_guess_idx];
        for (int i = 0; i < 5; i++) cout << (int)best_guess.d[i];
        cout << endl; // endlでフラッシュされる

        // --- レスポンス取得 ---
        // 頻度分布として受け取る
        int res_freq[36] = {0};
        int current_5h_count = 0;

        for (int i = 0; i < 30; i++) {
            int h, b;
            cin >> h >> b;
            if (h == -1) return 0; // エラー終了
            int code = h * 6 + b;
            res_freq[code]++;
            if (code == 30) current_5h_count++; // (5,0)はコード30
        }

        // --- 解決判定 ---
        // 今回のクエリ自体が正解だった場合（ジャッジ側の5Hの数が増えているか確認）
        // ただし、既に正解済みのものに対する (5,0) レスポンスも含まれるため差分を見る
        if (!is_solved[best_guess_idx]) {
            if (current_5h_count > (int)solved_indices.size()) {
                is_solved[best_guess_idx] = true;
                solved_indices.push_back(best_guess_idx);
            }
        }
        
        solved_count = current_5h_count;
        if (solved_count == 30) break; // 全問正解

        // --- 候補フィルタリング ---
        // まだ見つかっていないターゲットからの返答のみを抽出した分布を作る
        int unknown_res_freq[36];
        for(int j=0; j<36; j++) unknown_res_freq[j] = res_freq[j];
        
        // 既知の正解による (5,0) の分を差し引く
        unknown_res_freq[30] -= (int)solved_indices.size();

        // 次の候補リストを作成
        // swap技法を使って再確保コストを減らすことも可能だが、可読性重視で別vector作成
        vector<int> next_candidates;
        next_candidates.reserve(candidates.size());

        for (int c_idx : candidates) {
            // 既に解けたものは候補から外す
            if (is_solved[c_idx]) continue;

            // 自分が正解だと仮定したとき、今回の質問に対して返ってくるはずのHB
            ResultCode code = get_hb_code(best_guess, all_patterns[c_idx]);

            // そのHBが、未知のターゲットからの返答群に含まれているか？
            // 含まれていなければ、この候補はあり得ない
            if (unknown_res_freq[code] > 0) {
                next_candidates.push_back(c_idx);
            }
        }
        candidates = move(next_candidates);
    }

    return 0;
}
0