結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

typedef uint8_t RC;

struct G {
    uint8_t d[5];
    uint16_t m;
    int id;
};

inline RC get_c(const G& q, const G& 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 c = __builtin_popcount(q.m & t.m);
    return (RC)(h * 6 + (c - h));
}

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

    mt19937 rng(42);

    vector<G> ap;
    ap.reserve(30240);
    for (int i = 0; i <= 98765; i++) {
        int t = i, m = 0;
        uint8_t digs[5];
        bool ok = true;
        for (int j = 4; j >= 0; j--) {
            digs[j] = t % 10;
            if (m & (1 << digs[j])) { ok = false; break; }
            m |= (1 << digs[j]);
            t /= 10;
        }
        if (ok) {
            G g;
            g.m = (uint16_t)m;
            g.id = (int)ap.size();
            for (int j = 0; j < 5; j++) g.d[j] = digs[j];
            ap.push_back(g);
        }
    }

    vector<int> can;
    can.reserve(30240);
    for (int i = 0; i < (int)ap.size(); i++) can.push_back(i);

    vector<bool> sd(ap.size(), false);
    int sc = 0;

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

    while (sc < 30) {
        int bg = -1;

        if (can.size() <= (size_t)(30 - sc) && !can.empty()) {
            bg = can[0];
        } else if (sc == 0 && can.size() == 30240) {
            for(int i=0; i<(int)ap.size(); ++i) {
                if(ap[i].d[0]==0 && ap[i].d[1]==1 && ap[i].d[2]==2 && ap[i].d[3]==3 && ap[i].d[4]==4) {
                    bg = i; break;
                }
            }
        } else {
            double max_e = -1e18; // 初期値をより小さく
            int lim = (can.size() > 1000) ? 600 : 1800; // 候補が少ない時の探索を強化
            int ss = min((int)can.size(), 750); // サンプル数を微調整
            
            vector<int> smp;
            if (can.size() <= (size_t)ss) {
                smp = can;
            } else {
                for (int i = 0; i < ss; i++) 
                    smp.push_back(can[rng() % can.size()]);
            }

            for (int i = 0; i < lim; i++) {
                bool is_can = (rng() % 10 < 7); // 候補から選ぶ割合を7割に微調整
                int qi = (is_can && !can.empty()) ? can[rng() % can.size()] : rng() % ap.size();
                if (sd[qi]) continue;

                int cnt[36] = {0};
                for (int si : smp) {
                    cnt[get_c(ap[qi], ap[si])]++;
                }

                double cur_e = 0;
                for (int j = 0; j < 36; j++) {
                    if (cnt[j] > 0) cur_e -= tab[cnt[j]];
                }
                
                // タイブレーク：情報量が同じなら候補内(qiが正解の可能性がある手)を優先
                if (is_can) cur_e += 1e-7;

                if (cur_e > max_e) {
                    max_e = cur_e;
                    bg = qi;
                }
            }
        }

        if (bg == -1) bg = can[0];

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

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

        if (!sd[bg] && fr[30] > sc) {
            sd[bg] = true;
        }
        sc = fr[30];
        if (sc == 30) break;

        vector<int> nx;
        for (int ci : can) {
            if (sd[ci]) continue;
            RC c = get_c(ap[bg], ap[ci]);
            if (c < 30 && fr[c] > 0) {
                nx.push_back(ci);
            }
        }
        can = move(nx);
    }

    return 0;
}
0