結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2025-12-15 22:30:46 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 351 ms / 5,000 ms |
| コード長 | 9,662 bytes |
| 記録 | |
| コンパイル時間 | 3,479 ms |
| コンパイル使用メモリ | 304,504 KB |
| 実行使用メモリ | 26,228 KB |
| スコア | 9,995,821 |
| 平均クエリ数 | 41.79 |
| 最終ジャッジ日時 | 2025-12-25 01:50:07 |
| 合計ジャッジ時間 | 37,494 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
/*
30個並列・ソート済みHit&Blowの多重集合だけが返る問題に対し、
「残りの候補が各クエリの( h,b )ヒストグラム制約を満たすように重みを調整(IPF)」
→「最も重い候補を次にクエリ」
を繰り返す。
- flush必須
- 毎回30行読む
- 5s制限なので、時間が厳しくなったらIPF sweep数を落とす
*/
static constexpr int L = 5;
static constexpr int DIG = 10;
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---- popcount (10bit) ----
array<int, 1 << DIG> popc{};
for (int m = 0; m < (1 << DIG); m++) popc[m] = __builtin_popcount((unsigned)m);
// ---- (h,b) -> id (20種類; (4,1)は除外) ----
int id_table[6][6];
for (auto &row : id_table) for (int &x : row) x = -1;
vector<pair<int,int>> id2pair;
for (int h = 0; h <= 5; h++) {
for (int b = 0; b <= 5 - h; b++) {
if (h == 4 && b == 1) continue; // 不可能
int id = (int)id2pair.size();
id2pair.push_back({h,b});
id_table[h][b] = id;
}
}
const int S = (int)id2pair.size(); // 20
const int ID50 = id_table[5][0];
// ---- 全候補(30240=10P5)を列挙 ----
vector<array<uint8_t, L>> cand_digits;
vector<uint16_t> cand_mask;
vector<string> cand_str;
cand_digits.reserve(30240);
cand_mask.reserve(30240);
cand_str.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) {
array<uint8_t,5> dig = {(uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e};
uint16_t mask = (1u<<a)|(1u<<b)|(1u<<c)|(1u<<d)|(1u<<e);
string s;
s.push_back(char('0'+a));
s.push_back(char('0'+b));
s.push_back(char('0'+c));
s.push_back(char('0'+d));
s.push_back(char('0'+e));
cand_digits.push_back(dig);
cand_mask.push_back(mask);
cand_str.push_back(s);
}
const int U = (int)cand_digits.size();
// 念のため
// cerr << "U=" << U << "\n";
// 初手は 01234（上の列挙順で index 0 になる）
const int INIT_Q = 0;
// ---- 状態 ----
vector<char> asked(U, 0), found(U, 0), dead(U, 0);
vector<int> found_time(U, -1);
vector<int> found_list; found_list.reserve(30);
vector<int> q_idxs; // 各クエリとして出した候補のindex
vector<array<int,20>> obs_counts; // 観測した(20種)ヒストグラム（その時点の judge 仕様どおり）
vector<vector<uint8_t>> resp_cols; // resp_cols[j][u] = candidate u の query j に対する response id
// 重み（IPF）
vector<double> w(U, 1.0);
auto start = chrono::steady_clock::now();
const long long TIME_LIMIT_MS = 4900; // 少し安全側
const double EPS = 1e-12;
auto elapsed_ms = [&]() -> long long {
auto now = chrono::steady_clock::now();
return chrono::duration_cast<chrono::milliseconds>(now - start).count();
};
auto calc_resp_id = [&](int u, int qidx) -> uint8_t {
int hit = 0;
const auto &sd = cand_digits[u];
const auto &qd = cand_digits[qidx];
for (int i = 0; i < L; i++) hit += (sd[i] == qd[i]);
int m = popc[(int)(cand_mask[u] & cand_mask[qidx])];
int b = m - hit;
int id = id_table[hit][b];
if (id < 0) id = 0; // 念のため（基本来ない）
return (uint8_t)id;
};
auto add_query = [&](int qidx) -> bool {
int qi = (int)q_idxs.size();
q_idxs.push_back(qidx);
asked[qidx] = 1;
// 出力 & flush
cout << cand_str[qidx] << "\n" << flush;
array<int,20> cnt;
cnt.fill(0);
int h0 = -2, b0 = -2;
for (int i = 0; i < 30; i++) {
int h, b;
if (!(cin >> h >> b)) {
// 入力が途切れた（通常は起きない）
exit(0);
}
if (i == 0) { h0 = h; b0 = b; }
if (h == -1 && b == -1) {
// 不正やり取り扱い
exit(0);
}
int id = (0 <= h && h <= 5 && 0 <= b && b <= 5) ? id_table[h][b] : -1;
if (0 <= id && id < 20) cnt[id]++;
}
obs_counts.push_back(cnt);
// 全部当て終わったら (H0,B0)=(5,0)
if (h0 == 5 && b0 == 0) return true;
// 当たり判定： (5,0) の個数が「既知found数」より増えていれば新規ヒット
int found_before = (int)found_list.size();
int new_hits = cnt[ID50] - found_before;
if (new_hits > 0) {
found[qidx] = 1;
found_time[qidx] = qi;
found_list.push_back(qidx);
} else {
// 今回出した文字列はセットに含まれないと確定
dead[qidx] = 1;
}
// resp_col を作る（全候補 u の、このクエリに対する応答id）
vector<uint8_t> col(U);
for (int u = 0; u < U; u++) col[u] = calc_resp_id(u, qidx);
resp_cols.push_back(std::move(col));
return false;
};
// ---- 初手 ----
if (add_query(INIT_Q)) return 0;
// ---- メインループ ----
while (true) {
int K = (int)q_idxs.size();
int F = (int)found_list.size();
int R = 30 - F;
if (R <= 0) return 0;
// 時間がきつければ sweep を減らす（打ち切り）
long long ms = elapsed_ms();
int sweeps = 3;
if (ms > TIME_LIMIT_MS - 800) sweeps = 1;
else if (ms > TIME_LIMIT_MS - 1800) sweeps = 2;
// --- 調整済みヒストグラム（「残りR個」ぶん）を作る ---
vector<array<int,20>> adj = obs_counts; // copy
for (int s : found_list) {
int ft = found_time[s];
for (int j = 0; j < K; j++) {
if (ft < j) {
// クエリjの時点で既に見つかっていた -> (5,0) として出力されている
adj[j][ID50]--;
} else {
// まだ見つかっていない時点のクエリ -> 本来の応答を引く
uint8_t id = resp_cols[j][s];
adj[j][(int)id]--;
}
}
}
// --- 重みベクトルの準備 ---
// found/dead は 0 にする
double sumw = 0.0;
for (int u = 0; u < U; u++) {
if (found[u] || dead[u]) w[u] = 0.0;
sumw += w[u];
}
if (sumw <= 0.0) {
// 何かで潰れていたら再初期化
sumw = 0.0;
for (int u = 0; u < U; u++) {
w[u] = (found[u] || dead[u]) ? 0.0 : 1.0;
sumw += w[u];
}
}
// 合計Rに正規化
{
double scale = (sumw > 0.0) ? ((double)R / sumw) : 1.0;
for (int u = 0; u < U; u++) w[u] *= scale;
}
// --- IPF sweeps ---
for (int it = 0; it < sweeps; it++) {
for (int j = 0; j < K; j++) {
// 期待値 E[t] を計算
double E[20];
for (int t = 0; t < 20; t++) E[t] = 0.0;
const auto &col = resp_cols[j];
for (int u = 0; u < U; u++) {
double wu = w[u];
if (wu == 0.0) continue;
E[col[u]] += wu;
}
// ratio[t] = obs/expected
double ratio[20];
for (int t = 0; t < 20; t++) {
if (adj[j][t] <= 0) ratio[t] = 0.0;
else {
ratio[t] = (double)adj[j][t] / (E[t] + EPS);
// 念のため過度な発散を抑える（ほぼ不要だが安全策）
if (ratio[t] > 1e6) ratio[t] = 1e6;
}
}
// 重み更新
for (int u = 0; u < U; u++) {
double wu = w[u];
if (wu == 0.0) continue;
w[u] = wu * ratio[col[u]];
}
}
// sweep後に再正規化（合計Rに戻す）
sumw = 0.0;
for (int u = 0; u < U; u++) sumw += w[u];
if (sumw <= 0.0) {
// 潰れたら再初期化
sumw = 0.0;
for (int u = 0; u < U; u++) {
w[u] = (found[u] || dead[u]) ? 0.0 : 1.0;
sumw += w[u];
}
}
double scale = (sumw > 0.0) ? ((double)R / sumw) : 1.0;
for (int u = 0; u < U; u++) w[u] *= scale;
}
// --- 次に尋ねる：最も重い未質問候補 ---
int best = -1;
double bestw = -1.0;
for (int u = 0; u < U; u++) {
if (asked[u] || found[u] || dead[u]) continue;
if (w[u] > bestw) {
bestw = w[u];
best = u;
}
}
if (best < 0) {
// 念のため（通常は起きない）
for (int u = 0; u < U; u++) {
if (!asked[u] && !found[u] && !dead[u]) { best = u; break; }
}
if (best < 0) return 0;
}
if (add_query(best)) return 0;
if ((int)found_list.size() >= 30) return 0;
}
}