結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2025-12-15 23:31:13 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 504 ms / 5,000 ms |
| コード長 | 7,880 bytes |
| 記録 | |
| コンパイル時間 | 3,563 ms |
| コンパイル使用メモリ | 294,392 KB |
| 実行使用メモリ | 26,212 KB |
| スコア | 9,995,832 |
| 平均クエリ数 | 41.68 |
| 最終ジャッジ日時 | 2025-12-25 01:51:16 |
| 合計ジャッジ時間 | 49,138 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// 10P5 = 30240 candidates
static constexpr int R = 36; // id = h*6 + b
static constexpr int ID_50 = 5 * 6 + 0; // (5,0)
struct Cand {
array<uint8_t, 5> d; // digits
uint16_t mask; // 10-bit mask
string s; // "01234"
};
struct Constraint {
int q_idx; // which query
vector<uint8_t> resp; // resp[i] = id(candidate i vs q)
array<int16_t, R> cnt; // histogram for current remaining secrets
};
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// --- Generate all candidates (lexicographic, 30240) ---
vector<Cand> cand;
cand.reserve(30240);
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) if (b != a) {
for (int c = 0; c < 10; c++) if (c != a && c != b) {
for (int d = 0; d < 10; d++) if (d != a && d != b && d != c) {
for (int e = 0; e < 10; e++) if (e != a && e != b && e != c && e != d) {
Cand x;
x.d = {(uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e};
x.mask = (uint16_t)((1u<<a)|(1u<<b)|(1u<<c)|(1u<<d)|(1u<<e));
x.s.resize(5);
x.s[0] = char('0' + a);
x.s[1] = char('0' + b);
x.s[2] = char('0' + c);
x.s[3] = char('0' + d);
x.s[4] = char('0' + e);
cand.push_back(x);
}
}
}
}
}
const int N = (int)cand.size();
// Remaining secrets count m = 30 - solved
int solved = 0;
int remaining = 30;
// weights: expected membership in remaining set, sum(w)=remaining
vector<double> w(N, remaining / (double)N);
vector<uint8_t> asked(N, 0);
vector<Constraint> cons;
cons.reserve(128);
// Time control
const double TIME_LIMIT_SEC = 4.90; // easy to tweak
const int BASE_IPFP_ITER = 4; // try 4 when time allows (tweakable)
const auto t_start = chrono::steady_clock::now();
auto elapsed_sec = [&]() -> double {
auto now = chrono::steady_clock::now();
return chrono::duration<double>(now - t_start).count();
};
// Build resp array for a query q_idx: resp[i] = (h*6+b) between candidate i and q
auto build_resp = [&](int q_idx) -> vector<uint8_t> {
vector<uint8_t> resp(N);
const auto &q = cand[q_idx];
const uint16_t qmask = q.mask;
const auto &qd = q.d;
for (int i = 0; i < N; i++) {
const auto &sd = cand[i].d;
int h =
(sd[0] == qd[0]) + (sd[1] == qd[1]) + (sd[2] == qd[2]) +
(sd[3] == qd[3]) + (sd[4] == qd[4]);
int common = __builtin_popcount((unsigned)(cand[i].mask & qmask));
int b = common - h;
resp[i] = (uint8_t)(h * 6 + b);
}
return resp;
};
// IPFP update: adjust weights so that for each constraint, expected histogram matches cnt
auto ipfp_update = [&](int iters) {
if (cons.empty()) return;
for (int it = 0; it < iters; it++) {
for (auto &c : cons) {
double E[R];
for (int r = 0; r < R; r++) E[r] = 0.0;
// expected counts
const auto &resp = c.resp;
for (int i = 0; i < N; i++) {
double wi = w[i];
if (wi == 0.0) continue;
E[resp[i]] += wi;
}
// scaling factors
double f[R];
for (int r = 0; r < R; r++) {
if (c.cnt[r] == 0) f[r] = 0.0;
else if (E[r] > 0.0) {
double val = (double)c.cnt[r] / E[r];
// mild clamp for numerical safety
if (val > 1e9) val = 1e9;
f[r] = val;
} else {
// Should not happen if constraints are consistent,
// but keep safe.
f[r] = 0.0;
}
}
// apply scaling
for (int i = 0; i < N; i++) {
double wi = w[i];
if (wi == 0.0) continue;
w[i] = wi * f[resp[i]];
}
}
// normalize sum(w)=remaining
double sum = 0.0;
for (double wi : w) sum += wi;
if (!(sum > 0.0) || !isfinite(sum)) {
// fallback: uniform over unasked
int cnt_unasked = 0;
for (int i = 0; i < N; i++) if (!asked[i]) cnt_unasked++;
if (cnt_unasked == 0) return;
double uni = remaining / (double)cnt_unasked;
for (int i = 0; i < N; i++) w[i] = asked[i] ? 0.0 : uni;
} else {
double scale = remaining / sum;
for (double &wi : w) wi *= scale;
}
}
};
// --- Main interactive loop ---
while (true) {
// choose next query = argmax weight among unasked
int q_idx = -1;
double best = -1.0;
for (int i = 0; i < N; i++) {
if (asked[i]) continue;
if (w[i] > best) {
best = w[i];
q_idx = i;
}
}
if (q_idx < 0) return 0; // should not happen
asked[q_idx] = 1;
// output query
cout << cand[q_idx].s << "\n" << flush;
// read response (30 pairs)
array<int16_t, R> total{};
total.fill(0);
vector<pair<int,int>> hb(30);
for (int i = 0; i < 30; i++) {
int h, b;
if (!(cin >> h >> b)) return 0;
hb[i] = {h, b};
if (h == -1 && b == -1) {
// invalid interaction -> terminate immediately
return 0;
}
int id = h * 6 + b;
if (0 <= id && id < R) total[id]++;
}
// if (H0,B0)=(5,0) then all are solved (because sorted)
if (hb[0].first == 5) return 0;
const int solved_before = solved;
const int total50 = total[ID_50];
// detect if this query hit a NEW secret (count of (5,0) increases by 1)
const bool hit_new = (total50 > solved_before);
// build resp array for this query (needed for constraints/IPFP)
vector<uint8_t> resp = build_resp(q_idx);
if (hit_new) {
solved++;
remaining--;
// this solved string is removed from all previous constraints:
// cnt[resp_of_solved]--
for (auto &c : cons) {
uint8_t r = c.resp[q_idx];
c.cnt[r]--;
}
}
// counts for remaining secrets after this query
array<int16_t, R> cnt = total;
// subtract already-solved-before-query contributions to (5,0)
cnt[ID_50] -= (int16_t)solved_before;
// if we newly hit, subtract this q itself from remaining set
if (hit_new) cnt[ID_50]--;
// queried string can never be "remaining" any more
w[q_idx] = 0.0;
// add new constraint
Constraint nc;
nc.q_idx = q_idx;
nc.resp = std::move(resp);
nc.cnt = cnt;
cons.push_back(std::move(nc));
// decide IPFP iterations by remaining time
double left = TIME_LIMIT_SEC - elapsed_sec();
int iters = BASE_IPFP_ITER;
if (left < 0.40) iters = 1;
else if (left < 1.00) iters = min(iters, 2);
else if (left < 2.00) iters = min(iters, 3);
ipfp_update(iters);
}
}