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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-15 04:47:42
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 99 ms / 5,000 ms
• コード長: 7,719 bytes
• コンパイル時間: 3,359 ms
• コンパイル使用メモリ: 298,060 KB
• 実行使用メモリ: 29,792 KB
• スコア: 9,995,808
• 平均クエリ数: 41.92
• 最終ジャッジ日時: 2025-12-25 01:42:57
• 合計ジャッジ時間: 16,547 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

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

ソースコード

// By GPT 5.2 Pro n-th attempt
#include <bits/stdc++.h>
using namespace std;

/*
  "30個並列ごちゃ混ぜHit&Blow" solver.

  - Reply is 30 (h,b) pairs sorted lexicographically.
  - Once we ever query a secret string, that secret returns (5,0) forever.
  - Removing (5,0) pairs from the reply gives the histogram of types over the still-unknown secrets.

  We keep those histograms as constraints (records).
  Candidate ranking is done by IPF / raking:
    weights w[x] are adjusted so that for every record, bucket sums match observed counts.
  Then we query the max-weight candidate (highest estimated marginal probability).
*/

static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int T = 21; // number of (h,b) types with h+b<=5
static int idxOf[L + 1][L + 1];

struct Code {
    array<uint8_t, L> d;
    uint16_t mask;
};

static vector<Code> gen_all_codes() {
    vector<Code> all;
    all.reserve(30240);
    array<uint8_t, L> cur;
    function<void(int, uint16_t)> dfs = [&](int pos, uint16_t mask) {
        if (pos == L) {
            all.push_back(Code{cur, mask});
            return;
        }
        for (int dig = 0; dig < DIG; dig++) {
            if (mask & (1u << dig)) continue;
            cur[pos] = (uint8_t)dig;
            dfs(pos + 1, (uint16_t)(mask | (1u << dig)));
        }
    };
    dfs(0, 0);
    return all;
}

inline int type_idx(const Code &a, const Code &q) {
    int h = 0;
    for (int i = 0; i < L; i++) h += (a.d[i] == q.d[i]);
    int common = __builtin_popcount((unsigned)(a.mask & q.mask));
    int b = common - h;
    return idxOf[h][b];
}

struct Record {
    int qid;                        // query id
    array<int, T> cnt;              // histogram for CURRENT unknown set
    array<vector<int>, T> members;  // codes in each bucket (static, for fast elimination)
};

struct Solver {
    const vector<Code> &codes;
    const vector<string> &codeStr;
    int N;

    vector<char> asked; // queried already
    vector<char> found; // already discovered secret
    vector<char> alive; // still possible to be secret

    int foundCount = 0; // number of discovered secrets

    vector<Record> recs;
    vector<vector<uint8_t>> typeCache; // typeCache[ri][cid] = type index (0..20)

    explicit Solver(const vector<Code> &codes_, const vector<string> &codeStr_)
        : codes(codes_), codeStr(codeStr_), N((int)codes_.size()),
          asked(N, 0), found(N, 0), alive(N, 1) {}

    inline void eliminate_bucket(int ri, int t) {
        for (int cid : recs[ri].members[t]) alive[cid] = 0;
    }

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

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

        int ri = (int)recs.size();
        recs.push_back(std::move(rec));
        typeCache.push_back(std::move(row));

        // Exact pruning: if a bucket count is 0, no remaining secret can be in that bucket.
        for (int t = 0; t < T; t++) {
            if (recs[ri].cnt[t] == 0) eliminate_bucket(ri, t);
        }
    }

    void mark_asked_nonsecret(int qid) {
        asked[qid] = 1;
        alive[qid] = 0;
    }

    void mark_found(int qid) {
        found[qid] = 1;
        alive[qid] = 0;

        // Remove this secret from all previous histograms.
        // If a bucket becomes 0, eliminate the whole bucket immediately.
        for (int ri = 0; ri < (int)recs.size(); ri++) {
            int t = typeCache[ri][qid];
            int before = recs[ri].cnt[t];
            recs[ri].cnt[t]--;
            if (recs[ri].cnt[t] < 0) recs[ri].cnt[t] = 0;
            if (before > 0 && recs[ri].cnt[t] == 0) {
                eliminate_bucket(ri, t);
            }
        }
    }

    int choose_next_query() {
        if (recs.empty()) return 0; // first query: 01234

        int M = 30 - foundCount;

        vector<int> cand;
        cand.reserve(N);
        for (int cid = 0; cid < N; cid++) {
            if (!alive[cid]) continue;
            if (asked[cid] || found[cid]) continue;
            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 -1;
        }

        int K = (int)cand.size();
        vector<double> w(K, (double)M / (double)K); // expected membership counts

        // IPF / raking
        const int iters = 4;
        array<double, T> S;
        array<double, T> factor;

        for (int it = 0; it < iters; it++) {
            for (int ri = 0; ri < (int)recs.size(); ri++) {
                S.fill(0.0);
                for (int j = 0; j < K; j++) {
                    int cid = cand[j];
                    int t = typeCache[ri][cid];
                    S[t] += w[j];
                }
                for (int t = 0; t < T; t++) {
                    if (recs[ri].cnt[t] == 0 || S[t] <= 0.0) factor[t] = 0.0;
                    else factor[t] = (double)recs[ri].cnt[t] / S[t];
                }
                for (int j = 0; j < K; j++) {
                    int cid = cand[j];
                    int t = typeCache[ri][cid];
                    w[j] *= factor[t];
                }
            }
        }

        // choose max weight
        int best = cand[0];
        double bestw = -1.0;
        for (int j = 0; j < K; j++) {
            if (w[j] > bestw) {
                bestw = w[j];
                best = cand[j];
            }
        }
        return best;
    }
};

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

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

    const vector<Code> codes = gen_all_codes();
    const int N = (int)codes.size();

    // Prebuild strings for fast output
    vector<string> codeStr(N);
    for (int i = 0; i < N; i++) {
        string s;
        s.reserve(L);
        for (int k = 0; k < L; k++) s.push_back(char('0' + codes[i].d[k]));
        codeStr[i] = s;
    }

    Solver solver(codes, codeStr);

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

        cout << codeStr[qid] << "\n" << flush; // flush is required

        // read 30 answers (must read all)
        array<int, T> hist{};
        hist.fill(0);
        int cnt50 = 0;

        int firstH = 0, firstB = 0;
        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0; // EOF
            if (i == 0) {
                firstH = h;
                firstB = b;
            }
            if (h == 5 && b == 0) {
                cnt50++;
            } else {
                hist[idxOf[h][b]]++;
            }
        }

        // invalid interaction
        if (firstH == -1 && firstB == -1) return 0;

        // all found: reply is all (5,0), and since sorted, the first is (5,0)
        if (firstH == 5 && firstB == 0) return 0;

        solver.asked[qid] = 1;

        if (cnt50 > solver.foundCount) {
            // hit: qid is a newly discovered secret
            solver.foundCount = cnt50;
            solver.mark_found(qid);
        } else {
            // miss
            solver.mark_asked_nonsecret(qid);
        }

        // add constraint for the CURRENT unknown set
        solver.add_record(qid, hist);
    }
}