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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-14 23:32:42
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 14,111 bytes
• コンパイル時間: 4,337 ms
• コンパイル使用メモリ: 324,816 KB
• 実行使用メモリ: 33,904 KB
• スコア: 0
• 最終ジャッジ日時: 2025-12-25 01:42:39
• 合計ジャッジ時間: 16,892 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	TLE * 1 -- * 99

ソースコード

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

// Yukicoder interactive (30 parallel Hit&Blow, answers are sorted).
// Strategy:
//  1) Ask a few random queries to collect constraints.
//  2) Reconstruct the remaining hidden set by fitting the per-query (H,B) multiset counts.
//     Use simulated annealing / local search with an "anchor" query to reduce the state space.
//  3) Query the reconstructed strings; if a miss happens, treat it as extra constraint and re-solve.
//  4) Fallback: brute force remaining strings if reconstruction repeatedly fails.

static constexpr int LEN = 5;
static constexpr int MAXQ = 30240;
static constexpr int HB_STATES = 36; // id = h*6 + b
static constexpr int ID_50 = 5 * 6 + 0;

struct Code {
    array<uint8_t, LEN> d{};
    uint16_t mask = 0; // 10-bit
    string s;
};

struct Query {
    int qidx; // index into allCodes
    array<pair<int,int>, 30> resp;
};

static inline uint8_t hb_id(const Code &a, const Code &q) {
    int h = 0;
    for (int i = 0; i < LEN; i++) h += (a.d[i] == q.d[i]);
    int inter = __builtin_popcount((unsigned)(a.mask & q.mask));
    int b = inter - h;
    return (uint8_t)(h * 6 + b);
}

static vector<Code> gen_all_codes() {
    vector<Code> v;
    v.reserve(10*9*8*7*6);
    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) {
        Code x;
        x.d = { (uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e };
        x.mask = (1u<<a) | (1u<<b) | (1u<<c) | (1u<<d) | (1u<<e);
        x.s.resize(LEN);
        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);
        v.push_back(std::move(x));
    }
    return v;
}

static bool read_response(array<pair<int,int>,30> &resp) {
    for (int i = 0; i < 30; i++) {
        int H, B;
        if (!(cin >> H >> B)) return false;
        resp[i] = {H, B};
    }
    return true;
}

struct State {
    vector<Code> allCodes;
    vector<Query> history;

    vector<char> asked;
    vector<char> banned; // asked but NOT secret
    vector<char> found;

    vector<int> foundList;
    vector<int> foundAtStep; // step index of first discovery, -1 if not found

    int qcnt = 0;
    mt19937 rng;

    State(): rng(1234567) {}
};

static bool ask(State &st, int idx) {
    // output + flush (must)
    cout << st.allCodes[idx].s << '\n' << flush;
    st.qcnt++;

    Query q;
    q.qidx = idx;
    if (!read_response(q.resp)) return false;

    // invalid interaction
    if (q.resp[0].first == -1 && q.resp[0].second == -1) {
        exit(0);
    }

    // record query
    st.history.push_back(q);
    st.asked[idx] = 1;

    // termination: if sorted first is (5,0), then all are (5,0)
    if (q.resp[0].first == 5 && q.resp[0].second == 0) {
        exit(0);
    }

    // count (5,0)
    int cnt50 = 0;
    for (auto &p : q.resp) if (p.first == 5 && p.second == 0) cnt50++;

    int prevFound = (int)st.foundList.size();
    if (cnt50 > prevFound) {
        // this query is a new secret
        st.found[idx] = 1;
        st.foundAtStep[idx] = (int)st.history.size() - 1;
        st.foundList.push_back(idx);
    } else {
        // confirmed non-secret
        st.banned[idx] = 1;
    }

    return true;
}

// Compute per-query target counts for the STILL-UNKNOWN secrets (excluding all found secrets).
static vector<array<int,HB_STATES>> compute_targets(const State &st, const vector<int> &useSteps) {
    vector<array<int,HB_STATES>> targets;
    targets.reserve(useSteps.size());

    for (int step : useSteps) {
        array<int,HB_STATES> cnt{};
        cnt.fill(0);

        const auto &resp = st.history[step].resp;
        for (auto &p : resp) {
            int h = p.first;
            int b = p.second;
            int id = h * 6 + b;
            if (0 <= id && id < HB_STATES) cnt[id]++;
        }

        const Code &q = st.allCodes[st.history[step].qidx];
        // subtract found secrets
        for (int sidx : st.foundList) {
            int ds = st.foundAtStep[sidx];
            int id;
            if (step < ds) id = hb_id(st.allCodes[sidx], q);
            else           id = ID_50;
            cnt[id]--;
        }

        targets.push_back(cnt);
    }
    return targets;
}

// Choose up to maxUse most informative steps (largest number of distinct (H,B) among unknown).
static vector<int> choose_steps_for_solve(const State &st, int maxUse) {
    int T = (int)st.history.size();
    vector<pair<int,int>> scored; // (-distinct, step)
    scored.reserve(T);

    for (int step = 0; step < T; step++) {
        array<int,HB_STATES> cnt{};
        cnt.fill(0);
        for (auto &p : st.history[step].resp) {
            int id = p.first * 6 + p.second;
            if (0 <= id && id < HB_STATES) cnt[id]++;
        }

        const Code &q = st.allCodes[st.history[step].qidx];
        for (int sidx : st.foundList) {
            int ds = st.foundAtStep[sidx];
            int id = (step < ds) ? hb_id(st.allCodes[sidx], q) : ID_50;
            cnt[id]--;
        }

        int distinct = 0;
        for (int id = 0; id < HB_STATES; id++) if (cnt[id] > 0) distinct++;
        scored.push_back({-distinct, step});
    }

    sort(scored.begin(), scored.end());
    vector<int> use;
    for (int i = 0; i < (int)scored.size() && (int)use.size() < maxUse; i++) {
        use.push_back(scored[i].second);
    }
    sort(use.begin(), use.end());
    return use;
}

// Try to reconstruct remaining secrets.
// Return empty vector if K==0.
// Return nullopt if failed.
static optional<vector<int>> solve_unknown(State &st, int maxUseSteps = 25, double timeLimitSec = 1.2) {
    int K = 30 - (int)st.foundList.size();
    if (K == 0) return vector<int>{};

    // Candidate pool: not found, and not confirmed non-secret.
    vector<int> cand;
    cand.reserve(st.allCodes.size());
    for (int i = 0; i < (int)st.allCodes.size(); i++) {
        if (st.found[i]) continue;
        if (st.banned[i]) continue;
        cand.push_back(i);
    }
    if ((int)cand.size() < K) return nullopt;

    // Select steps to use
    vector<int> useSteps = choose_steps_for_solve(st, maxUseSteps);
    int t = (int)useSteps.size();
    if (t == 0) return nullopt;

    // Compute target counts
    vector<array<int,HB_STATES>> target = compute_targets(st, useSteps);

    // Determine an anchor step: maximize distinct outcomes
    int anchorPos = 0; // position in useSteps
    {
        int best = -1;
        for (int pos = 0; pos < t; pos++) {
            int distinct = 0;
            for (int id = 0; id < HB_STATES; id++) if (target[pos][id] > 0) distinct++;
            if (distinct > best) {
                best = distinct;
                anchorPos = pos;
            }
        }
    }

    // Precompute hb matrix for all codes vs used queries.
    // hbMat[codeIndex * t + pos] = id
    vector<uint8_t> hbMat(st.allCodes.size() * (size_t)t);
    for (int i = 0; i < (int)st.allCodes.size(); i++) {
        const Code &a = st.allCodes[i];
        uint8_t *row = &hbMat[(size_t)i * t];
        for (int pos = 0; pos < t; pos++) {
            const Code &q = st.allCodes[st.history[useSteps[pos]].qidx];
            row[pos] = hb_id(a, q);
        }
    }

    // Build anchor buckets for candidates
    vector<vector<int>> anchorBuckets(HB_STATES);
    for (int i : cand) {
        int id = hbMat[(size_t)i * t + anchorPos];
        anchorBuckets[id].push_back(i);
    }

    // Feasibility check on anchor distribution
    for (int id = 0; id < HB_STATES; id++) {
        if (target[anchorPos][id] > 0 && (int)anchorBuckets[id].size() < target[anchorPos][id]) {
            return nullopt;
        }
    }

    auto start = chrono::steady_clock::now();
    uniform_real_distribution<double> uni01(0.0, 1.0);

    // restarts
    const int RESTARTS = 6;
    const int MAX_ITERS = 900000;

    vector<int> posInSel(st.allCodes.size(), -1);

    for (int r = 0; r < RESTARTS; r++) {
        double elapsed = chrono::duration<double>(chrono::steady_clock::now() - start).count();
        if (elapsed > timeLimitSec) break;

        // Build initial selection satisfying anchor exactly
        vector<int> sel;
        sel.reserve(K);
        for (int id = 0; id < HB_STATES; id++) {
            int need = target[anchorPos][id];
            if (need <= 0) continue;
            std::sample(anchorBuckets[id].begin(), anchorBuckets[id].end(), back_inserter(sel), (size_t)need, st.rng);
        }
        if ((int)sel.size() != K) continue;

        fill(posInSel.begin(), posInSel.end(), -1);
        for (int i = 0; i < K; i++) posInSel[sel[i]] = i;

        vector<array<int,HB_STATES>> cur(t);
        for (int pos = 0; pos < t; pos++) cur[pos].fill(0);

        for (int idx : sel) {
            const uint8_t *row = &hbMat[(size_t)idx * t];
            for (int pos = 0; pos < t; pos++) cur[pos][row[pos]]++;
        }

        auto compute_err = [&]() -> long long {
            long long err = 0;
            for (int pos = 0; pos < t; pos++)
                for (int id = 0; id < HB_STATES; id++)
                    err += llabs(cur[pos][id] - target[pos][id]);
            return err;
        };

        long long err = compute_err();
        if (err == 0) return sel;

        const double T0 = 6.0;
        const double T1 = 0.08;

        for (int it = 0; it < MAX_ITERS; it++) {
            if ((it & 4095) == 0) {
                double el = chrono::duration<double>(chrono::steady_clock::now() - start).count();
                if (el > timeLimitSec) break;
            }

            double prog = (double)it / (double)MAX_ITERS;
            double temp = T0 * pow(T1 / T0, prog);

            int p = (int)(st.rng() % (uint32_t)K);
            int a = sel[p];
            int anchorId = hbMat[(size_t)a * t + anchorPos];

            const auto &bucket = anchorBuckets[anchorId];
            if ((int)bucket.size() <= target[anchorPos][anchorId]) continue;

            int b = -1;
            for (int tries = 0; tries < 24; tries++) {
                int candIdx = bucket[st.rng() % (uint32_t)bucket.size()];
                if (posInSel[candIdx] == -1) { b = candIdx; break; }
            }
            if (b == -1) continue;

            long long delta = 0;
            const uint8_t *rowA = &hbMat[(size_t)a * t];
            const uint8_t *rowB = &hbMat[(size_t)b * t];

            for (int pos = 0; pos < t; pos++) {
                int ida = rowA[pos];
                int idb = rowB[pos];
                if (ida == idb) continue;

                int ca = cur[pos][ida];
                int cb = cur[pos][idb];

                delta += llabs((ca - 1) - target[pos][ida]) - llabs(ca - target[pos][ida]);
                delta += llabs((cb + 1) - target[pos][idb]) - llabs(cb - target[pos][idb]);
            }

            bool accept = false;
            if (delta <= 0) accept = true;
            else {
                double prob = exp(-(double)delta / temp);
                if (uni01(st.rng) < prob) accept = true;
            }
            if (!accept) continue;

            for (int pos = 0; pos < t; pos++) {
                int ida = rowA[pos];
                int idb = rowB[pos];
                if (ida == idb) continue;
                cur[pos][ida]--;
                cur[pos][idb]++;
            }
            err += delta;

            int pa = posInSel[a];
            sel[pa] = b;
            posInSel[a] = -1;
            posInSel[b] = pa;

            if (err == 0) return sel;
        }
    }

    return nullopt;
}

static void brute_force_finish(State &st, vector<int> &order) {
    for (int idx : order) {
        if (st.qcnt >= MAXQ) break;
        if (st.asked[idx]) continue;
        ask(st, idx);
    }
}

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

    State st;
    st.allCodes = gen_all_codes();
    int N = (int)st.allCodes.size();

    st.asked.assign(N, 0);
    st.banned.assign(N, 0);
    st.found.assign(N, 0);
    st.foundAtStep.assign(N, -1);

    vector<int> randomOrder(N);
    iota(randomOrder.begin(), randomOrder.end(), 0);
    shuffle(randomOrder.begin(), randomOrder.end(), st.rng);
    int ptr = 0;

    auto next_unused = [&]() -> int {
        while (ptr < N && st.asked[randomOrder[ptr]]) ptr++;
        if (ptr >= N) return -1;
        return randomOrder[ptr++];
    };

    // Phase 1: collect constraints
    const int BASE_INFO = 12;
    while ((int)st.history.size() < BASE_INFO && st.qcnt < MAXQ) {
        int idx = next_unused();
        if (idx == -1) break;
        ask(st, idx);
    }

    // Phase 2: solve & query candidates
    while ((int)st.foundList.size() < 30 && st.qcnt < MAXQ) {
        auto sol = solve_unknown(st);
        if (!sol.has_value()) {
            // add more info queries
            for (int add = 0; add < 2 && st.qcnt < MAXQ; add++) {
                int idx = next_unused();
                if (idx == -1) break;
                ask(st, idx);
            }
            if ((int)st.history.size() > 40) {
                brute_force_finish(st, randomOrder);
                return 0;
            }
            continue;
        }

        vector<int> plan = *sol;
        shuffle(plan.begin(), plan.end(), st.rng);

        bool miss = false;
        for (int idx : plan) {
            if (st.qcnt >= MAXQ) break;
            if (st.asked[idx]) continue;

            int prevFound = (int)st.foundList.size();
            ask(st, idx);
            int nowFound = (int)st.foundList.size();

            if (nowFound == prevFound) {
                // miss -> re-solve with the new constraint
                miss = true;
                break;
            }
        }

        if (!miss) {
            // add more constraints just in case
            int idx = next_unused();
            if (idx == -1) break;
            ask(st, idx);
        }
    }

    brute_force_finish(st, randomOrder);
    return 0;
}