結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 syndrome
|
| 提出日時 | 2025-12-25 16:12:25 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,601 ms / 5,000 ms |
| コード長 | 7,946 bytes |
| 記録 | |
| コンパイル時間 | 5,445 ms |
| コンパイル使用メモリ | 341,632 KB |
| 実行使用メモリ | 26,216 KB |
| スコア | 9,995,852 |
| 平均クエリ数 | 41.48 |
| 最終ジャッジ日時 | 2025-12-25 16:14:43 |
| 合計ジャッジ時間 | 129,662 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
main.cpp: In function ‘int solver()’:
main.cpp:197:27: warning: ‘q’ may be used uninitialized [-Wmaybe-uninitialized]
197 | cout << cand[q] << endl;
| ^
main.cpp:160:13: note: ‘q’ was declared here
160 | int q;
| ^
ソースコード
// (◕ᴗ◕✿)
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }
#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}
// #define DEBUG
#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif
unsigned int randxor(){
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}
struct Timer {
public:
Timer(int limit){
start = chrono::high_resolution_clock::now();
goal = start + chrono::milliseconds(limit);
}
inline double rate(){
return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
}
inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}
private:
chrono::high_resolution_clock::time_point start;
chrono::high_resolution_clock::time_point goal;
};
constexpr int TIMELIMIT = 2000;
constexpr int N = 30;
constexpr int M = 21;
constexpr int S = 30240;
constexpr int MAXSCORE = 100;
vc<string> cand;
set<string> answer;
array<int, 10> F;
int turn = 0;
pair<int, int> hb(string &q, string &p){
turn++;
int h = 0, b = 0;
rep(i, 5) F[p[i] - '0'] = turn;
rep(i, 5){
if (q[i] == p[i]) h++;
else b += (F[q[i] - '0'] == turn);
}
return {h, b};
}
void InitBot(){
answer.clear();
while (len(answer) < N){
int i = randint(0, S);
answer.insert(cand[i]);
}
}
vc<pair<int, int>> LocalBot(string a){
vc<pair<int, int>> ret;
rep(i, N - len(answer)) ret.push_back({5, 0});
for (auto x : answer){
auto [h, b] = hb(a, x);
ret.push_back({h, b});
}
if (answer.count(a)) answer.erase(a);
sort(all(ret));
return ret;
}
int solver(){
Timer timer(TIMELIMIT);
cand.clear();
rep(i, 100000){
string a = to_string(i);
while (len(a) < 5) a = "0" + a;
bool ok = true;
rep(y, 5) rep(x, y) if (a[x] == a[y]){
ok = false;
}
if (ok) cand.emplace_back(a);
}
if (DEBUGMODE) InitBot();
array<double, S> prb;
rep(i, S) prb[i] = N / (double)S;
array<array<int, 6>, 6> indexs;
int id = 0;
rep(h, 6) rep(b, 6) if (h + b <= 5){
indexs[h][b] = id;
id++;
}
int score = 0;
int FIND = 0;
array<string, MAXSCORE> Q;
array<array<int, M>, MAXSCORE> P;
array<array<vi, M>, MAXSCORE> rt;
rep(i, MAXSCORE) rep(j, M) P[i][j] = 0;
rep(i, 10) F[i] = 0;
auto update_prb = [&](int id) -> void {
rep(t, M) if (len(rt[id][t])){
double sm = 0;
for (auto i : rt[id][t]) sm += prb[i];
if (sm < 1e-13) continue;
double coeff = P[id][t] / sm;
for (auto i : rt[id][t]){
prb[i] *= coeff;
prb[i] = min(prb[i], 1.0);
}
}
};
array<int, S> order; iota(all(order), 0);
while (true){
sort(all(order) , [&](auto i, auto j){return prb[i] > prb[j];});
int q;
double best = -inf;
rep(_, 200){
int id = order[_];
if (prb[id] < 0.94 * prb[order[0]]) break;
// cerr << cand[id] << ' ' << prb[id] << endl;
array<array<double, N + 1>, M> subprb;
rep(i, M){
fill(all(subprb[i]), 0.0);
subprb[i][0] = 1;
}
rep(j, S){
auto [h, b] = hb(cand[id], cand[j]);
int id = indexs[h][b];
for (int i = N - FIND; i >= 0; i--){
subprb[id][i] *= (1.0 - prb[j]);
if (i > 0) subprb[id][i] += subprb[id][i - 1] * prb[j];
}
}
double info = 0;
rep(i, M){
rep(j, N - FIND + 1) if (subprb[i][j] > 1e-12) info -= subprb[i][j] * log2(subprb[i][j]);
}
double cost = info;
// cout << info << ' ' << prb[id] << ' ' << cost << endl;
// if (prb[id] > 1.0 - 1e-5) cost = inf;
if (cost > best){
best = cost;
q = id;
}
}
// cerr <<"query : " << cand[q] << ' ' << FIND << endl;
// cout << cand[q] << ' ' << prb[q] << ' ' << best << endl;
vc<pair<int, int>> ret;
if (DEBUGMODE){
ret = LocalBot(cand[q]);
}else{
cout << cand[q] << endl;
rep(i, N){
int h, b; cin >> h >> b;
ret.push_back({h, b});
}
}
Q[score] = cand[q];
if (ret[0] == make_pair(5, 0)) break;
for (auto [h, b] : ret){
P[score][indexs[h][b]]++;
}
if (ret[N - FIND - 1] == make_pair(5, 0)){
rep(j, score){
auto [nh, nb] = hb(Q[j], Q[score]);
P[j][indexs[nh][nb]]--;
}
FIND++;
}
rep(i, S) if (prb[i] > 0){
auto [h, b] = hb(cand[q], cand[i]);
if (h == 5){
prb[i] = 0;
}else{
rt[score][indexs[h][b]].push_back(i);
}
}
update_prb(score);
double sm = accumulate(all(prb), 0.0);
double coeff = (N - FIND) / sm;
for (auto& p : prb){
p *= coeff;
p = min(p, 1.0);
}
rep(j, 20){
rep(i, score + 1) update_prb(i);
double sm = accumulate(all(prb), 0.0);
double coeff = (N - FIND) / sm;
rep(i, S){
prb[i] *= coeff;
prb[i] = min(prb[i], 1.0);
}
}
score++;
}
cerr << score + 1 << ' ' << timer.rate() * TIMELIMIT << endl;
return score + 1;
}
int main(){
solver();
// int multi = 100;
// double totalscore = 0;
// rep(i, multi) totalscore += solver();
// cerr << totalscore / (double)multi << endl;
}