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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-15 21:08:32
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,545 ms / 5,000 ms
• コード長: 18,937 bytes
• コンパイル時間: 3,830 ms
• コンパイル使用メモリ: 314,560 KB
• 実行使用メモリ: 29,872 KB
• スコア: 9,995,778
• 平均クエリ数: 42.22
• 最終ジャッジ日時: 2025-12-25 01:49:03
• 合計ジャッジ時間: 134,288 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

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

ソースコード

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

// =============================================================
// Time / effort knobs
// =============================================================
// Total time budget in ms (keep < 5000 to be safe).
#ifndef TIME_BUDGET_MS
#define TIME_BUDGET_MS 4950
#endif

// BASE_LEVEL: baseline heaviness (0: light, 1: medium, 2: heavy)
#ifndef BASE_LEVEL
#define BASE_LEVEL 2
#endif

static constexpr int HARD_GUARD_MS = 30; // stop heavy work when remaining < this

// =============================================================
// Problem constants
// =============================================================
static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int T = 21;          // number of (H,B) with H+B<=5
static constexpr int M_TOTAL = 30;
static constexpr int N_ALL = 30240;

static int IDX[L+1][L+1];

struct Stopwatch {
    chrono::steady_clock::time_point st = chrono::steady_clock::now();
    inline int ms() const {
        return (int)chrono::duration_cast<chrono::milliseconds>(
            chrono::steady_clock::now() - st).count();
    }
};

struct XorShift {
    uint64_t x = 88172645463325252ull;
    inline uint64_t next() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    inline int next_int(int lo, int hi) { // inclusive
        return lo + (int)(next() % (uint64_t)(hi - lo + 1));
    }
};

struct Code {
    array<uint8_t, L> d{};
    uint16_t mask = 0;
    string s;
};

static vector<Code> generate_all_codes() {
    vector<Code> all;
    all.reserve(N_ALL);

    array<uint8_t, L> cur{};
    string buf(L, '0');

    function<void(int, uint16_t)> dfs = [&](int pos, uint16_t mask) {
        if (pos == L) {
            Code c;
            c.d = cur;
            c.mask = mask;
            c.s = buf;
            all.push_back(std::move(c));
            return;
        }
        for (int dig = 0; dig < DIG; dig++) {
            if (mask & (1u << dig)) continue;
            cur[pos] = (uint8_t)dig;
            buf[pos] = char('0' + dig);
            dfs(pos + 1, (uint16_t)(mask | (1u << dig)));
        }
    };
    dfs(0, 0);
    return all;
}

static inline uint8_t type_idx(const Code &a, const Code &q) {
    int hit = 0;
    for (int i = 0; i < L; i++) hit += (a.d[i] == q.d[i]);
    int common = __builtin_popcount((unsigned)(a.mask & q.mask));
    int blow = common - hit;
    return (uint8_t)IDX[hit][blow];
}

// =============================================================
// Dynamic parameter computation (spend time if we are "ahead of schedule")
// =============================================================
struct DynParams {
    int ipfIters;
    int ipfRecent;
    double hitThreshold; // if best weight >= threshold, go for hit
    int infoPoolTop;
    int infoPoolRand;
    int infoSample;
    bool enableInfo;
};

struct ParamScheduler {
    Stopwatch &sw;
    int &qDone;
    int &foundCount;

    // Smoothed hit-rate estimate (for query count forecast)
    // Start with a mild prior to avoid exploding when found=0.
    double hitEMA = 0.18;

    explicit ParamScheduler(Stopwatch &sw_, int &qDone_, int &foundCount_)
        : sw(sw_), qDone(qDone_), foundCount(foundCount_) {}

    inline bool near_deadline() const {
        return sw.ms() >= TIME_BUDGET_MS - HARD_GUARD_MS;
    }

    // Update after each query
    void feed(bool hit) {
        double obs = hit ? 1.0 : 0.0;
        hitEMA = 0.92 * hitEMA + 0.08 * obs;
        hitEMA = min(0.95, max(0.03, hitEMA));
    }

    // Forecast total queries based on current hit rate.
    int estimate_total_queries() const {
        // expected queries to get 30 hits with hit prob ~= hitEMA
        double p = max(0.06, hitEMA);
        int est = (int)round((double)M_TOTAL / p);

        // Clamp to reasonable band (empirically this game often finishes ~35-50 in decent solvers)
        est = max(32, min(70, est));

        // Add a small buffer for information queries
        est += 2;
        return est;
    }

    // schedule-based scaling:
    // if elapsed is lower than ideal schedule, scale > 1 to spend more time;
    // if higher, scale < 1 to save time.
    double schedule_scale() const {
        int elapsed = sw.ms();
        int Qest = estimate_total_queries();

        double progress = (double)(qDone + 1) / (double)max(1, Qest);
        progress = min(1.2, max(0.0, progress));

        double idealElapsed = progress * (double)TIME_BUDGET_MS;

        double ratio = (idealElapsed + 120.0) / (elapsed + 120.0);
        ratio = min(2.2, max(0.55, ratio));

        // If near deadline, force small scale.
        if (elapsed >= TIME_BUDGET_MS - HARD_GUARD_MS) ratio = 0.55;

        return ratio;
    }

    DynParams make() const {
        DynParams dp{};

        double s = schedule_scale();

        // Base values by BASE_LEVEL
        int ipfI_base, ipfR_base;
        int poolTop_base, poolRand_base, sample_base;
        double thr_base;

#if BASE_LEVEL == 0
        ipfI_base = 5;  ipfR_base = 20;
        poolTop_base = 70; poolRand_base = 180; sample_base = 1800;
        thr_base = 0.74;
#elif BASE_LEVEL == 1
        ipfI_base = 7;  ipfR_base = 34;
        poolTop_base = 100; poolRand_base = 260; sample_base = 3000;
        thr_base = 0.71;
#else
        ipfI_base = 9;  ipfR_base = 50;
        poolTop_base = 140; poolRand_base = 420; sample_base = 5200;
        thr_base = 0.69;
#endif

        // Remaining secrets: early = more info queries, late = more direct hits
        int rem = M_TOTAL - foundCount;
        double phase = 1.0 - (double)rem / (double)M_TOTAL; // 0 early -> 1 late

        // Hit threshold increases later (prefer sure hits near end)
        double thr = thr_base + 0.10 * phase;
        thr = min(0.82, max(0.62, thr));

        dp.ipfIters = (int)round(ipfI_base * pow(s, 0.85));
        dp.ipfRecent = (int)round(ipfR_base * pow(s, 0.70));

        dp.ipfIters = max(3, min(14, dp.ipfIters));
        dp.ipfRecent = max(12, min(90, dp.ipfRecent));

        dp.hitThreshold = thr;

        dp.enableInfo = true;
        dp.infoPoolTop  = (int)round(poolTop_base  * s);
        dp.infoPoolRand = (int)round(poolRand_base * s);
        dp.infoSample   = (int)round(sample_base   * s);

        dp.infoPoolTop  = max(40, min(260, dp.infoPoolTop));
        dp.infoPoolRand = max(80, min(900, dp.infoPoolRand));
        dp.infoSample   = max(1200, min(9000, dp.infoSample));

        // If very late, reduce info search (it tends to add extra misses)
        if (rem <= 6) {
            dp.infoPoolTop  = min(dp.infoPoolTop, 80);
            dp.infoPoolRand = min(dp.infoPoolRand, 160);
            dp.infoSample   = min(dp.infoSample, 2200);
        }

        // Near deadline: disable expensive info search
        if (near_deadline()) {
            dp.enableInfo = false;
            dp.ipfIters = min(dp.ipfIters, 4);
            dp.ipfRecent = min(dp.ipfRecent, 16);
        }

        return dp;
    }
};

// =============================================================
// Solver
// =============================================================
struct Solver {
    const vector<Code> &codes;
    const int N;

    Stopwatch sw;
    XorShift rng;

    vector<char> possible; // still can be an unfound secret
    vector<char> asked;    // already queried
    vector<char> found;    // already confirmed secret

    int qDone = 0;
    int foundCount = 0;

    struct Record {
        int qid;
        array<int, T> need;        // histogram for remaining secrets (excluding (5,0))
        array<int, T> aliveCnt;    // number of possible candidates per bucket
        array<vector<int>, T> members; // candidates by bucket (static list for this query)
    };

    vector<Record> recs;
    vector<vector<uint8_t>> typeCache; // typeCache[r][cid] = type(codes[cid], query[r])

    ParamScheduler scheduler;

    explicit Solver(const vector<Code>& codes_)
        : codes(codes_), N((int)codes_.size()),
          possible(N, 1), asked(N, 0), found(N, 0),
          scheduler(sw, qDone, foundCount) {}

    inline bool out_of_time() const {
        return sw.ms() >= TIME_BUDGET_MS - HARD_GUARD_MS;
    }

    void kill_candidate(int cid) {
        if (!possible[cid]) return;
        possible[cid] = 0;
        // Update aliveCnt for all records
        for (int r = 0; r < (int)recs.size(); r++) {
            int t = typeCache[r][cid];
            recs[r].aliveCnt[t]--;
        }
    }

    void eliminate_bucket(int r, int t) {
        // need[t]==0 => no remaining secret can be in this bucket
        for (int cid : recs[r].members[t]) {
            if (!asked[cid] && possible[cid]) kill_candidate(cid);
        }
    }

    void add_record(int qid, const array<int,T> &hist) {
        Record rec;
        rec.qid = qid;
        rec.need = hist;
        rec.aliveCnt.fill(0);
        for (int t = 0; t < T; t++) rec.members[t].clear();

        vector<uint8_t> row(N);
        for (int cid = 0; cid < N; cid++) {
            uint8_t t = type_idx(codes[cid], codes[qid]);
            row[cid] = t;
            rec.members[t].push_back(cid);
        }

        recs.push_back(std::move(rec));
        typeCache.push_back(std::move(row));
        int r = (int)recs.size() - 1;

        // init aliveCnt
        for (int cid = 0; cid < N; cid++) {
            if (possible[cid] && !asked[cid]) recs[r].aliveCnt[typeCache[r][cid]]++;
        }

        // zero-bucket elimination
        for (int t = 0; t < T; t++) {
            if (recs[r].need[t] == 0) eliminate_bucket(r, t);
        }
    }

    void apply_found_secret_to_past(int sid) {
        // This new secret was counted in past records' histograms; remove it now.
        for (int r = 0; r < (int)recs.size(); r++) {
            int t = typeCache[r][sid];
            if (recs[r].need[t] > 0) {
                recs[r].need[t]--;
                if (recs[r].need[t] == 0) eliminate_bucket(r, t);
            }
        }
    }

    int find_forced_hit() {
        // If need[t] == aliveCnt[t] > 0, all candidates in that bucket must be secrets.
        for (int r = 0; r < (int)recs.size(); r++) {
            for (int t = 0; t < T; t++) {
                int need = recs[r].need[t];
                int aliveC = recs[r].aliveCnt[t];
                if (need > 0 && aliveC == need) {
                    for (int cid : recs[r].members[t]) {
                        if (possible[cid] && !asked[cid]) return cid; // guaranteed hit
                    }
                }
            }
        }
        return -1;
    }

    void ipf_weights(const vector<int>& cand, int useR, int iters,
                     vector<double>& w, vector<double>& wById) {
        int M = M_TOTAL - foundCount;
        int K = (int)cand.size();

        w.assign(K, (double)M / (double)max(1, K));
        wById.assign(N, 0.0);

        int R = (int)recs.size();
        int rs = max(0, R - useR);

        array<double, T> sum;
        array<double, T> fac;

        for (int it = 0; it < iters; it++) {
            for (int r = rs; r < R; r++) {
                sum.fill(0.0);
                auto &row = typeCache[r];
                for (int i = 0; i < K; i++) sum[row[cand[i]]] += w[i];

                for (int t = 0; t < T; t++) {
                    if (recs[r].need[t] == 0 || sum[t] <= 0.0) fac[t] = 0.0;
                    else fac[t] = (double)recs[r].need[t] / sum[t];
                }
                for (int i = 0; i < K; i++) w[i] *= fac[typeCache[r][cand[i]]];
            }
            // normalize to sum M
            double tot = 0.0;
            for (double x : w) tot += x;
            if (tot <= 0.0) break;
            double mul = (double)M / tot;
            for (double &x : w) x *= mul;

            if (out_of_time()) break;
        }

        for (int i = 0; i < K; i++) wById[cand[i]] = w[i];
    }

    int choose_info_query(const vector<int>& cand,
                          const vector<double>& w,
                          const vector<double>& wById,
                          const DynParams& dp) {
        int K = (int)cand.size();
        int M = M_TOTAL - foundCount;

        // Top candidates by weight
        vector<int> idx(K);
        iota(idx.begin(), idx.end(), 0);
        int wantTop = min(dp.infoPoolTop, K);
        nth_element(idx.begin(), idx.begin() + wantTop, idx.end(),
                    [&](int a, int b){ return w[a] > w[b]; });
        idx.resize(wantTop);
        sort(idx.begin(), idx.end(), [&](int a, int b){ return w[a] > w[b]; });

        // Build query pool
        vector<int> pool;
        pool.reserve(dp.infoPoolTop + dp.infoPoolRand);

        vector<char> inPool(N, 0);
        for (int j : idx) {
            int qid = cand[j];
            if (asked[qid]) continue;
            if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
        }
        while ((int)pool.size() < wantTop + dp.infoPoolRand && !out_of_time()) {
            int qid = rng.next_int(0, N-1);
            if (asked[qid]) continue;
            if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
        }
        if (pool.empty()) return cand[idx[0]];

        // Sample candidates for evaluation
        int sampleN = min(dp.infoSample, K);
        vector<int> sidx;
        sidx.reserve(sampleN);

        int topPart = (int)round(sampleN * 0.75);
        topPart = min(topPart, (int)idx.size());
        for (int i = 0; i < topPart; i++) sidx.push_back(idx[i]);
        while ((int)sidx.size() < sampleN && !out_of_time()) {
            sidx.push_back(rng.next_int(0, K-1));
        }

        vector<double> mass(T);
        vector<int> cnt(T);

        // scoring coefficients
        const double COEF_ENT  = 1.00;
        const double COEF_ELIM = 0.08;
        const double COEF_HIT  = 0.65;

        int bestQ = pool[0];
        double bestScore = -1e300;

        for (int qid : pool) {
            fill(mass.begin(), mass.end(), 0.0);
            fill(cnt.begin(), cnt.end(), 0);

            double tot = 0.0;
            for (int j : sidx) {
                int sid = cand[j];
                double ww = w[j];
                uint8_t t = type_idx(codes[sid], codes[qid]);
                mass[t] += ww;
                cnt[t]  += 1;
                tot += ww;
            }
            if (tot <= 0.0) continue;

            // entropy
            double ent = 0.0;
            for (int t = 0; t < T; t++) {
                if (mass[t] <= 0.0) continue;
                double p = mass[t] / tot;
                ent -= p * log(p);
            }

            // expected elimination (rough):
            // if a type bucket gets 0 remaining secrets, we can eliminate that bucket.
            // prob(bucket gets 0) ~ (1-p)^M
            double expElim = 0.0;
            for (int t = 0; t < T; t++) {
                if (mass[t] <= 0.0) continue;
                double p = mass[t] / tot;
                double q = max(1e-12, 1.0 - p);
                double probZero = exp((double)M * log(q));
                double estBucketSize = (double)cnt[t] * ((double)K / (double)sampleN);
                expElim += estBucketSize * probZero;
            }

            double hitP = wById[qid]; // 0 if qid isn't candidate
            double score = COEF_ENT * ent + COEF_ELIM * (expElim / (double)max(1, K)) + COEF_HIT * hitP;

            if (score > bestScore) {
                bestScore = score;
                bestQ = qid;
            }
            if (out_of_time()) break;
        }

        return bestQ;
    }

    int choose_next() {
        if (foundCount >= M_TOTAL) return -1;

        // If near deadline, keep it simple.
        if (out_of_time()) {
            for (int cid = 0; cid < N; cid++) if (!asked[cid]) return cid;
            return 0;
        }

        // Forced hit first
        int forced = find_forced_hit();
        if (forced != -1) return forced;

        // First query: any is symmetric under uniform secret distribution, so pick lex-min.
        if (recs.empty()) return 0; // "01234"

        // Build candidate list
        vector<int> cand;
        cand.reserve(N);
        for (int cid = 0; cid < N; cid++) {
            if (possible[cid] && !asked[cid]) cand.push_back(cid);
        }
        if (cand.empty()) {
            for (int cid = 0; cid < N; cid++) if (!asked[cid]) return cid;
            return 0;
        }

        // Dynamic params
        DynParams dp = scheduler.make();

        // IPF weights (recent records only)
        vector<double> w, wById;
        int useR = min(dp.ipfRecent, (int)recs.size());
        int iters = dp.ipfIters;

        ipf_weights(cand, useR, iters, w, wById);

        // Best candidate to hit
        int bestI = 0;
        for (int i = 1; i < (int)cand.size(); i++) if (w[i] > w[bestI]) bestI = i;
        int bestCid = cand[bestI];
        double bestW = w[bestI];

        // If confident enough, go for hit
        if (bestW >= dp.hitThreshold || !dp.enableInfo || out_of_time()) {
            return bestCid;
        }

        // Otherwise, spend time to find a more informative query
        return choose_info_query(cand, w, wById, dp);
    }

    void observe(int qid, const vector<pair<int,int>> &hb) {
        // invalid -> exit immediately :contentReference[oaicite:5]{index=5}
        if (hb[0].first == -1 && hb[0].second == -1) exit(0);

        int cnt50 = 0;
        array<int,T> hist{};
        hist.fill(0);
        for (auto &p: hb) {
            if (p.first == 5 && p.second == 0) cnt50++;
            else hist[IDX[p.first][p.second]]++;
        }

        bool hit = (cnt50 == foundCount + 1);

        asked[qid] = 1;
        // remove qid from remaining-secret candidates either way
        kill_candidate(qid);

        if (hit) {
            found[qid] = 1;
            foundCount++;
            apply_found_secret_to_past(qid);
        }

        add_record(qid, hist);

        qDone++;
        scheduler.feed(hit);
    }
};

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

    // Build IDX (H,B)->0..20
    int id = 0;
    for (int h = 0; h <= L; h++) {
        for (int b = 0; b <= L - h; b++) IDX[h][b] = id++;
    }

    vector<Code> codes = generate_all_codes();
    Solver solver(codes);

    while (true) {
        int qid = solver.choose_next();
        if (qid < 0) return 0;

        // Output query and flush (mandatory) :contentReference[oaicite:6]{index=6}
        cout << codes[qid].s << "\n" << flush;

        // Read all 30 lines (mandatory) :contentReference[oaicite:7]{index=7}
        vector<pair<int,int>> hb(M_TOTAL);
        for (int i = 0; i < M_TOTAL; i++) {
            if (!(cin >> hb[i].first >> hb[i].second)) return 0;
        }

        // Termination: answers are sorted; if (H0,B0)=(5,0) then all are (5,0), so solved. :contentReference[oaicite:8]{index=8}
        if (hb[0].first == 5 && hb[0].second == 0) return 0;

        solver.observe(qid, hb);
    }
}