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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-16 00:04:58
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 143 ms / 5,000 ms
• コード長: 7,532 bytes
• コンパイル時間: 4,597 ms
• コンパイル使用メモリ: 301,060 KB
• 実行使用メモリ: 25,972 KB
• スコア: 9,995,819
• 平均クエリ数: 41.81
• 最終ジャッジ日時: 2025-12-25 01:51:39
• 合計ジャッジ時間: 21,021 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

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

// =====================
//  Code representation
// =====================
struct Code {
    array<uint8_t, 5> d;  // digits
    uint16_t mask;        // 10-bit mask
    string s;             // "01234"
};

static int OFF[6];                 // offset for type index
static const int TYPE20 = 20;      // (5,0)
static const int N = 30240;        // 10P5

// type index from (hits, blows)
inline int hb_to_type(int h, int b) {
    return OFF[h] + b;
}

// =====================
// Query info
// =====================
struct QueryInfo {
    int qidx;                    // index in codes[]
    vector<uint8_t> types;       // types[i] = type(secret=codes[i], query=this->qidx)
    array<int, 21> rem;          // remaining unknown secrets count per type for THIS query
};

// popcount for uint16_t
inline int popc16(uint16_t x) { return __builtin_popcount((unsigned)x); }

// Compute type(secretIdx, queryIdx)
inline uint8_t calc_type(const vector<Code>& codes, int secretIdx, int queryIdx) {
    const auto& a = codes[secretIdx];
    const auto& q = codes[queryIdx];
    int hit = 0;
    for (int i = 0; i < 5; i++) hit += (a.d[i] == q.d[i]);
    int common = popc16(a.mask & q.mask);
    int blow = common - hit;
    return (uint8_t)hb_to_type(hit, blow);
}

// Choose IPF iterations based on time/candidate size (runtime tuning)
int choose_ipf_iters(double elapsed_sec, int cand_size) {
    // Safe-ish tuning: more iterations early, fewer late.
    if (elapsed_sec > 4.3) return 2;
    if (elapsed_sec > 3.5) return 3;
    if (cand_size > 20000) return 3;
    return 5;
}

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

    // Build OFF[]
    OFF[0] = 0;
    for (int h = 0; h < 5; h++) OFF[h + 1] = OFF[h] + (6 - h);

    // Generate all 10P5 codes
    vector<Code> codes;
    codes.reserve(N);
    unordered_map<string, int> idx_of;
    idx_of.reserve(N * 2);

    for (int a = 0; a <= 9; a++) for (int b = 0; b <= 9; b++) if (b != a)
    for (int c = 0; c <= 9; c++) if (c != a && c != b)
    for (int d = 0; d <= 9; d++) if (d != a && d != b && d != c)
    for (int e = 0; e <= 9; e++) if (e != a && e != b && e != c && e != d) {
        Code x;
        x.d = {(uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e};
        x.mask = (uint16_t)((1u<<a)|(1u<<b)|(1u<<c)|(1u<<d)|(1u<<e));
        x.s.resize(5);
        x.s[0] = char('0'+a);
        x.s[1] = char('0'+b);
        x.s[2] = char('0'+c);
        x.s[3] = char('0'+d);
        x.s[4] = char('0'+e);
        int id = (int)codes.size();
        codes.push_back(x);
        idx_of[x.s] = id;
    }

    // Initial query
    int qidx = idx_of["01234"];

    // state: 0 = unqueried, 1 = queried miss, 2 = found
    vector<uint8_t> state(N, 0);

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

    int foundCount = 0;
    auto t0 = chrono::steady_clock::now();

    while (true) {
        // Ask
        cout << codes[qidx].s << "\n";
        cout.flush();

        // Read response: 30 lines of (Hi, Bi)
        array<int, 21> raw{};
        raw.fill(0);
        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0;  // EOF safeguard
            if (h == -1 && b == -1) return 0; // judge error
            // type index
            int t = hb_to_type(h, b);
            raw[t]++;
        }

        int beforeFound = foundCount;
        int afterFound = raw[TYPE20];
        bool hit = (afterFound > beforeFound);

        // Build query info: types for all codes
        QueryInfo qi;
        qi.qidx = qidx;
        qi.types.resize(N);
        for (int i = 0; i < N; i++) {
            qi.types[i] = calc_type(codes, i, qidx);
        }

        // Initialize remaining counts for "unknown secrets now"
        qi.rem = raw;
        // subtract secrets that were already found BEFORE this query
        qi.rem[TYPE20] -= beforeFound;

        queries.push_back(std::move(qi));
        int k = (int)queries.size() - 1;

        if (hit) {
            // qidx itself is a new secret
            state[qidx] = 2;
            foundCount++;

            // Retroactively subtract this secret from all previous queries:
            // for queries < k: it contributed its actual type
            for (int j = 0; j < k; j++) {
                uint8_t t = queries[j].types[qidx];
                queries[j].rem[t]--;
            }
            // for query k: it contributed (5,0)
            queries[k].rem[TYPE20]--;
        } else {
            state[qidx] = 1;
        }

        if (foundCount >= 30) break;

        // Recompute candidate list (only eliminate by 0-bins + already-asked)
        vector<int> cand;
        cand.reserve(N);
        for (int i = 0; i < N; i++) {
            if (state[i] != 0) continue;
            bool ok = true;
            for (const auto& qq : queries) {
                uint8_t t = qq.types[i];
                if (qq.rem[t] == 0) { ok = false; break; }
            }
            if (ok) cand.push_back(i);
        }

        if (cand.empty()) {
            // Should not happen if everything is consistent, but just in case:
            for (int i = 0; i < N; i++) if (state[i] == 0) { qidx = i; break; }
            continue;
        }

        // IPF to estimate max-entropy distribution p over candidates
        int C = (int)cand.size();
        vector<double> p(C, 1.0 / (double)C);

        int remaining = 30 - foundCount;

        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration<double>(now - t0).count();
        int iters = choose_ipf_iters(elapsed, C);

        for (int it = 0; it < iters; it++) {
            for (const auto& qq : queries) {
                double curr[21];
                for (int t = 0; t < 21; t++) curr[t] = 0.0;

                for (int i = 0; i < C; i++) {
                    uint8_t t = qq.types[cand[i]];
                    curr[t] += p[i];
                }

                double factor[21];
                for (int t = 0; t < 21; t++) {
                    if (qq.rem[t] <= 0) {
                        factor[t] = 0.0; // candidates should not be in this bin anyway
                    } else {
                        double target = (double)qq.rem[t] / (double)remaining;
                        double denom = curr[t];
                        if (denom <= 0.0) {
                            // In a consistent state, this shouldn't happen.
                            // Keep it neutral to avoid NaN explosion.
                            factor[t] = 1.0;
                        } else {
                            factor[t] = target / denom;
                        }
                    }
                }

                double sumP = 0.0;
                for (int i = 0; i < C; i++) {
                    uint8_t t = qq.types[cand[i]];
                    p[i] *= factor[t];
                    sumP += p[i];
                }

                if (!(sumP > 0.0) || !isfinite(sumP)) {
                    // reset if numerically broken
                    double uni = 1.0 / (double)C;
                    for (int i = 0; i < C; i++) p[i] = uni;
                } else {
                    double inv = 1.0 / sumP;
                    for (int i = 0; i < C; i++) p[i] *= inv;
                }
            }
        }

        // Choose argmax
        int bestPos = 0;
        for (int i = 1; i < C; i++) {
            if (p[i] > p[bestPos]) bestPos = i;
        }
        qidx = cand[bestPos];
    }

    return 0;
}