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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-16 01:38:02
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 60 ms / 5,000 ms
• コード長: 6,690 bytes
• コンパイル時間: 3,352 ms
• コンパイル使用メモリ: 286,696 KB
• 実行使用メモリ: 26,228 KB
• スコア: 9,956,212
• 平均クエリ数: 437.88
• 最終ジャッジ日時: 2025-12-25 01:55:34
• 合計ジャッジ時間: 12,489 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

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

ソースコード

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

static const int M = 30;

struct Resp {
    array<int, M> h;
    array<int, M> b;
};

static inline string digits_to_string(const array<int,5>& a){
    string s;
    s.reserve(5);
    for(int i=0;i<5;i++) s.push_back(char('0'+a[i]));
    return s;
}

static Resp ask(const string& q){
    cout << q << "\n";
    cout.flush(); // flush必須 :contentReference[oaicite:12]{index=12}

    Resp r;
    for(int i=0;i<M;i++){
        if(!(cin >> r.h[i] >> r.b[i])) {
            // 入力が途切れたら終了
            exit(0);
        }
    }
    // 不正なやり取り (-1,-1) が返る場合がある :contentReference[oaicite:13]{index=13}
    if(r.h[0]==-1 && r.b[0]==-1) exit(0);

    // (H0,B0)=(5,0) なら全て当て終わり :contentReference[oaicite:14]{index=14}
    if(r.h[0]==5) exit(0);

    return r;
}

// そのクエリで「数字集合が完全一致しているが未解決」な秘密の個数
// = (h+b==5 かつ h!=5) の本数
static int count_sum5_nonhit(const Resp& r){
    int c=0;
    for(int i=0;i<M;i++){
        int h=r.h[i], b=r.b[i];
        if(h!=5 && h+b==5) c++;
    }
    return c;
}

// 「count==1 の数字集合 D」について、その唯一の未解決秘密の (hit) を読む。
// 返り値:
//   - 0..3: その秘密の固定点数 (h)
//   - 5:    既に当たった（(5,0) になっている＝このクエリで当てた など）
// 前提：このクエリの数字集合が D で、D 内の未解決秘密がちょうど1個
static int read_h_for_unique_secret_in_block(const Resp& r){
    // 未解決の (h+b=5, h!=5) を探す
    int found = -1;
    for(int i=0;i<M;i++){
        int h=r.h[i], b=r.b[i];
        if(h!=5 && h+b==5){
            if(found!=-1){
                // ここに来るのは前提違反（ブロック内が1個じゃない）
                // 安全のため諦める
                return -2;
            }
            found = h;
        }
    }
    if(found==-1){
        // 未解決が0個：= その秘密は (5,0) になっている（当てた）
        return 5;
    }
    return found;
}

static inline int fixed_points(const array<int,5>& a, const array<int,5>& g){
    int h=0;
    for(int i=0;i<5;i++) if(a[i]==g[i]) h++;
    return h;
}

// 候補集合 cand（配列の集合）の中から minimax で次の guess を選ぶ
static array<int,5> choose_minimax_guess(const vector<array<int,5>>& cand){
    // 返答 h は 0,1,2,3,5（4は起こらない）を想定
    // h=5 は当たりなので worst-case の評価から除外してよい
    int bestWorst = INT_MAX;
    array<int,5> best = cand[0];

    for(const auto& g : cand){
        int cnt[6] = {0,0,0,0,0,0};
        for(const auto& a : cand){
            int h = fixed_points(a,g);
            // h==4 は起こらない（4固定点なら残りも一致して5になる）
            cnt[h]++;
        }
        int worst = max({cnt[0], cnt[1], cnt[2], cnt[3]});
        if(worst < bestWorst){
            bestWorst = worst;
            best = g;
        }
    }
    return best;
}

// ブロック D（5種類の数字）に属する未解決秘密が「ちょうど1個」のとき、最悪6手でそれを当てる
static void solve_unique_block(const array<int,5>& D){
    // 候補：D の全 5! = 120 通り
    array<int,5> p = D;
    vector<array<int,5>> cand;
    sort(p.begin(), p.end());
    do {
        cand.push_back(p);
    } while(next_permutation(p.begin(), p.end()));

    while(true){
        array<int,5> g = choose_minimax_guess(cand);
        string q = digits_to_string(g);
        Resp r = ask(q);

        int h = read_h_for_unique_secret_in_block(r);
        if(h==5){
            // 当たった
            return;
        }
        if(h<0){
            // 想定外（ブロック内が1個じゃない等）
            return;
        }
        // 候補を絞る
        vector<array<int,5>> nxt;
        nxt.reserve(cand.size());
        for(const auto& a : cand){
            if(fixed_points(a,g)==h) nxt.push_back(a);
        }
        cand.swap(nxt);
    }
}

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

    // 252 個の数字集合（0..9 から 5 個選ぶ）
    vector<array<int,5>> blocks;
    blocks.reserve(252);
    for(int a=0;a<10;a++)
    for(int b=a+1;b<10;b++)
    for(int c=b+1;c<10;c++)
    for(int d=c+1;d<10;d++)
    for(int e=d+1;e<10;e++){
        blocks.push_back({a,b,c,d,e});
    }

    // 各ブロックに属する未解決秘密数（(h+b=5, h!=5) 本数）
    vector<int> blockCnt(blocks.size(), -1);

    bool firstHitAccelerated = false;

    // まず 252 ブロックを1回ずつスキャンする（ここで count==1 が出たら即 solve して“最初の当たり”を早める）
    for(size_t i=0;i<blocks.size();i++){
        string q = digits_to_string(blocks[i]); // 代表：昇順
        Resp r = ask(q);

        int c = count_sum5_nonhit(r);
        blockCnt[i] = c;

        // “最初の当たり”高速化：
        // まだ1個も当てていない（=firstHitAccelerated==false）段階で、
        // count==1 のブロックが見つかったら、その秘密を最悪6手で当てる
        if(!firstHitAccelerated && c==1){
            solve_unique_block(blocks[i]);
            firstHitAccelerated = true;
            blockCnt[i] = 0; // その唯一の秘密を当てたので残り0
        }
    }

    // 残りを解く（単純：count==1 のブロックは minimax で順に潰す）
    // count>=2 のブロックは 120 通り総当たりで1個当てて count を減らし、最後1個になったら minimax
    for(size_t i=0;i<blocks.size();i++){
        while(blockCnt[i] > 0){
            if(blockCnt[i]==1){
                solve_unique_block(blocks[i]);
                blockCnt[i] = 0;
                continue;
            }

            // count>=2：120通りを総当たりして1個当てに行く
            array<int,5> p = blocks[i];
            sort(p.begin(), p.end());
            bool reduced = false;
            do {
                Resp r = ask(digits_to_string(p));
                int newc = count_sum5_nonhit(r);
                if(newc < blockCnt[i]){
                    blockCnt[i] = newc;
                    reduced = true;
                    break; // 1個当たった（or とにかく減った）ので抜ける
                }
            } while(next_permutation(p.begin(), p.end()));

            if(!reduced){
                // 120通りやっても減らないのはあり得ないが、安全のため抜ける
                break;
            }
        }
    }

    return 0;
}