#1140523 (C++23) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-15 23:51:33
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 150 ms / 5,000 ms
• コード長: 10,094 bytes
• コンパイル時間: 3,663 ms
• コンパイル使用メモリ: 305,056 KB
• 実行使用メモリ: 26,228 KB
• スコア: 9,995,748
• 平均クエリ数: 42.52
• 最終ジャッジ日時: 2025-12-25 01:51:17
• 合計ジャッジ時間: 19,901 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;

/*
  30個並列ごちゃ混ぜ Hit&Blow
  - 候補全30240を列挙
  - 各質問の返答（(H,B)ヒストグラム）を制約として保持
  - IPF(Iterative Proportional Fitting)で候補の重みwを更新し、
    wが最大の候補を質問する（当たりやすいものから潰す）
  - 5秒制限対策：IPF反復回数/使用する過去質問数を調整、時間が迫れば軽量化
*/

static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int N = 30240;
static constexpr int CODES = 36; // code = hit*6 + blow (0..35)

// ===== 調整パラメータ =====
static constexpr double TIME_LIMIT_SEC = 4.85; // 5sに対して少し余裕
static constexpr int IPF_ITERS_BASE = 10;      // IPF反復回数（増やすほど重いが当たりやすくなることが多い）
static constexpr int IPF_USE_LAST = 16;        // IPFに使う過去質問数（末尾K個）
static constexpr bool USE_FIXED_PROBES = true; // 初期探索を固定するか
// ==========================

struct Cand {
    array<uint8_t, L> d;
    uint16_t mask; // 10-bit
};

struct QueryInfo {
    int q_idx;
    array<int, CODES> rem;        // (5,0)以外の個数（未発見分）
    vector<uint8_t> code_to;      // size N: code_to[i] = score(q, cand[i]) as code
};

static inline int encode_code(int hit, int blow) { return hit * 6 + blow; }

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);

    // 時間計測
    const auto t_start = chrono::steady_clock::now();
    auto elapsed_sec = [&]() -> double {
        auto now = chrono::steady_clock::now();
        return chrono::duration<double>(now - t_start).count();
    };

    // popcount(10bit)テーブル
    static uint8_t pop10[1 << 10];
    for (int m = 0; m < (1 << 10); m++) pop10[m] = (uint8_t)__builtin_popcount((unsigned)m);

    // 候補30240生成 + 文字列->index簡易マップ
    vector<Cand> cand;
    cand.reserve(N);
    unordered_map<int,int> idx_of; // key = a*10000 + b*1000 + c*100 + d*10 + e
    idx_of.reserve(N * 2);

    for (int a = 0; a < 10; a++) for (int b = 0; b < 10; b++) if (b != a)
    for (int c = 0; c < 10; c++) if (c != a && c != b)
    for (int d = 0; d < 10; d++) if (d != a && d != b && d != c)
    for (int e = 0; e < 10; e++) if (e != a && e != b && e != c && e != d) {
        Cand x;
        x.d = {(uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e};
        x.mask = (uint16_t)((1<<a)|(1<<b)|(1<<c)|(1<<d)|(1<<e));
        int key = a*10000 + b*1000 + c*100 + d*10 + e;
        int id = (int)cand.size();
        cand.push_back(x);
        idx_of[key] = id;
    }
    // 念のため
    if ((int)cand.size() != N) return 0;

    auto idx_from_string = [&](const string &s) -> int {
        int key = 0;
        for (int i = 0; i < L; i++) key = key * 10 + (s[i] - '0');
        auto it = idx_of.find(key);
        if (it == idx_of.end()) return -1;
        return it->second;
    };

    auto print_query = [&](int q_idx) {
        const auto &d = cand[q_idx].d;
        for (int i = 0; i < L; i++) cout << char('0' + d[i]);
        cout << "\n" << flush; // flush必須
    };

    auto read_response = [&]() -> vector<pair<int,int>> {
        vector<pair<int,int>> hb(30);
        for (int i = 0; i < 30; i++) {
            if (!(cin >> hb[i].first >> hb[i].second)) {
                // EOF等
                exit(0);
            }
        }
        return hb;
    };

    auto compute_code_to = [&](int q_idx) -> vector<uint8_t> {
        vector<uint8_t> code_to(N);
        const auto &qd = cand[q_idx].d;
        uint16_t qmask = cand[q_idx].mask;

        for (int i = 0; i < N; i++) {
            int hit = 0;
            const auto &sd = cand[i].d;
            hit += (sd[0] == qd[0]);
            hit += (sd[1] == qd[1]);
            hit += (sd[2] == qd[2]);
            hit += (sd[3] == qd[3]);
            hit += (sd[4] == qd[4]);
            int common = pop10[cand[i].mask & qmask];
            int blow = common - hit;
            code_to[i] = (uint8_t)encode_code(hit, blow);
        }
        return code_to;
    };

    // 状態
    vector<char> alive(N, 1);
    vector<char> asked(N, 0);
    vector<int> alive_list;
    alive_list.reserve(N);
    for (int i = 0; i < N; i++) alive_list.push_back(i);

    vector<QueryInfo> hist;
    hist.reserve(80);

    int found_cnt = 0; // (5,0)の個数

    // 初期探索（固定2手）
    vector<int> probe_indices;
    if (USE_FIXED_PROBES) {
        int p1 = idx_from_string("01234");
        int p2 = idx_from_string("56789");
        if (p1 >= 0) probe_indices.push_back(p1);
        if (p2 >= 0) probe_indices.push_back(p2);
    }

    // alive_list再構築（prune含む）
    auto prune_all = [&]() {
        vector<int> next;
        next.reserve(alive_list.size());
        for (int idx : alive_list) {
            if (!alive[idx] || asked[idx]) {
                alive[idx] = 0;
                continue;
            }
            bool ok = true;
            for (const auto &q : hist) {
                if (q.rem[q.code_to[idx]] == 0) { ok = false; break; }
            }
            if (!ok) {
                alive[idx] = 0;
            } else {
                next.push_back(idx);
            }
        }
        alive_list.swap(next);
    };

    // メインループ
    int step = 0;
    while (true) {
        // 打ち切り防止：候補が尽きたら（通常起きないが）終了
        prune_all();
        if (alive_list.empty()) {
            // 最悪：未質問のものを適当に投げ続ける（ここに来ない想定）
            for (int i = 0; i < N; i++) if (!asked[i]) {
                print_query(i);
                auto hb = read_response();
                if (hb[0].first == -1) return 0;
                if (hb[0].first == 5 && hb[0].second == 0) return 0;
            }
            return 0;
        }

        int q_idx = -1;

        // 時間が厳しいなら軽量化（末尾から適当に）
        double t = elapsed_sec();
        if (t > TIME_LIMIT_SEC) {
            q_idx = alive_list[0];
        } else if (step < (int)probe_indices.size()) {
            // 初期探索
            q_idx = probe_indices[step];
            if (q_idx < 0 || asked[q_idx] || !alive[q_idx]) {
                q_idx = alive_list[0];
            }
        } else {
            // IPFで重み計算
            int remaining = 30 - found_cnt;
            // 使う過去質問を末尾K個に制限
            int K = (int)hist.size();
            K = min(K, IPF_USE_LAST);
            int start_idx = (int)hist.size() - K;

            // 残り時間で反復回数を調整
            int iters = IPF_ITERS_BASE;
            double left = TIME_LIMIT_SEC - t;
            if (left < 0.20) iters = min(iters, 2);
            else if (left < 0.40) iters = min(iters, 4);

            static vector<float> w;
            w.assign(N, 0.0f);

            // 初期重み（aliveのみ）
            float scale0 = (alive_list.empty() ? 0.0f : (float)remaining / (float)alive_list.size());
            for (int idx : alive_list) w[idx] = scale0;

            array<float, CODES> tot{};
            array<float, CODES> factor{};

            for (int it = 0; it < iters; it++) {
                for (int qi = start_idx; qi < (int)hist.size(); qi++) {
                    const auto &Q = hist[qi];
                    // tot初期化
                    tot.fill(0.0f);
                    // 集計
                    for (int idx : alive_list) {
                        tot[Q.code_to[idx]] += w[idx];
                    }
                    // factor計算
                    for (int c = 0; c < CODES; c++) {
                        if (tot[c] > 1e-20f) factor[c] = (float)Q.rem[c] / tot[c];
                        else factor[c] = 0.0f;
                    }
                    // 更新
                    for (int idx : alive_list) {
                        w[idx] *= factor[Q.code_to[idx]];
                    }
                }
                // 正規化（sum w = remaining）
                double sumW = 0.0;
                for (int idx : alive_list) sumW += (double)w[idx];
                if (sumW > 0) {
                    float s = (float)((double)remaining / sumW);
                    for (int idx : alive_list) w[idx] *= s;
                }
            }

            // 最大重みを選ぶ
            float best = -1.0f;
            int best_idx = alive_list[0];
            for (int idx : alive_list) {
                if (w[idx] > best) { best = w[idx]; best_idx = idx; }
            }
            q_idx = best_idx;
        }

        // 質問
        print_query(q_idx);
        auto hb = read_response();

        // 不正/終了チェック
        if (hb[0].first == -1) return 0;
        if (hb[0].first == 5 && hb[0].second == 0) return 0;

        // found_cnt更新（(5,0)の数）
        int new_found = 0;
        for (auto &p : hb) if (p.first == 5 && p.second == 0) new_found++;

        // もし今回で新しく秘密を当てた（= q_idx が秘密の一つ）なら、
        // 過去の全クエリのremからこの秘密分を差し引く
        if (new_found > found_cnt) {
            for (auto &Q : hist) {
                int c = Q.code_to[q_idx];
                if (Q.rem[c] > 0) Q.rem[c]--;
            }
        }
        found_cnt = new_found;

        // q_idxは二度と使わない（当たりでも外れでも、秘密は重複しないので）
        asked[q_idx] = 1;
        alive[q_idx] = 0;

        // 今回のクエリを制約として追加
        QueryInfo qi;
        qi.q_idx = q_idx;
        qi.rem.fill(0);

        // (5,0) は「既発見扱い」なので rem に入れない
        for (auto &p : hb) {
            if (p.first == 5 && p.second == 0) continue;
            int code = encode_code(p.first, p.second);
            qi.rem[code]++;
        }
        qi.code_to = compute_code_to(q_idx);
        hist.push_back(std::move(qi));

        step++;
    }
}