結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

typedef uint8_t ResultCode;

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

vector<Guess> all_patterns;
ResultCode* hb_table = nullptr;
double log_table[30241];

void precompute() {
    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 << (int)digs[j])) { ok = false; break; }
            m |= (1 << (int)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);
        }
    }

    size_t n = all_patterns.size();
    hb_table = new ResultCode[n * n];
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            int h = 0;
            if (all_patterns[i].d[0] == all_patterns[j].d[0]) h++;
            if (all_patterns[i].d[1] == all_patterns[j].d[1]) h++;
            if (all_patterns[i].d[2] == all_patterns[j].d[2]) h++;
            if (all_patterns[i].d[3] == all_patterns[j].d[3]) h++;
            if (all_patterns[i].d[4] == all_patterns[j].d[4]) h++;
            int common = __builtin_popcount(all_patterns[i].mask & all_patterns[j].mask);
            hb_table[i * n + j] = (ResultCode)(h * 6 + (common - h));
        }
    }

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

// 1手のエントロピー計算
inline double calc_entropy(int q_idx, const vector<int>& samples, int N) {
    int counts[36] = {0};
    ResultCode* row = &hb_table[q_idx * N];
    for (int s_idx : samples) counts[row[s_idx]]++;
    double entropy = 0;
    for (int j = 0; j < 36; j++) {
        if (counts[j] > 0) entropy -= (double)counts[j] * log_table[counts[j]];
    }
    return entropy;
}

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

    precompute();
    int N = all_patterns.size();
    mt19937 rng(42);

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

    vector<bool> is_solved(N, false);
    int solved_total = 0;

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

        if (candidates.size() <= (size_t)(30 - solved_total)) {
            for (int c : candidates) if (!is_solved[c]) { best_guess_idx = c; break; }
        } 
        else if (solved_total == 0 && candidates.size() == (size_t)N) {
            // 初手 01234
            for(int i=0; i<N; ++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 && all_patterns[i].d[4]==4) { best_guess_idx = i; break; }
        } 
        else {
            // --- ビームサーチのフェーズ ---
            int sample_size = min((int)candidates.size(), 600);
            vector<int> samples;
            for(int i=0; i<sample_size; ++i) samples.push_back(candidates[rng() % candidates.size()]);

            // 1. 候補の絞り込み (1次選考)
            vector<pair<double, int>> beam;
            int search_limit = (candidates.size() > 2000) ? 800 : 2000;
            for (int i = 0; i < search_limit; i++) {
                int q_idx = (rng() % 10 < 7) ? candidates[rng() % candidates.size()] : rng() % N;
                if (is_solved[q_idx]) continue;
                double e = calc_entropy(q_idx, samples, N);
                beam.push_back({e, q_idx});
            }
            sort(beam.rbegin(), beam.rend());

            // 2. Look-ahead (2次選考)
            // 上位K個のクエリについて、次のステップの「期待される残り候補数」を最小化する
            int beam_width = (candidates.size() < 500) ? 15 : 5;
            double best_score = -1e18;

            for (int i = 0; i < min((int)beam.size(), beam_width); i++) {
                int q_idx = beam[i].second;
                int counts[36] = {0};
                ResultCode* row = &hb_table[q_idx * N];
                for (int s_idx : samples) counts[row[s_idx]]++;

                // スコア = 今回のエントロピー + 次のステップの期待情報量
                // 簡略化のため、E = Σ P(ri) * Entropy(C|ri) を計算
                double expected_future_entropy = 0;
                for (int j = 0; j < 36; j++) {
                    if (counts[j] > 1) {
                        // 次の状態の「絞り込みやすさ」を簡易評価
                        expected_future_entropy -= (double)counts[j] * log_table[counts[j]];
                    }
                }
                
                double total_score = beam[i].first + (expected_future_entropy * 0.1); // 将来への重み
                if (total_score > best_score) {
                    best_score = total_score;
                    best_guess_idx = q_idx;
                }
            }
        }

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

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

        int res_freq[36] = {0};
        for (int i = 0; i < 30; i++) {
            int h, b; cin >> h >> b;
            if (h == -1) return 0;
            res_freq[h * 6 + b]++;
        }

        if (res_freq[30] > solved_total && !is_solved[best_guess_idx]) is_solved[best_guess_idx] = true;
        solved_total = res_freq[30];
        if (solved_total == 30) break;

        vector<int> next_c;
        ResultCode* row = &hb_table[best_guess_idx * N];
        for (int c : candidates) {
            if (!is_solved[c] && res_freq[row[c]] > 0 && row[c] != 30) next_c.push_back(c);
        }
        candidates = move(next_c);
    }
    delete[] hb_table;
    return 0;
}
0