結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー LNG
提出日時 2025-12-25 13:43:07
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 6,484 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,383 ms
コンパイル使用メモリ 202,992 KB
実行使用メモリ 34,160 KB
スコア 0
最終ジャッジ日時 2025-12-25 13:43:22
合計ジャッジ時間 15,096 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 99
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//AI改善指示

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

using namespace std;

typedef uint8_t ResultCode;

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

// ヒット・ブロー判定の高速化
inline ResultCode get_hb_code(const Guess& q, const Guess& t) {
    int h = 0;
    if (q.d[0] == t.d[0]) h++;
    if (q.d[1] == t.d[1]) h++;
    if (q.d[2] == t.d[2]) h++;
    if (q.d[3] == t.d[3]) h++;
    if (q.d[4] == t.d[4]) h++;
    int common = __builtin_popcount(q.mask & t.mask);
    return (ResultCode)(h * 6 + (common - h));
}

// 過去のクエリとその時の度数分布を記録する構造体
struct QueryHistory {
    int guess_idx;
    int freq[36];
};

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

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

    mt19937 rng(42);
    vector<Guess> all_patterns;
    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_patterns.push_back(g);
        }
    }

    vector<int> candidates;
    candidates.reserve(all_patterns.size());
    for (int i = 0; i < (int)all_patterns.size(); i++) candidates.push_back(i);
    
    vector<bool> is_solved(all_patterns.size(), false);
    vector<int> solved_indices;
    vector<QueryHistory> history;
    int solved_count = 0;

    double log_table[30241];
    for (int i = 0; i <= 30240; i++) log_table[i] = (i <= 1) ? 0 : log2((double)i);

    while (solved_count < 30) {
        int best_guess_idx = -1;

        // --- 1. 探索フェーズ ---
        if (candidates.size() <= (size_t)(30 - solved_count)) {
            for (int c : candidates) if (!is_solved[c]) { best_guess_idx = c; break; }
        } else if (history.empty()) {
            // 初手は 01234
            for(int i=0; i<(int)all_patterns.size(); ++i) {
                if(all_patterns[i].d[0]==0 && all_patterns[i].d[1]==1 && all_patterns[i].d[2]==2 && all_patterns[i].d[3]==3) {
                    best_guess_idx = i; break;
                }
            }
        } else {
            double max_entropy = -1.0;
            long long time_limit = 4800; // 4.8秒まで使用

            // 候補が少なければ全数検査、多ければサンプリング
            int sample_size = (candidates.size() < 1200) ? candidates.size() : 800;
            vector<int> samples;
            if (candidates.size() <= (size_t)sample_size) samples = candidates;
            else {
                for (int i = 0; i < sample_size; i++) samples.push_back(candidates[rng() % candidates.size()]);
            }

            int attempts = 0;
            while (get_elapsed() < time_limit) {
                attempts++;
                // 候補から選ぶ (80%) または 全体から選ぶ (20%)
                int q_idx = (rng() % 10 < 8) ? candidates[rng() % candidates.size()] : rng() % all_patterns.size();
                if (is_solved[q_idx]) continue;

                int counts[36] = {0};
                for (int s_idx : samples) counts[get_hb_code(all_patterns[q_idx], all_patterns[s_idx])]++;

                double entropy = 0;
                for (int j = 0; j < 36; j++) if (counts[j] > 0) entropy -= (double)counts[j] * log_table[counts[j]];

                if (entropy > max_entropy) {
                    max_entropy = entropy;
                    best_guess_idx = q_idx;
                }
                
                if (candidates.size() < 200 && attempts > 3000) break;
                if (attempts > 8000) break;
            }
        }

        if (best_guess_idx == -1) best_guess_idx = candidates[0];

        // --- 2. クエリ出力 ---
        for (int i = 0; i < 5; i++) cout << all_patterns[best_guess_idx].d[i];
        cout << endl;

        // --- 3. レスポンス取得 ---
        QueryHistory cur_h;
        cur_h.guess_idx = best_guess_idx;
        for (int j = 0; j < 36; j++) cur_h.freq[j] = 0;
        for (int i = 0; i < 30; i++) {
            int h, b; cin >> h >> b;
            if (h == -1) return 0;
            cur_h.freq[h * 6 + b]++;
        }
        history.push_back(cur_h);

        // --- 4. 解決状況更新 ---
        if (!is_solved[best_guess_idx] && history.back().freq[30] > (int)solved_indices.size()) {
            is_solved[best_guess_idx] = true;
            solved_indices.push_back(best_guess_idx);
        }
        solved_count = history.back().freq[30];
        if (solved_count == 30) break;

        // --- 5. 高度なフィルタリング ---
        // 解決済みターゲットの寄与を全履歴から差し引く
        vector<QueryHistory> unknown_history = history;
        for (auto &uh : unknown_history) {
            for (int s_idx : solved_indices) {
                // そのターゲットが過去のクエリに対して出したであろう結果を特定
                ResultCode c = get_hb_code(all_patterns[uh.guess_idx], all_patterns[s_idx]);
                // ジャッジは既に解決したものを(5,0)=30として返す点に注意
                // ただしuh.guess_idx自体がそのターゲットだった場合はジャッジ時に30になる
                if (uh.guess_idx == s_idx) uh.freq[30]--;
                else uh.freq[c]--;
            }
        }

        vector<int> next_candidates;
        next_candidates.reserve(candidates.size());
        for (int c_idx : candidates) {
            if (is_solved[c_idx]) continue;

            bool possible = true;
            // 過去すべてのクエリ結果と矛盾しないかチェック
            for (const auto &uh : unknown_history) {
                ResultCode code = get_hb_code(all_patterns[uh.guess_idx], all_patterns[c_idx]);
                if (uh.freq[code] <= 0) {
                    possible = false;
                    break;
                }
            }
            if (possible) next_candidates.push_back(c_idx);
        }
        candidates = move(next_candidates);
    }

    return 0;
}
0