結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 LNG
|
| 提出日時 | 2025-12-25 12:49:27 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,274 bytes |
| 記録 | |
| コンパイル時間 | 2,497 ms |
| コンパイル使用メモリ | 209,700 KB |
| 実行使用メモリ | 26,228 KB |
| スコア | 0 |
| 平均クエリ数 | 30241.00 |
| 最終ジャッジ日時 | 2025-12-25 12:57:05 |
| 合計ジャッジ時間 | 445,562 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 100 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <map>
#include <set>
using namespace std;
struct Result {
int h, b;
bool operator<(const Result& o) const {
if (h != o.h) return h < o.h;
return b < o.b;
}
bool operator==(const Result& o) const {
return h == o.h && b == o.b;
}
bool operator!=(const Result& o) const {
return !(*this == o);
}
};
struct Guess {
int d[5];
int mask;
};
inline Result get_hb(const Guess& q, const Guess& t) {
int h = 0;
if (q.d[0] == t.d[0]) h++;
if (q.d[1] == t.d[1]) h++;
if (q.d[2] == t.d[2]) h++;
if (q.d[3] == t.d[3]) h++;
if (q.d[4] == t.d[4]) h++;
int total = __builtin_popcount(q.mask & t.mask);
return {h, total - h};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto start_time = chrono::steady_clock::now();
vector<Guess> all_v;
for (int i = 0; i <= 99999; i++) {
int tmp = i, m = 0, digs[5];
bool ok = true;
for (int j = 4; j >= 0; j--) {
digs[j] = tmp % 10;
if (m & (1 << digs[j])) ok = false;
m |= (1 << digs[j]);
tmp /= 10;
}
if (ok) {
Guess g; g.mask = m;
for (int j = 0; j < 5; j++) g.d[j] = digs[j];
all_v.push_back(g);
}
}
vector<int> candidates;
candidates.reserve(all_v.size());
for (int i = 0; i < (int)all_v.size(); i++) candidates.push_back(i);
mt19937 rng(42);
int found_count = 0;
int turn = 0;
set<int> resolved_indices;
while (found_count < 30) {
int best_q_idx = -1;
if (turn == 0) {
for(int i=0; i<(int)all_v.size(); ++i) {
if(all_v[i].d[0]==0 && all_v[i].d[1]==1 && all_v[i].d[2]==2 && all_v[i].d[3]==3 && all_v[i].d[4]==4) {
best_q_idx = i; break;
}
}
} else if (turn == 1) {
for(int i=0; i<(int)all_v.size(); ++i) {
if(all_v[i].d[0]==5 && all_v[i].d[1]==6 && all_v[i].d[2]==7 && all_v[i].d[3]==8 && all_v[i].d[4]==9) {
best_q_idx = i; break;
}
}
} else {
auto now = chrono::steady_clock::now();
double elapsed = chrono::duration_cast<chrono::milliseconds>(now - start_time).count();
int sample_size = min((int)candidates.size(), (elapsed < 4000) ? 400 : 200);
vector<int> sample_c;
sample_c.reserve(sample_size);
if (candidates.size() <= (size_t)sample_size) {
sample_c = candidates;
} else {
for (int i = 0; i < sample_size; i++) {
sample_c.push_back(candidates[rng() % candidates.size()]);
}
}
double max_entropy = -1.0;
int search_limit = (elapsed < 3500) ? 100 : 50;
for (int i = 0; i < search_limit; i++) {
int cur_q = (i < 20 && !candidates.empty()) ? candidates[rng() % candidates.size()] : rng() % all_v.size();
auto calc_entropy = [&](int q_idx) {
int counts[6][6] = {0};
for (int c_idx : sample_c) {
Result r = get_hb(all_v[q_idx], all_v[c_idx]);
counts[r.h][r.b]++;
}
double ent = 0;
for (int h = 0; h <= 5; h++) {
for (int b = 0; b <= 5; b++) {
if (counts[h][b] > 0) {
double p = (double)counts[h][b] / sample_size;
ent -= p * log2(p);
}
}
}
return ent;
};
double cur_ent = calc_entropy(cur_q);
for (int step = 0; step < 10; step++) {
int next_q = cur_q;
int opt = rng() % 2;
if (opt == 0) {
int p1 = rng() % 5, p2 = rng() % 5;
swap(all_v[next_q].d[p1], all_v[next_q].d[p2]);
} else {
int p = rng() % 5, v = rng() % 10;
bool exists = false;
for(int k=0; k<5; k++) if(all_v[next_q].d[k] == v) exists = true;
if(!exists) all_v[next_q].d[p] = v;
}
int m = 0;
for(int k=0; k<5; k++) m |= (1 << all_v[next_q].d[k]);
all_v[next_q].mask = m;
double next_ent = calc_entropy(next_q);
if (next_ent > cur_ent) {
cur_ent = next_ent;
} else {
all_v[next_q] = all_v[cur_q];
}
}
if (cur_ent > max_entropy) {
max_entropy = cur_ent;
best_q_idx = cur_q;
}
if (chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start_time).count() > 4700) break;
}
}
if (best_q_idx == -1) best_q_idx = candidates[rng() % candidates.size()];
for (int i = 0; i < 5; i++) cout << all_v[best_q_idx].d[i];
cout << endl;
map<pair<int, int>, int> res_map;
for (int i = 0; i < 30; i++) {
int h, b;
if (!(cin >> h >> b)) return 0;
if (h == -1) return 0;
res_map[{h, b}]++;
}
found_count = res_map[{5, 0}];
if (found_count == 30) break;
vector<int> next_candidates;
for (int c_idx : candidates) {
Result r = get_hb(all_v[best_q_idx], all_v[c_idx]);
if (r.h == 5 && r.b == 0) continue;
if (res_map[{r.h, r.b}] > 0) {
next_candidates.push_back(c_idx);
}
}
candidates = move(next_candidates);
turn++;
}
return 0;
}