結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

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

inline int get_hb_val(const Guess& a, const Guess& b) {
    int h = (a.d[0] == b.d[0]) + (a.d[1] == b.d[1]) + (a.d[2] == b.d[2]) + (a.d[3] == b.d[3]) + (a.d[4] == b.d[4]);
    int bl = __builtin_popcount(a.mask & b.mask) - h;
    return h * 6 + bl;
}

Guess all_guesses[30240];
double log_table[31];
int candidates[30240];
int cand_size = 0;
bool is_found[30240];

void init_data() {
    int idx = 0;
    for (int i = 0; i <= 99999; i++) {
        int tmp = i;
        int mask = 0;
        unsigned char d[5];
        bool ok = true;
        for (int j = 4; j >= 0; j--) {
            d[j] = tmp % 10;
            if ((mask >> d[j]) & 1) { ok = false; break; }
            mask |= (1 << d[j]);
            tmp /= 10;
        }
        if (ok) {
            all_guesses[idx].mask = mask;
            for(int k=0; k<5; k++) all_guesses[idx].d[k] = d[k];
            candidates[idx] = idx;
            idx++;
        }
    }
    cand_size = idx;
    memset(is_found, 0, sizeof(is_found));
    
    for (int i = 1; i <= 30; i++) log_table[i] = log2(i);
}

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

    init_data();

    int found_count = 0;
    mt19937 rng(12345);
    
    auto start_time = chrono::steady_clock::now();

    while (found_count < 30) {
        int best_q = -1;
        
        if (found_count == 0 && cand_size == 30240) {
            for(int i=0; i<30240; i++) {
                if (all_guesses[i].d[0]==0 && all_guesses[i].d[1]==1 && all_guesses[i].d[2]==2 && 
                    all_guesses[i].d[3]==3 && all_guesses[i].d[4]==4) {
                    best_q = i;
                    break;
                }
            }
        } else if (cand_size <= 30 - found_count) {
             best_q = candidates[0];
        } else {
            double max_entropy = -1.0;
            int sample_size = (cand_size > 2000) ? 120 : cand_size;
            
            int attempt_limit = (cand_size > 5000) ? 200 : (cand_size > 1000 ? 500 : 30240); 
            
            for (int k = 0; k < attempt_limit; k++) {
                int q_idx;
                if (k < cand_size) q_idx = candidates[k]; 
                else q_idx = rng() % 30240;

                if (is_found[q_idx]) continue;

                int counts[31] = {0};
                
                if (cand_size <= sample_size) {
                    for (int i = 0; i < cand_size; i++) {
                        counts[get_hb_val(all_guesses[q_idx], all_guesses[candidates[i]])]++;
                    }
                } else {
                    for (int i = 0; i < sample_size; i++) {
                        int r = rng() % cand_size;
                        counts[get_hb_val(all_guesses[q_idx], all_guesses[candidates[r]])]++;
                    }
                }

                double entropy = 0;
                for (int i = 0; i < 31; i++) {
                    if (counts[i] > 0) {
                        double p = (double)counts[i] / (cand_size <= sample_size ? cand_size : sample_size);
                        entropy -= p * log2(p);
                    }
                }

                if (entropy > max_entropy) {
                    max_entropy = entropy;
                    best_q = q_idx;
                }
                
                if (chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start_time).count() > 4800) {
                     break; 
                }
            }
        }
        
        if (best_q == -1) best_q = candidates[0];

        for (int i = 0; i < 5; i++) cout << (int)all_guesses[best_q].d[i];
        cout << endl;

        int res_counts[31] = {0};
        int h5b0 = 0;
        for (int i = 0; i < 30; i++) {
            int h, b;
            cin >> h >> b;
            int val = h * 6 + b;
            res_counts[val]++;
            if (val == 30) h5b0++;
        }

        if (h5b0 == 30) break;

        res_counts[30] -= found_count;
        
        bool new_hit = false;
        if (res_counts[30] > 0) {
            new_hit = true;
            res_counts[30]--; 
            found_count++;
            is_found[best_q] = true;
            
            int write_idx = 0;
            for(int i=0; i<cand_size; i++){
                if(candidates[i] != best_q) {
                    candidates[write_idx++] = candidates[i];
                }
            }
            cand_size = write_idx;
        }

        int next_size = 0;
        int temp_next[30240];
        
        for (int i = 0; i < cand_size; i++) {
            int c_idx = candidates[i];
            int val = get_hb_val(all_guesses[best_q], all_guesses[c_idx]);
            if (res_counts[val] > 0) {
                temp_next[next_size++] = c_idx;
            }
        }
        
        for(int i=0; i<next_size; i++) candidates[i] = temp_next[i];
        cand_size = next_size;
    }

    return 0;
}
0