結果

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

ソースコード

diff #
raw source code 

//生成AIによる改善案

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

using namespace std;

// 結果を1バイト(0-35)で保持しキャッシュ効率を最大化
typedef unsigned char ResultCode;

struct Guess {
    int d[5];
    int mask;
};

// 高速なHit & Blow計算
inline ResultCode get_hb_code(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 b = __builtin_popcount(q.mask & t.mask) - h;
    return (ResultCode)(h * 6 + b);
}

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

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

    // 1. 全通りの生成 (10P5 = 30240)
    vector<Guess> all;
    for (int i = 0; i <= 99999; i++) {
        int tmp = i, m = 0, 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.push_back(g);
        }
    }

    vector<int> candidates;
    for (int i = 0; i < (int)all.size(); i++) candidates.push_back(i);

    vector<bool> used_query(all.size(), false);
    int found_total = 0;
    int turn = 0;
    mt19937 rng(1337);

    // ログテーブル（log2計算を高速化）
    double log_table[30241];
    for (int i = 1; i <= 30240; i++) log_table[i] = log2(i);

    while (found_total < 30) {
        int best_idx = -1;
        long long elapsed = get_elapsed();

        if (turn == 0) {
            // 初手: 01234
            for (int i = 0; i < (int)all.size(); i++) {
                if (all[i].d[0] == 0 && all[i].d[1] == 1 && all[i].d[2] == 2 && all[i].d[3] == 3 && all[i].d[4] == 4) {
                    best_idx = i; break;
                }
            }
        } else if (candidates.size() <= (size_t)(30 - found_total)) {
            // 候補が絞り込まれたら未クエリの候補を順に解決
            for (int c : candidates) if (!used_query[c]) { best_idx = c; break; }
        } else {
            // エントロピー計算によるクエリ選択
            double max_entropy = -1.0;
            
            // 計算リソースの動的配分
            int time_limit = (elapsed < 3000) ? 600 : (elapsed < 4500 ? 300 : 100);
            auto search_start = chrono::steady_clock::now();
            
            // 候補数に応じてサンプリング数を変える
            int sample_n = (candidates.size() < 1200) ? (int)candidates.size() : 800;
            
            // クエリの評価
            for (int a = 0; a < 3000; a++) {
                if (a % 20 == 0) {
                    if (chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - search_start).count() > time_limit) break;
                }

                // クエリ候補: 候補から優先的に、時々全集合から
                int q_idx = (a < 100 && candidates.size() < 100) ? candidates[a % candidates.size()] : 
                            (rng() % 10 < 7 ? candidates[rng() % candidates.size()] : rng() % all.size());
                
                if (used_query[q_idx]) continue;

                int counts[36] = {0};
                if (candidates.size() == (size_t)sample_n) {
                    for (int c_idx : candidates) counts[get_hb_code(all[q_idx], all[c_idx])]++;
                } else {
                    for (int i = 0; i < sample_n; i++) {
                        counts[get_hb_code(all[q_idx], all[candidates[rng() % candidates.size()]])]++;
                    }
                }

                double entropy = 0;
                for (int i = 0; i < 36; i++) {
                    if (counts[i] > 0) {
                        double p = (double)counts[i] / sample_n;
                        entropy -= p * log_table[counts[i]]; // 高速化版
                    }
                }
                
                // 候補から選ぶことに微小なボーナス（正解を直接引く可能性）
                if (entropy > max_entropy) {
                    max_entropy = entropy;
                    best_idx = q_idx;
                }
            }
        }

        if (best_idx == -1) best_idx = candidates[0];
        
        // 2. クエリ出力
        used_query[best_idx] = true;
        for (int i = 0; i < 5; i++) cout << all[best_idx].d[i];
        cout << endl;

        // 3. ジャッジ回答受取
        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]++;
        }

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

        // 4. 候補のフィルタリング
        vector<int> next_c;
        next_c.reserve(candidates.size());
        for (int c_idx : candidates) {
            if (c_idx == best_idx) continue;
            
            ResultCode code = get_hb_code(all[best_idx], all[c_idx]);
            // codeが30(5H0B)以外で、その結果がジャッジから返ってきているなら残す
            if (code != 30 && res_freq[code] > 0) {
                next_c.push_back(c_idx);
            }
        }
        candidates = move(next_c);
        turn++;
        found_total = current_found;
    }

    return 0;
}
0