結果

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

ソースコード

diff #
raw source code 

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

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(0);
    cin.tie(0);

    mt19937 rng(42);
    vector<G> ap;
    ap.reserve(30240);
    for (int i = 0; i <= 98765; i++) {
        int t = i, m = 0;
        uint8_t d[5];
        bool ok = true;
        for (int j = 4; j >= 0; j--) {
            d[j] = t % 10;
            if (m & (1 << d[j])) { ok = false; break; }
            m |= (1 << d[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] = d[j];
            ap.push_back(g);
        }
    }

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

    vector<bool> svd(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) ? 500 : 1500;
            int ss = min((int)can.size(), 800);
            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++) {
                int qi = (rng() % 10 < 8) ? can[rng() % can.size()] : rng() % ap.size();
                if (svd[qi]) continue;
                int f[36] = {0};
                for (int si : smp) f[get_c(ap[qi], ap[si])]++;
                double e = 0;
                for (int j = 0; j < 36; j++) if (f[j] > 0) e -= tab[f[j]];
                if (e > max_e) { max_e = 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) || h == -1) return 0;
            fr[h * 6 + b]++;
        }

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

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