結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2025-12-15 20:24:59 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 841 ms / 5,000 ms |
| コード長 | 21,925 bytes |
| 記録 | |
| コンパイル時間 | 5,477 ms |
| コンパイル使用メモリ | 337,240 KB |
| 実行使用メモリ | 26,228 KB |
| スコア | 9,995,747 |
| 平均クエリ数 | 42.53 |
| 最終ジャッジ日時 | 2025-12-25 01:48:43 |
| 合計ジャッジ時間 | 80,075 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// =============================================================
// Tunable parameters
// PRESET = 0: FAST (時間優先、そこそこスコア)
// PRESET = 1: BALANCED (推奨：5sに収めつつスコアも狙う)
// PRESET = 2: AGGRESSIVE (手数優先：重いので環境によってはTLEしやすい)
// =============================================================
// #ifndef PRESET
#define PRESET 2
// #endif
struct Params {
// wall-clock guard (ms). 5s制限なので少し余裕を取る
static constexpr int SOFT_TIME_LIMIT_MS = 4900;
// ---- Core inference (IPF) ----
#if PRESET == 0
static constexpr int IPF_ITERS = 5;
static constexpr int IPF_RECENT_RECORDS = 22; // 直近だけ使う(速い)
#elif PRESET == 1
static constexpr int IPF_ITERS = 7;
static constexpr int IPF_RECENT_RECORDS = 36;
#else
static constexpr int IPF_ITERS = 10;
static constexpr int IPF_RECENT_RECORDS = 60; // ほぼ全履歴
#endif
// 当たりに行く閾値（IPFの重み w は「その候補が秘密集合に含まれる確率」近似）
#if PRESET == 0
static constexpr double HIT_THRESHOLD = 0.78;
#elif PRESET == 1
static constexpr double HIT_THRESHOLD = 0.72;
#else
static constexpr double HIT_THRESHOLD = 0.68;
#endif
// ---- Information query search (expensive, but reduces misses early) ----
#if PRESET == 0
static constexpr bool ENABLE_INFO_QUERY = true;
static constexpr int INFO_POOL_TOP = 60;
static constexpr int INFO_POOL_RAND = 140;
static constexpr int INFO_SAMPLE_CAND = 1600;
#elif PRESET == 1
static constexpr bool ENABLE_INFO_QUERY = true;
static constexpr int INFO_POOL_TOP = 90;
static constexpr int INFO_POOL_RAND = 220;
static constexpr int INFO_SAMPLE_CAND = 2600;
#else
static constexpr bool ENABLE_INFO_QUERY = true;
static constexpr int INFO_POOL_TOP = 140;
static constexpr int INFO_POOL_RAND = 420;
static constexpr int INFO_SAMPLE_CAND = 4200;
#endif
// 情報質問の評価関数の係数
static constexpr double SCORE_COEF_ENT = 1.00; // エントロピー（情報量）
static constexpr double SCORE_COEF_ELIM = 0.08; // 0バケット発生による候補削減期待
static constexpr double SCORE_COEF_HIT = 0.65; // 当たり確率
// ---- Endgame exact-ish solver (can be heavy) ----
#if PRESET == 2
static constexpr bool ENABLE_ENDGAME_SOLVER = true;
static constexpr int ENDGAME_M_MAX = 7;
static constexpr int ENDGAME_CAND_MAX = 1400;
#else
static constexpr bool ENABLE_ENDGAME_SOLVER = false;
static constexpr int ENDGAME_M_MAX = 0;
static constexpr int ENDGAME_CAND_MAX = 0;
#endif
// ---- Optional fixed probes (early constraints) ----
// 0なら無効。固定で数手使う代わりに序盤の絞り込みを強める。
#if PRESET == 2
static constexpr int PROBE_STEPS = 2; // 01234, 56789 を先に打つ
#else
static constexpr int PROBE_STEPS = 0;
#endif
// ---- Auto throttle by elapsed time ----
static constexpr bool AUTO_THROTTLE = true;
};
// =============================================================
// Problem constants
// =============================================================
static constexpr int L = 5;
static constexpr int DIG = 10;
static constexpr int T = 21; // (H,B) with H+B<=5
static constexpr int M_TOTAL = 30;
static int IDX[L+1][L+1];
struct Stopwatch {
chrono::steady_clock::time_point st = chrono::steady_clock::now();
inline int ms() const {
return (int)chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - st).count();
}
};
struct Code {
array<uint8_t, L> d{};
uint16_t mask = 0;
string s;
};
static vector<Code> generate_all_codes() {
vector<Code> all;
all.reserve(30240);
array<uint8_t, L> cur{};
string buf(L, '0');
function<void(int, uint16_t)> dfs = [&](int pos, uint16_t mask) {
if (pos == L) {
Code c;
c.d = cur;
c.mask = mask;
c.s = buf;
all.push_back(std::move(c));
return;
}
for (int dig = 0; dig < DIG; dig++) {
if (mask & (1u << dig)) continue;
cur[pos] = (uint8_t)dig;
buf[pos] = char('0' + dig);
dfs(pos + 1, (uint16_t)(mask | (1u << dig)));
}
};
dfs(0, 0);
return all;
}
static inline uint8_t type_idx(const Code &a, const Code &q) {
int hit = 0;
for (int i = 0; i < L; i++) hit += (a.d[i] == q.d[i]);
int common = __builtin_popcount((unsigned)(a.mask & q.mask));
int blow = common - hit;
return (uint8_t)IDX[hit][blow];
}
struct Solver {
const vector<Code> &codes;
const int N;
Stopwatch sw;
vector<char> possible; // まだ秘密であり得る
vector<char> asked; // 質問済み
vector<char> found; // 発見済み(=秘密だと確定して当てた)
int foundCount = 0;
struct Record {
int qid;
array<int, T> need; // 残り秘密のヒストグラム（(5,0)除外済み）
array<int, T> aliveCnt; // possible のうち、この型に入る候補数
};
vector<Record> recs;
vector<vector<uint8_t>> typeCache; // typeCache[r][cid] = type(code[cid], query[r])
vector<int> planned; // endgameで一意解が出たときの回収リスト
// probe queries (by string)
vector<int> probeQids;
explicit Solver(const vector<Code>& codes_)
: codes(codes_), N((int)codes_.size()),
possible(N, 1), asked(N, 0), found(N, 0) {
// Prepare probe IDs if enabled
if (Params::PROBE_STEPS > 0) {
unordered_map<string,int> mp;
mp.reserve(N*2);
for (int i=0;i<N;i++) mp[codes[i].s]=i;
vector<string> probes = {"01234", "56789", "02468", "13579"};
for (auto &s: probes) if (mp.count(s)) probeQids.push_back(mp[s]);
}
}
inline bool time_low() const {
return sw.ms() >= Params::SOFT_TIME_LIMIT_MS;
}
inline double time_scale() const {
if (!Params::AUTO_THROTTLE) return 1.0;
double t = (double)sw.ms() / (double)Params::SOFT_TIME_LIMIT_MS;
// 早い段階は1.0、終盤は0.35くらいまで落とす
double s = 1.0 - 0.65 * max(0.0, min(1.0, t));
return max(0.35, s);
}
void kill_candidate(int cid) {
if (!possible[cid]) return;
possible[cid] = 0;
for (int r = 0; r < (int)recs.size(); r++) {
int t = typeCache[r][cid];
recs[r].aliveCnt[t]--;
}
}
void recompute_aliveCnt(int r) {
recs[r].aliveCnt.fill(0);
for (int cid = 0; cid < N; cid++) {
if (!possible[cid]) continue;
if (asked[cid]) continue;
recs[r].aliveCnt[typeCache[r][cid]]++;
}
}
void eliminate_bucket(int r, int t) {
// need[t]==0 -> bucket 全消し
auto &row = typeCache[r];
for (int cid = 0; cid < N; cid++) {
if (!possible[cid] || asked[cid]) continue;
if (row[cid] == t) kill_candidate(cid);
}
}
void apply_found_secret_to_past(int sid) {
// 新しく見つかった秘密 sid は、過去の記録では(5,0)になっていた分だけ
// 本来の型を1つ消す必要がある
for (int r = 0; r < (int)recs.size(); r++) {
int t = typeCache[r][sid];
if (recs[r].need[t] > 0) {
recs[r].need[t]--;
if (recs[r].need[t] == 0) eliminate_bucket(r, t);
}
}
}
void add_record(int qid, const array<int,T> &hist) {
Record rec;
rec.qid = qid;
rec.need = hist;
rec.aliveCnt.fill(0);
vector<uint8_t> row(N);
for (int cid = 0; cid < N; cid++) row[cid] = type_idx(codes[cid], codes[qid]);
typeCache.push_back(std::move(row));
recs.push_back(std::move(rec));
int r = (int)recs.size() - 1;
recompute_aliveCnt(r);
// 0 bucket elimination (exact)
for (int t = 0; t < T; t++) {
if (recs[r].need[t] == 0) eliminate_bucket(r, t);
}
}
void observe(int qid, const vector<pair<int,int>> &hb) {
// (-1,-1) が来たら即終了
if (hb[0].first == -1 && hb[0].second == -1) exit(0);
int cnt50 = 0;
array<int,T> hist{};
hist.fill(0);
for (auto &p: hb) {
if (p.first == 5 && p.second == 0) cnt50++;
else hist[IDX[p.first][p.second]]++;
}
asked[qid] = 1;
// qid 自体は秘密でも秘密でなくても「未発見候補」ではない
kill_candidate(qid);
if (cnt50 == foundCount + 1) {
foundCount++;
found[qid] = 1;
apply_found_secret_to_past(qid);
}
// この hist は「現在の未発見集合」に対する分布（合計は 30-cnt50）
add_record(qid, hist);
}
int find_forced_hit() {
// need[t] == aliveCnt[t] > 0 なら、そのバケットの候補は全て秘密
for (int r = 0; r < (int)recs.size(); r++) {
for (int t = 0; t < T; t++) {
int need = recs[r].need[t];
int alive = recs[r].aliveCnt[t];
if (need > 0 && alive == need) {
auto &row = typeCache[r];
for (int cid = 0; cid < N; cid++) {
if (!possible[cid] || asked[cid]) continue;
if (row[cid] == t) return cid; // guaranteed hit
}
}
}
}
return -1;
}
// (optional) endgame: try to find unique remaining set (very limited)
bool try_endgame_unique() {
if (!Params::ENABLE_ENDGAME_SOLVER) return false;
int M = M_TOTAL - foundCount;
if (M > Params::ENDGAME_M_MAX) return false;
vector<int> cand;
cand.reserve(N);
for (int cid = 0; cid < N; cid++) if (possible[cid] && !asked[cid]) cand.push_back(cid);
if ((int)cand.size() > Params::ENDGAME_CAND_MAX) return false;
if (recs.empty()) return false;
int R = (int)recs.size();
// choose record with minimal branching (rough)
int bestR = 0;
double best = 1e300;
for (int r = 0; r < R; r++) {
array<int,T> sz{};
sz.fill(0);
for (int cid: cand) sz[typeCache[r][cid]]++;
double sc = 1.0;
for (int t=0;t<T;t++){
int k = recs[r].need[t];
if (!k) continue;
sc *= pow((double)max(1, sz[t]), (double)k);
if (sc > best) break;
}
if (sc < best) { best=sc; bestR=r; }
}
vector<vector<int>> bucket(T);
bucket.assign(T, {});
for (int i=0;i<(int)cand.size();i++){
bucket[typeCache[bestR][cand[i]]].push_back(i);
}
vector<array<int,T>> need(R);
for (int r=0;r<R;r++) need[r]=recs[r].need;
vector<char> used(cand.size(), 0);
vector<int> cur;
vector<vector<int>> sols;
vector<int> types;
for (int t=0;t<T;t++) if (need[bestR][t]>0) types.push_back(t);
// recursion with time guard
function<void(int,int,int)> dfs = [&](int ti, int pickLeft, int start) {
if ((int)sols.size() >= 2) return;
if (time_low()) return;
if (ti == (int)types.size()) {
if ((int)cur.size() != M) return;
for (int r=0;r<R;r++) for (int t=0;t<T;t++) if (need[r][t]!=0) return;
sols.push_back(cur);
return;
}
int t = types[ti];
if (pickLeft < 0) pickLeft = need[bestR][t];
if (pickLeft == 0) { dfs(ti+1, -1, 0); return; }
auto &vec = bucket[t];
for (int p=start;p<(int)vec.size();p++){
int idx = vec[p];
if (used[idx]) continue;
int cid = cand[idx];
used[idx]=1;
cur.push_back(cid);
bool ok=true;
for (int r=0;r<R;r++){
int tt = typeCache[r][cid];
if (--need[r][tt] < 0) ok=false;
}
if (ok) dfs(ti, pickLeft-1, p+1);
for (int r=0;r<R;r++){
int tt = typeCache[r][cid];
need[r][tt]++;
}
cur.pop_back();
used[idx]=0;
if ((int)sols.size() >= 2) return;
if (time_low()) return;
}
};
dfs(0, -1, 0);
if ((int)sols.size() == 1) {
planned = std::move(sols[0]);
return true;
}
planned.clear();
return false;
}
// IPF on candidates (recent records only)
void ipf_weights(const vector<int>& cand, vector<double>& w, vector<double>& wById) {
int M = M_TOTAL - foundCount;
int K = (int)cand.size();
w.assign(K, (double)M / (double)K);
wById.assign(N, 0.0);
int R = (int)recs.size();
int useR = min(R, Params::IPF_RECENT_RECORDS);
int rs = R - useR;
int iters = Params::IPF_ITERS;
double sc = time_scale();
iters = max(2, (int)floor(iters * sc));
array<double, T> sum;
array<double, T> fac;
for (int it = 0; it < iters; it++) {
for (int r = rs; r < R; r++) {
sum.fill(0.0);
auto &row = typeCache[r];
for (int i = 0; i < K; i++) {
sum[row[cand[i]]] += w[i];
}
for (int t = 0; t < T; t++) {
if (recs[r].need[t] == 0 || sum[t] <= 0.0) fac[t] = 0.0;
else fac[t] = (double)recs[r].need[t] / sum[t];
}
for (int i = 0; i < K; i++) {
w[i] *= fac[typeCache[r][cand[i]]];
}
}
// normalize sum(w)=M
double tot = 0.0;
for (double x : w) tot += x;
if (tot <= 0.0) break;
double mul = (double)M / tot;
for (double &x : w) x *= mul;
if (time_low()) break;
}
for (int i = 0; i < K; i++) wById[cand[i]] = w[i];
}
int choose_info_query(const vector<int>& cand, const vector<double>& w, const vector<double>& wById) {
// Build query pool: top weighted candidates + random codes
int K = (int)cand.size();
double sc = time_scale();
int poolTop = (int)floor(Params::INFO_POOL_TOP * sc);
int poolRand = (int)floor(Params::INFO_POOL_RAND * sc);
poolTop = max(20, poolTop);
poolRand = max(40, poolRand);
int sampleN = (int)floor(Params::INFO_SAMPLE_CAND * sc);
sampleN = max(500, sampleN);
sampleN = min(sampleN, K);
// top indices for poolTop / sampleN
vector<int> idx(K);
iota(idx.begin(), idx.end(), 0);
int wantTop = min(poolTop, K);
nth_element(idx.begin(), idx.begin() + wantTop, idx.end(),
[&](int a, int b){ return w[a] > w[b]; });
idx.resize(wantTop);
sort(idx.begin(), idx.end(), [&](int a, int b){ return w[a] > w[b]; });
vector<char> inPool(N, 0);
vector<int> pool;
pool.reserve(wantTop + poolRand);
for (int j : idx) {
int qid = cand[j];
if (asked[qid]) continue;
if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
}
static mt19937 rng(1234567);
uniform_int_distribution<int> uni(0, N-1);
while ((int)pool.size() < wantTop + poolRand && !time_low()) {
int qid = uni(rng);
if (asked[qid]) continue;
if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
}
if (pool.empty()) return cand[idx[0]];
// sample candidates (mostly top, plus random tail)
vector<int> sidx;
sidx.reserve(sampleN);
int topPart = min(sampleN, (int)floor(sampleN * 0.70));
// reuse idx for bigger topPart if needed
if (topPart > wantTop) {
vector<int> idx2(K);
iota(idx2.begin(), idx2.end(), 0);
nth_element(idx2.begin(), idx2.begin() + topPart, idx2.end(),
[&](int a, int b){ return w[a] > w[b]; });
idx2.resize(topPart);
sort(idx2.begin(), idx2.end(), [&](int a, int b){ return w[a] > w[b]; });
for (int j : idx2) sidx.push_back(j);
} else {
for (int i = 0; i < topPart; i++) sidx.push_back(idx[i]);
}
uniform_int_distribution<int> uniK(0, K-1);
while ((int)sidx.size() < sampleN && !time_low()) {
sidx.push_back(uniK(rng));
}
// scoring
int M = M_TOTAL - foundCount;
vector<double> mass(T);
vector<int> cnt(T);
int bestQ = pool[0];
double bestScore = -1e300;
for (int qid : pool) {
fill(mass.begin(), mass.end(), 0.0);
fill(cnt.begin(), cnt.end(), 0);
double massTot = 0.0;
for (int j : sidx) {
int sid = cand[j];
double ww = w[j];
uint8_t t = type_idx(codes[sid], codes[qid]);
mass[t] += ww;
cnt[t] += 1;
massTot += ww;
}
if (massTot <= 0.0) continue;
// entropy
double ent = 0.0;
for (int t = 0; t < T; t++) {
if (mass[t] <= 0.0) continue;
double p = mass[t] / massTot;
ent -= p * log(p);
}
// expected elimination (rough)
double expElim = 0.0;
for (int t = 0; t < T; t++) {
if (mass[t] <= 0.0) continue;
double p = mass[t] / massTot;
double q = max(1e-12, 1.0 - p);
double probZero = exp((double)M * log(q)); // approx (1-p)^M
double estBucket = (double)cnt[t] * ((double)K / (double)sampleN);
expElim += estBucket * probZero;
}
double hitP = wById[qid]; // 0 if not candidate
double score = Params::SCORE_COEF_ENT * ent
+ Params::SCORE_COEF_ELIM * (expElim / (double)max(1, K))
+ Params::SCORE_COEF_HIT * hitP;
if (score > bestScore) {
bestScore = score;
bestQ = qid;
}
if (time_low()) break;
}
return bestQ;
}
int choose_next() {
if (foundCount >= M_TOTAL) return -1;
// planned（終盤一意解）
if (!planned.empty()) {
int q = planned.back();
planned.pop_back();
return q;
}
// probes
if (Params::PROBE_STEPS > 0 && (int)recs.size() < Params::PROBE_STEPS) {
int pi = (int)recs.size();
if (pi < (int)probeQids.size() && !asked[probeQids[pi]]) return probeQids[pi];
}
// forced hit
int forced = find_forced_hit();
if (forced != -1) return forced;
// endgame attempt
if (Params::ENABLE_ENDGAME_SOLVER) {
int M = M_TOTAL - foundCount;
if (M <= Params::ENDGAME_M_MAX && try_endgame_unique() && !planned.empty()) {
int q = planned.back();
planned.pop_back();
return q;
}
}
// first query (lex smallest) is "01234"
if (recs.empty()) return 0;
// candidates
vector<int> cand;
cand.reserve(N);
for (int cid = 0; cid < N; cid++) if (possible[cid] && !asked[cid]) cand.push_back(cid);
if (cand.empty()) {
for (int cid = 0; cid < N; cid++) if (!asked[cid]) return cid;
return 0;
}
// IPF weights
vector<double> w, wById;
ipf_weights(cand, w, wById);
// best hit candidate
int bestI = 0;
for (int i = 1; i < (int)cand.size(); i++) if (w[i] > w[bestI]) bestI = i;
int bestCid = cand[bestI];
double bestW = w[bestI];
// If confident enough, just hit
if (bestW >= Params::HIT_THRESHOLD || !Params::ENABLE_INFO_QUERY || time_low()) {
return bestCid;
}
// Otherwise do info-query search (bounded by parameters)
return choose_info_query(cand, w, wById);
}
};
int main() {
// build IDX (H,B) -> 0..20
int id = 0;
for (int h = 0; h <= L; h++) {
for (int b = 0; b <= L - h; b++) IDX[h][b] = id++;
}
vector<Code> codes = generate_all_codes();
Solver solver(codes);
while (true) {
int qid = solver.choose_next();
if (qid < 0) return 0;
// output & flush (必須) :contentReference[oaicite:5]{index=5}
cout << codes[qid].s << '\n' << flush;
// read 30 pairs (必ず最後まで読む) :contentReference[oaicite:6]{index=6}
vector<pair<int,int>> hb(M_TOTAL);
for (int i = 0; i < M_TOTAL; i++) {
if (!(cin >> hb[i].first >> hb[i].second)) return 0;
}
// termination: since answers are lex-sorted, (H0,B0)=(5,0) iff all are (5,0)
// so all secrets are found -> exit :contentReference[oaicite:7]{index=7}
if (hb[0].first == 5 && hb[0].second == 0) return 0;
// invalid interaction -> exit :contentReference[oaicite:8]{index=8}
if (hb[0].first == -1 && hb[0].second == -1) return 0;
solver.observe(qid, hb);
}
}