結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー LNG
提出日時 2025-12-25 14:05:02
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 192 ms / 5,000 ms
コード長 5,041 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,975 ms
コンパイル使用メモリ 194,972 KB
実行使用メモリ 26,356 KB
スコア 9,990,874
平均クエリ数 91.26
最終ジャッジ日時 2025-12-25 14:05:28
合計ジャッジ時間 25,822 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>

using namespace std;

// 結果を1バイトで保持 (H*6 + B)
typedef uint8_t Result;

struct Guess {
    int8_t d[5];
    int16_t mask;
};

// インライン展開による高速判定
inline Result get_hb(const Guess& q, const Guess& t) {
    int h = (q.d[0] == t.d[0]) + (q.d[1] == t.d[1]) + (q.d[2] == t.d[2]) + (q.d[3] == t.d[3]) + (q.d[4] == t.d[4]);
    int common = __builtin_popcount(q.mask & t.mask);
    return (Result)(h * 6 + (common - h));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto start_time = chrono::steady_clock::now();
    mt19937 rng(42);

    // 1. 全パターン生成
    vector<Guess> all_patterns;
    all_patterns.reserve(30240);
    for (int i = 0; i <= 99999; i++) {
        int tmp = i, m = 0;
        int8_t digs[5];
        bool ok = true;
        for (int j = 4; j >= 0; j--) {
            digs[j] = tmp % 10;
            if (m & (1 << digs[j])) { ok = false; break; }
            m |= (1 << digs[j]);
            tmp /= 10;
        }
        if (ok) {
            Guess g; g.mask = m;
            for (int j = 0; j < 5; j++) g.d[j] = digs[j];
            all_patterns.push_back(g);
        }
    }

    vector<int> candidates;
    for (int i = 0; i < 30240; i++) candidates.push_back(i);
    
    vector<bool> is_solved(30240, false);
    int solved_count = 0;
    int next_guess_idx = 0; // "01234"

    while (solved_count < 30) {
        // --- クエリ出力 (flush) ---
        for (int i = 0; i < 5; i++) cout << (int)all_patterns[next_guess_idx].d[i];
        cout << endl;

        // --- レスポンス取得 ---
        int res_freq[36] = {0};
        for (int i = 0; i < 30; i++) {
            int h, b;
            if (!(cin >> h >> b)) return 0;
            if (h == -1) return 0;
            res_freq[h * 6 + b]++;
        }

        if (res_freq[30] == 30) break;

        // --- ターゲット管理の更新 ---
        // このクエリ自体が正解だった場合、以降そのスロットは(5,0)を返すようになる
        if (!is_solved[next_guess_idx] && res_freq[30] > solved_count) {
            is_solved[next_guess_idx] = true;
        }
        solved_count = res_freq[30];

        // --- 厳密フィルタリング ---
        int unknown_target_res[36];
        for(int j=0; j<36; j++) unknown_target_res[j] = res_freq[j];
        
        // すでに発見済みの正解数を(5,0)の度数から引く
        int known_in_res = 0;
        for(int i=0; i<30240; i++) if(is_solved[i]) known_in_res++;
        unknown_target_res[30] -= known_in_res;

        vector<int> next_candidates;
        for (int c_idx : candidates) {
            if (is_solved[c_idx]) continue;
            Result r = get_hb(all_patterns[next_guess_idx], all_patterns[c_idx]);
            if (unknown_target_res[r] > 0) {
                next_candidates.push_back(c_idx);
            }
        }
        candidates = move(next_candidates);

        // --- 次の推論 (エントロピー最大化) ---
        if (candidates.size() <= (size_t)(30 - solved_count)) {
            for(int c : candidates) { if(!is_solved[c]) { next_guess_idx = c; break; } }
        } else {
            double max_entropy = -1.0;
            
            // 時間計測
            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast<chrono::milliseconds>(now - start_time).count();
            
            // 残り時間に応じた動的パラメータ調整
            int num_test_queries = (candidates.size() < 500) ? 500 : 150; 
            int sample_size = (candidates.size() < 1000) ? candidates.size() : 600;

            // 5秒制限のうち、4.5秒までを探索に使う
            if (elapsed > 4500) {
                next_guess_idx = candidates[0];
            } else {
                for (int i = 0; i < num_test_queries; i++) {
                    // 候補から選ぶ(80%)、全体から選ぶ(20%)
                    int q_idx = (rng() % 10 < 8) ? candidates[rng() % candidates.size()] : rng() % 30240;
                    if (is_solved[q_idx]) continue;

                    int counts[36] = {0};
                    for (int s = 0; s < sample_size; s++) {
                        int s_idx = candidates[rng() % candidates.size()];
                        counts[get_hb(all_patterns[q_idx], all_patterns[s_idx])]++;
                    }

                    double entropy = 0;
                    for (int j = 0; j < 36; j++) {
                        if (counts[j] > 0) {
                            double p = (double)counts[j] / sample_size;
                            entropy -= p * log(p);
                        }
                    }

                    if (entropy > max_entropy) {
                        max_entropy = entropy;
                        next_guess_idx = q_idx;
                    }
                }
            }
        }
    }
    return 0;
}
0