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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-15 18:01:46
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 228 ms / 5,000 ms
• コード長: 8,307 bytes
• コンパイル時間: 3,268 ms
• コンパイル使用メモリ: 300,108 KB
• 実行使用メモリ: 26,228 KB
• スコア: 9,995,818
• 平均クエリ数: 41.82
• 最終ジャッジ日時: 2025-12-25 01:43:27
• 合計ジャッジ時間: 25,338 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

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

ソースコード

// By GPT 5.2 Pro

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

// Parallel Mixed Hit & Blow solver
//
// Key ideas:
// 1) Keep all 30240 length-5 distinct-digit strings as candidates.
// 2) Each query returns a multiset of (Hit, Blow) for remaining secrets.
//    Treat it as a histogram constraint: for each record r and type t,
//    exactly cnt[r][t] secrets are in the bucket {x | type_r(x)=t}.
// 3) If cnt[r][t]==0 -> eliminate the whole bucket.
// 4) If bucketSize == cnt[r][t] -> forced bucket: all are secrets, query them.
// 5) Otherwise compute IPF weights (iterative proportional fitting) and query max.

static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int T = 21;          // number of (h,b) pairs with h+b<=5
static constexpr int M_TOTAL = 30;

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

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

static inline int 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 = (int)__builtin_popcount((unsigned)(a.mask & q.mask));
    int blow = common - hit;
    return idxOf[hit][blow];
}

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

    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 d = 0; d < DIG; d++) {
            if (mask & (1u << d)) continue;
            cur[pos] = (uint8_t)d;
            buf[pos] = char('0' + d);
            dfs(pos + 1, mask | (1u << d));
        }
    };
    dfs(0, 0);
    return all;
}

struct Solver {
    vector<Code> codes;
    int N = 0;

    vector<char> alive, asked, found;
    int foundCount = 0; // number of already-identified secrets

    struct Record {
        int qid;
        array<int, T> cnt; // histogram for *remaining* secrets (excluding (5,0))
    };

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

    explicit Solver(vector<Code> allCodes)
        : codes(std::move(allCodes)) {
        N = (int)codes.size();
        alive.assign(N, 1);
        asked.assign(N, 0);
        found.assign(N, 0);
    }

    void eliminate_bucket_if_zero(int ri, int t) {
        // If cnt==0 for (ri,t), no remaining secret can be in this bucket.
        // Remove all candidates that would yield type t for record ri.
        auto& row = typeCache[ri];
        for (int cid = 0; cid < N; cid++) {
            if (!alive[cid]) continue;
            if (row[cid] == t) alive[cid] = 0;
        }
    }

    void apply_zero_elimination(int ri) {
        for (int t = 0; t < T; t++) {
            if (recs[ri].cnt[t] == 0) eliminate_bucket_if_zero(ri, t);
        }
    }

    void subtract_found_secret(int sid) {
        // Remove the contribution of a newly found secret from all past records.
        for (int ri = 0; ri < (int)recs.size(); ri++) {
            int t = typeCache[ri][sid];
            if (recs[ri].cnt[t] > 0) recs[ri].cnt[t]--;
            if (recs[ri].cnt[t] == 0) eliminate_bucket_if_zero(ri, t);
        }
    }

    void add_record(int qid, const array<int, T>& hist) {
        recs.push_back({qid, hist});
        vector<uint8_t> row(N);
        for (int cid = 0; cid < N; cid++) {
            row[cid] = (uint8_t)type_idx(codes[cid], codes[qid]);
        }
        typeCache.push_back(std::move(row));
        apply_zero_elimination((int)recs.size() - 1);
    }

    void update_after_query(int qid, const array<int, T>& hist, int count50) {
        asked[qid] = 1;

        if (count50 > foundCount) {
            // hit a new secret: it must be qid
            found[qid] = 1;
            alive[qid] = 0;
            subtract_found_secret(qid);
            foundCount = count50;
        } else {
            // miss: qid is not a secret
            alive[qid] = 0;
        }
        add_record(qid, hist);
    }

    int choose_next() {
        int M = M_TOTAL - foundCount;
        vector<int> cand;
        cand.reserve(N);
        for (int cid = 0; cid < N; cid++) {
            if (alive[cid] && !asked[cid] && !found[cid]) cand.push_back(cid);
        }
        if (cand.empty()) {
            // fallback (should be rare)
            for (int cid = 0; cid < N; cid++) {
                if (!asked[cid] && !found[cid]) cand.push_back(cid);
            }
            if (cand.empty()) return 0;
        }

        // --- Forced bucket (recent records) ---
        const int R = (int)recs.size();
        const int forcedDepth = 8; // check only last few records for speed
        if (R > 0 && M > 0) {
            int start = max(0, R - forcedDepth);
            array<int, T> bucketCnt;
            for (int ri = R - 1; ri >= start; ri--) {
                bucketCnt.fill(0);
                auto& row = typeCache[ri];
                for (int cid : cand) bucketCnt[row[cid]]++;
                for (int t = 0; t < T; t++) {
                    int need = recs[ri].cnt[t];
                    if (need > 0 && bucketCnt[t] == need) {
                        // all candidates in this bucket are secrets -> guaranteed hit
                        for (int cid : cand) {
                            if (row[cid] == t) return cid;
                        }
                    }
                }
            }
        }

        // --- IPF weighting ---
        int K = (int)cand.size();
        vector<double> w(K, (double)M / (double)K);

        const int iters = 6; // tuned in local simulation
        array<double, T> sum;
        array<double, T> fac;

        for (int it = 0; it < iters; it++) {
            for (int ri = 0; ri < (int)recs.size(); ri++) {
                sum.fill(0.0);
                auto& row = typeCache[ri];

                for (int j = 0; j < K; j++) {
                    sum[row[cand[j]]] += w[j];
                }
                for (int t = 0; t < T; t++) {
                    if (recs[ri].cnt[t] == 0 || sum[t] <= 0.0) fac[t] = 0.0;
                    else fac[t] = (double)recs[ri].cnt[t] / sum[t];
                }
                for (int j = 0; j < K; j++) {
                    w[j] *= fac[row[cand[j]]];
                }

                // normalize to keep sum(w)=M (avoid underflow / overflow)
                double s = 0.0;
                for (double x : w) s += x;
                if (s > 0.0) {
                    double mul = (double)M / s;
                    for (double& x : w) x *= mul;
                } else {
                    // numerical fallback
                    std::fill(w.begin(), w.end(), (double)M / (double)K);
                }
            }
        }

        int best = 0;
        for (int j = 1; j < K; j++) if (w[j] > w[best]) best = j;
        return cand[best];
    }
};

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

    // build (h,b)->idx
    int idx = 0;
    for (int h = 0; h <= L; h++) {
        for (int b = 0; b <= L - h; b++) {
            idxOf[h][b] = idx++;
        }
    }

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

    while (true) {
        int qid = solver.choose_next();
        cout << solver.codes[qid].s << '\n' << flush;

        // read 30 pairs (always read all, even if we will terminate)
        vector<pair<int,int>> hb(M_TOTAL);
        for (int i = 0; i < M_TOTAL; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0; // EOF safety
            hb[i] = {h, b};
        }

        // invalid response (WA): all (-1,-1)
        if (hb[0].first == -1 && hb[0].second == -1) return 0;

        // termination: (H0,B0) = (5,0)  <=>  all pairs are (5,0)
        if (hb[0].first == 5 && hb[0].second == 0) return 0;

        // build histogram excluding (5,0)
        array<int, T> hist{};
        hist.fill(0);
        int cnt50 = 0;
        for (auto [h, b] : hb) {
            if (h == 5 && b == 0) {
                cnt50++;
            } else {
                hist[idxOf[h][b]]++;
            }
        }

        solver.update_after_query(qid, hist, cnt50);
    }
}