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

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

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

ソースコード

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

// ------------------------------
// 30-parallel Hit&Blow solver
// Strategy: pick the (currently) most probable remaining code.
// Probability is estimated by maximum-entropy raking (iterative proportional fitting)
// under the per-query (H,B) histogram constraints.
// ------------------------------

struct Code {
    array<uint8_t,5> d;
    uint16_t mask;
    array<char,6> s; // null-terminated
};

static int HB_ID[6][6];
static int ID_50;
static constexpr int K = 21; // number of (hit,blow) types

static inline int popcnt10(uint16_t x){
    return __builtin_popcount((unsigned)x);
}

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

    // Build mapping (hit,blow) -> 0..20
    for(int h=0;h<=5;h++) for(int b=0;b<=5;b++) HB_ID[h][b] = -1;
    int kk=0;
    for(int h=0;h<=5;h++){
        for(int b=0;b<=5-h;b++) HB_ID[h][b] = kk++;
    }
    ID_50 = HB_ID[5][0];

    // Generate all 10P5 codes (30240)
    vector<Code> all;
    all.reserve(30240);
    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 = (uint16_t)((1u<<a)|(1u<<b)|(1u<<c)|(1u<<d)|(1u<<e));
                        x.s = {(char)('0'+a),(char)('0'+b),(char)('0'+c),(char)('0'+d),(char)('0'+e), '\0'};
                        all.push_back(x);
                    }
                }
            }
        }
    }
    const int N = (int)all.size();

    auto hb = [&](int i, int j)->int{
        int hits = 0;
        for(int k=0;k<5;k++) hits += (all[i].d[k] == all[j].d[k]);
        int common = popcnt10((uint16_t)(all[i].mask & all[j].mask));
        int blow = common - hits;
        return HB_ID[hits][blow];
    };

    // ------------------------------
    // Solver state
    // ------------------------------
    vector<char> asked(N,false); // asked at least once (found or not)
    vector<char> alive(N,true);  // still possible to be in the remaining unknown set

    vector<int> alive_list(N);
    iota(alive_list.begin(), alive_list.end(), 0);

    // History
    vector<int> queries;                 // query indices
    vector<array<int,K>> cnt;            // residual histograms for current unknown set
    vector<vector<uint8_t>> cats;        // cats[q][i] = category of HB(query[q], i)
    vector<uint32_t> zeroMask;           // categories with count==0 for each query

    vector<double> w(N, 1.0);            // weights ~ existence probability (expected count)

    int found_count = 0;                 // how many hidden strings are already identified

    // Time control (computation only; I/O cost dominates on the judge side)
    constexpr long long TIME_LIMIT_MS = 4900; // leave some margin under 5s
    constexpr int BASE_SWEEPS = 3;            // accuracy knob (increase if you have time)
    auto t0 = chrono::steady_clock::now();

    auto elapsed_ms = [&]()->long long{
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
    };

    auto normalize = [&](int n_rem){
        double tot = 0.0;
        for(int i: alive_list) tot += w[i];
        if(tot <= 0.0){
            for(int i: alive_list) w[i] = 1.0;
            tot = (double)alive_list.size();
        }
        double sc = (double)n_rem / tot;
        for(int i: alive_list) w[i] *= sc;
    };

    auto prune_with_mask = [&](int qid, uint32_t maskBits){
        // Remove i from alive_list if cats[qid][i] is in maskBits
        vector<int> new_alive;
        new_alive.reserve(alive_list.size());
        const auto &cat = cats[qid];
        for(int i: alive_list){
            if(!alive[i]) continue;
            int c = cat[i];
            if(maskBits & (1u<<c)){
                alive[i] = false;
                w[i] = 0.0;
            }else{
                new_alive.push_back(i);
            }
        }
        alive_list.swap(new_alive);
    };

    auto rake = [&](int n_rem, int sweeps){
        if(alive_list.empty()) return;
        if(queries.empty()){
            for(int i: alive_list) w[i] = 1.0;
            normalize(n_rem);
            return;
        }
        for(int it=0; it<sweeps; it++){
            normalize(n_rem);
            for(int q=0; q<(int)queries.size(); q++){
                double sum[K];
                for(int r=0;r<K;r++) sum[r]=0.0;
                const auto &cat = cats[q];
                for(int i: alive_list) sum[cat[i]] += w[i];

                double factor[K];
                for(int r=0;r<K;r++){
                    if(sum[r] > 0.0) factor[r] = (double)cnt[q][r] / sum[r];
                    else factor[r] = (cnt[q][r] == 0 ? 1.0 : 0.0);
                }
                for(int i: alive_list) w[i] *= factor[cat[i]];
            }
        }
        normalize(n_rem);
    };

    // ------------------------------
    // Main interaction loop
    // ------------------------------
    while(true){
        if(found_count >= 30) return 0; // just in case

        if(alive_list.empty()){
            // Extremely unlikely unless something went wrong.
            // Fall back to "ask everything not asked".
            for(int i=0;i<N;i++){
                if(asked[i]) continue;
                cout.write(all[i].s.data(), 5);
                cout << '\n' << flush;
                bool bad=false;
                int c50=0;
                for(int k=0;k<30;k++){
                    int h,b; cin>>h>>b;
                    if(!cin) return 0;
                    if(h==-1 && b==-1) bad=true;
                    if(h==5 && b==0) c50++;
                }
                if(bad || c50==30) return 0;
            }
            return 0;
        }

        const int n_rem = 30 - found_count;

        int qidx = -1;
        if((int)alive_list.size() == n_rem){
            // Only n_rem candidates are possible -> all must exist with probability 1.
            qidx = alive_list[0];
        }else{
            long long rem = TIME_LIMIT_MS - elapsed_ms();
            int sweeps = BASE_SWEEPS;
            if(rem < 200) sweeps = 0;
            else if(rem < 400) sweeps = min(sweeps, 1);
            else if(rem < 800) sweeps = min(sweeps, 2);

            if(sweeps > 0) rake(n_rem, sweeps);
            else normalize(n_rem);

            qidx = alive_list[0];
            double best = w[qidx];
            for(int i: alive_list){
                if(w[i] > best){ best = w[i]; qidx = i; }
            }
            if(best <= 0.0){
                // fallback: pick something to make progress
                qidx = alive_list[(uint64_t)elapsed_ms() % alive_list.size()];
            }
        }

        // Ask qidx
        asked[qidx] = true;
        // (We mark alive=false now; it will be physically removed by prune right after we add this query.)
        alive[qidx] = false;
        w[qidx] = 0.0;

        cout.write(all[qidx].s.data(), 5);
        cout << '\n' << flush; // required

        // Read judge response (30 lines)
        array<int,K> hist{};
        hist.fill(0);
        bool bad = false;
        int c50 = 0;
        for(int k=0;k<30;k++){
            int h,b; cin >> h >> b;
            if(!cin) return 0;
            if(h==-1 && b==-1) bad = true;
            if(!bad){
                int id = HB_ID[h][b];
                if(id >= 0) hist[id]++;
                if(h==5 && b==0) c50++;
            }
        }
        if(bad) return 0;
        if(c50 == 30) return 0; // all solved

        int prev_found = found_count;
        bool new_found = (c50 > prev_found);
        found_count = c50;

        // residual histogram for the currently unknown set (after this query)
        array<int,K> resid = hist;
        resid[ID_50] -= found_count;

        // Store this query
        queries.push_back(qidx);
        cnt.push_back(resid);
        cats.emplace_back(N);
        int qid = (int)queries.size() - 1;
        for(int i=0;i<N;i++) cats[qid][i] = (uint8_t)hb(qidx, i);

        // Build zero mask and prune
        uint32_t z = 0;
        for(int r=0;r<K;r++) if(cnt[qid][r] == 0) z |= (1u<<r);
        zeroMask.push_back(z);
        prune_with_mask(qid, z);

        // If we found a new code, peel it from all previous histograms.
        if(new_found){
            int sidx = qidx;
            for(int q=0;q<qid;q++){
                int cid = hb(sidx, queries[q]);
                cnt[q][cid]--;
                if(cnt[q][cid] == 0){
                    uint32_t bit = (1u<<cid);
                    if(!(zeroMask[q] & bit)){
                        zeroMask[q] |= bit;
                        prune_with_mask(q, bit);
                    }
                }
            }
        }
    }
}