結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2025-12-14 20:04:48 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 101 ms / 5,000 ms |
| コード長 | 18,327 bytes |
| 記録 | |
| コンパイル時間 | 4,440 ms |
| コンパイル使用メモリ | 328,176 KB |
| 実行使用メモリ | 25,972 KB |
| スコア | 9,964,197 |
| 平均クエリ数 | 358.03 |
| 最終ジャッジ日時 | 2025-12-25 01:33:54 |
| 合計ジャッジ時間 | 14,304 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
// By GPT 5.2 Pro
#include <bits/stdc++.h>
using namespace std;
/*
方針（重要アイデア）:
- クエリ q の数字集合を Q (|Q|=5) とする。
- ある未解決の秘密文字列 S の数字集合を D (|D|=5) とする。
- D==Q のときに限り、S と q の共通数字数は 5 なので必ず h+b=5 になる。
（数字は相異・長さ 5 なので）
- すでに当てた S は以後どんなクエリでも (5,0) が返る。
- したがって「h+b==5 の個数」から、クエリ集合 Q と同じ数字集合を持つ秘密文字列が何本あるか数えられる。
ただし、過去に当てた本数（= (5,0) の本数）ぶんは常に h+b==5 に混入するので差し引く。
*/
struct Reply {
array<pair<int,int>,30> hb{};
int solvedCount = 0; // (5,0) の数
bool allSolved = false; // hb[0]==(5,0) なら全て (5,0)
bool invalid = false; // (-1,-1) が来たら不正
};
static int g_solvedCount = 0; // これまでに当てた本数
static unordered_set<string> g_solvedStrings; // 当てた文字列集合
static unordered_set<string> g_asked; // 既に投げたクエリ（無駄撃ち回避）
static array<int, 1<<10> g_solvedByMask{}; // 数字集合(mask)ごとの当てた本数
static mt19937 rng(1234567);
static inline int maskFromString(const string& s){
int m=0;
for(char c: s) m |= 1<<(c-'0');
return m;
}
static inline int hitCount(const string& a, const string& b){
int h=0;
for(int i=0;i<5;i++) if(a[i]==b[i]) h++;
return h;
}
// クエリを出して 30 行読む（インタラクティブ）
static Reply ask(const string& q){
cout << q << "\n" << flush;
Reply rep;
for(int i=0;i<30;i++){
int h,b;
if(!(cin >> h >> b)){
// EOF: ここまでで終了
exit(0);
}
rep.hb[i] = {h,b};
}
if(rep.hb[0].first == -1 && rep.hb[0].second == -1){
rep.invalid = true;
return rep;
}
int sc=0;
for(auto &p: rep.hb) if(p.first==5 && p.second==0) sc++;
rep.solvedCount = sc;
rep.allSolved = (rep.hb[0].first==5 && rep.hb[0].second==0);
return rep;
}
static void recordSolvedString(const string& s){
if(g_solvedStrings.insert(s).second){
int m = maskFromString(s);
g_solvedByMask[m]++;
}
}
// 「今回のクエリの数字集合」と一致する（未解決の）秘密文字列たちの hit 値 multiset を取り出す。
// 具体的には、h+b==5 のペア列から「以前に当てた本数(prevSolved)」だけ (5,0) を除去し、残りの h を返す。
// ※クエリと同じ数字集合のものだけが未解決で h+b==5 になる。既解決は常に (5,0) で混ざるので引く。
static vector<int> extractHitsSameDigitSet(const Reply& rep, int prevSolved){
vector<pair<int,int>> sum5;
sum5.reserve(30);
for(auto &p: rep.hb){
if(p.first >= 0 && p.first + p.second == 5) sum5.push_back(p);
}
int remove = prevSolved;
vector<int> hits;
hits.reserve(sum5.size());
for(auto &p: sum5){
if(p.first==5 && p.second==0 && remove>0){
remove--;
}else{
hits.push_back(p.first);
}
}
sort(hits.begin(), hits.end());
return hits;
}
static vector<int> digitsFromMask(int mask){
vector<int> d;
for(int x=0;x<10;x++) if(mask&(1<<x)) d.push_back(x);
return d;
}
static string digitsToAscendingQuery(const vector<int>& d){
string s;
for(int x: d) s.push_back(char('0'+x));
return s;
}
static vector<string> allPermutationsOfDigits(vector<int> d){
sort(d.begin(), d.end());
vector<string> perms;
do{
string s;
for(int x: d) s.push_back(char('0'+x));
perms.push_back(s);
}while(next_permutation(d.begin(), d.end()));
// 5! = 120
return perms;
}
struct MaskInfo {
int cnt = 0; // この数字集合を持つ秘密文字列の本数
string scanQuery; // スキャンで投げたクエリ（昇順）
vector<int> scanHitsAll; // scanQuery に対する「この集合の文字列」全本数ぶんの hit multiset（サイズ cnt）
};
// フォールバック: この数字集合の 120 順列を順に投げて remaining 本当てる
static void bruteForceSolveMask(const MaskInfo& info, int mask, int remaining){
if(remaining<=0) return;
auto digits = digitsFromMask(mask);
auto perms = allPermutationsOfDigits(digits);
for(const string& q: perms){
if(remaining<=0) return;
if(g_solvedStrings.count(q)) continue;
if(g_asked.count(q)) continue; // なるべく無駄を避ける
int prevSolved = g_solvedCount;
Reply rep = ask(q);
g_asked.insert(q);
if(rep.invalid) exit(0);
if(rep.solvedCount > prevSolved){
recordSolvedString(q);
remaining--;
}
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
}
}
// remaining==1 を「候補絞り込み（minimax）」で解く
static void solveSingleInMask(const MaskInfo& info, int mask){
int remaining = info.cnt - g_solvedByMask[mask];
if(remaining!=1) return;
auto digits = digitsFromMask(mask);
auto perms = allPermutationsOfDigits(digits);
// scanHitsAll から、すでにこの mask で解いた分を引いて「残り1本の scan hit」を得る
vector<int> scanHits = info.scanHitsAll;
for(const string& s: g_solvedStrings){
if(maskFromString(s)==mask){
int h = hitCount(s, info.scanQuery);
auto it = find(scanHits.begin(), scanHits.end(), h);
if(it!=scanHits.end()) scanHits.erase(it);
}
}
vector<int> candidates;
candidates.reserve(120);
if(scanHits.size()==1){
int h0 = scanHits[0];
for(int i=0;i<(int)perms.size();i++){
if(g_solvedStrings.count(perms[i])) continue;
if(hitCount(perms[i], info.scanQuery)==h0) candidates.push_back(i);
}
}else{
// 万一崩れたら全候補から
for(int i=0;i<(int)perms.size();i++){
if(g_solvedStrings.count(perms[i])) continue;
candidates.push_back(i);
}
}
// 安全策
if(candidates.empty()){
bruteForceSolveMask(info, mask, 1);
return;
}
// 追加クエリで絞る（最大 12 回程度で打ち切ってフォールバック）
for(int step=0; step<12; step++){
if(g_solvedCount>=30) exit(0);
if(candidates.size()==1){
string guess = perms[candidates[0]];
if(!g_asked.count(guess) && !g_solvedStrings.count(guess)){
int prevSolved = g_solvedCount;
Reply rep = ask(guess);
g_asked.insert(guess);
if(rep.invalid) exit(0);
if(rep.solvedCount > prevSolved){
recordSolvedString(guess);
}
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
}
return;
}
// minimax（候補を最も割る質問を探す）
int bestQ = -1;
int bestMax = INT_MAX;
for(int qi=0; qi<(int)perms.size(); qi++){
const string& q = perms[qi];
if(g_asked.count(q)) continue;
int bucket[6]={0,0,0,0,0,0};
for(int ci: candidates){
int h = hitCount(perms[ci], q);
bucket[h]++;
}
int mx=0;
for(int k=0;k<6;k++) mx=max(mx, bucket[k]);
if(mx < bestMax){
bestMax = mx;
bestQ = qi;
}
}
if(bestQ==-1){
// すべて聞いてしまった等: 先頭候補を投げる
bestQ = candidates[0];
}
string q = perms[bestQ];
int prevSolved = g_solvedCount;
Reply rep = ask(q);
g_asked.insert(q);
if(rep.invalid) exit(0);
// この mask のクエリなので、増えていればこの mask の解
if(rep.solvedCount > prevSolved){
recordSolvedString(q);
}
// hit の観測（この mask に残っている 1 本ぶん）
vector<int> hits = extractHitsSameDigitSet(rep, prevSolved);
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
if(hits.size()!=1){
bruteForceSolveMask(info, mask, 1);
return;
}
int obs = hits[0];
// obs==5 なら q が正解で解けた
if(obs==5) return;
vector<int> nextCand;
nextCand.reserve(candidates.size());
for(int ci: candidates){
if(hitCount(perms[ci], q)==obs) nextCand.push_back(ci);
}
candidates.swap(nextCand);
if(candidates.empty()){
bruteForceSolveMask(info, mask, 1);
return;
}
}
// 打ち切りフォールバック
bruteForceSolveMask(info, mask, 1);
}
// remaining==2 or 3 を「部分集合列挙→マルチセット一致」で解く
template<int R>
static void solveMultiInMask(const MaskInfo& info, int mask){
int remaining = info.cnt - g_solvedByMask[mask];
if(remaining!=R) return;
auto digits = digitsFromMask(mask);
auto perms = allPermutationsOfDigits(digits);
// scanHitsAll から、すでにこの mask で解いた分を引いて「残りR本の scan hit」を得る
vector<int> scanHits = info.scanHitsAll;
for(const string& s: g_solvedStrings){
if(maskFromString(s)==mask){
int h = hitCount(s, info.scanQuery);
auto it = find(scanHits.begin(), scanHits.end(), h);
if(it!=scanHits.end()) scanHits.erase(it);
}
}
if((int)scanHits.size()!=R){
// 崩れていたら brute force
bruteForceSolveMask(info, mask, remaining);
return;
}
sort(scanHits.begin(), scanHits.end());
// 候補部分集合を作る（scanQuery に対する hit multiset が一致するものだけ）
vector<int> avail;
avail.reserve(120);
for(int i=0;i<(int)perms.size();i++){
if(g_solvedStrings.count(perms[i])) continue;
avail.push_back(i);
}
struct Sub { array<uint8_t,R> a; };
vector<Sub> subs;
auto sc = info.scanQuery;
if constexpr (R==2){
for(int xi=0; xi<(int)avail.size(); xi++){
for(int yi=xi+1; yi<(int)avail.size(); yi++){
int i=avail[xi], j=avail[yi];
int h1=hitCount(perms[i], sc);
int h2=hitCount(perms[j], sc);
array<int,2> hs{h1,h2};
sort(hs.begin(), hs.end());
if(hs[0]==scanHits[0] && hs[1]==scanHits[1]){
Sub s; s.a = {(uint8_t)i,(uint8_t)j};
subs.push_back(s);
}
}
}
} else { // R==3
for(int xi=0; xi<(int)avail.size(); xi++){
for(int yi=xi+1; yi<(int)avail.size(); yi++){
for(int zi=yi+1; zi<(int)avail.size(); zi++){
int i=avail[xi], j=avail[yi], k=avail[zi];
int h1=hitCount(perms[i], sc);
int h2=hitCount(perms[j], sc);
int h3=hitCount(perms[k], sc);
array<int,3> hs{h1,h2,h3};
sort(hs.begin(), hs.end());
if(hs[0]==scanHits[0] && hs[1]==scanHits[1] && hs[2]==scanHits[2]){
Sub s; s.a = {(uint8_t)i,(uint8_t)j,(uint8_t)k};
subs.push_back(s);
}
}
}
}
}
if(subs.empty()){
bruteForceSolveMask(info, mask, remaining);
return;
}
// 追加クエリで絞る（最大 8 回）
for(int step=0; step<8; step++){
if(g_solvedCount>=30) exit(0);
if(subs.size()==1) break;
// クエリ候補を少数サンプルして minimax
vector<int> qCand;
qCand.reserve(120);
for(int qi=0; qi<(int)perms.size(); qi++){
if(g_asked.count(perms[qi])) continue;
qCand.push_back(qi);
}
if(qCand.empty()) break;
shuffle(qCand.begin(), qCand.end(), rng);
int K = min<int>((int)qCand.size(), 25);
int bestQ = qCand[0];
int bestMax = INT_MAX;
for(int t=0;t<K;t++){
int qi = qCand[t];
// outcome code を数える
// R==2: code=a*6+b (a<=b)
// R==3: code=a*36+b*6+c (a<=b<=c)
static vector<int> cnt;
int maxCode = (R==2 ? 36 : 216);
cnt.assign(maxCode, 0);
for(const auto& s: subs){
array<int,R> hs;
for(int r=0;r<R;r++){
hs[r] = hitCount(perms[(int)s.a[r]], perms[qi]);
}
sort(hs.begin(), hs.end());
int code = 0;
if constexpr (R==2){
code = hs[0]*6 + hs[1];
}else{
code = hs[0]*36 + hs[1]*6 + hs[2];
}
cnt[code]++;
}
int mx=0;
for(int v: cnt) mx=max(mx,v);
if(mx < bestMax){
bestMax = mx;
bestQ = qi;
}
}
string q = perms[bestQ];
int prevSolved = g_solvedCount;
Reply rep = ask(q);
g_asked.insert(q);
if(rep.invalid) exit(0);
// もし解けたなら（この mask のどれかに一致）、一旦戻って remaining を減らして解き直す
if(rep.solvedCount > prevSolved){
recordSolvedString(q);
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
return;
}
vector<int> obs = extractHitsSameDigitSet(rep, prevSolved);
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
if((int)obs.size()!=R){
bruteForceSolveMask(info, mask, remaining);
return;
}
sort(obs.begin(), obs.end());
vector<Sub> next;
next.reserve(subs.size());
for(const auto& s: subs){
array<int,R> hs;
for(int r=0;r<R;r++){
hs[r] = hitCount(perms[(int)s.a[r]], q);
}
sort(hs.begin(), hs.end());
bool ok=true;
for(int r=0;r<R;r++) if(hs[r]!=obs[r]) ok=false;
if(ok) next.push_back(s);
}
subs.swap(next);
if(subs.empty()){
bruteForceSolveMask(info, mask, remaining);
return;
}
}
if(subs.size()==1){
// 特定できたので順に当てる
auto s = subs[0];
int need = info.cnt - g_solvedByMask[mask];
for(int r=0;r<R;r++){
if(need<=0) break;
string guess = perms[(int)s.a[r]];
if(g_solvedStrings.count(guess)) continue;
if(g_asked.count(guess)) {
// 既に聞いたのに解けてないなら矛盾 → brute
bruteForceSolveMask(info, mask, need);
return;
}
int prevSolved = g_solvedCount;
Reply rep = ask(guess);
g_asked.insert(guess);
if(rep.invalid) exit(0);
if(rep.solvedCount > prevSolved){
recordSolvedString(guess);
need--;
}else{
// 外した → brute
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
bruteForceSolveMask(info, mask, need);
return;
}
g_solvedCount = rep.solvedCount;
if(rep.allSolved) exit(0);
}
return;
}
// まだ複数候補なら brute
bruteForceSolveMask(info, mask, remaining);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 5 数字集合(10C5=252)を列挙
vector<int> masks;
for(int m=0; m<(1<<10); m++){
if(__builtin_popcount((unsigned)m)==5) masks.push_back(m);
}
array<MaskInfo, 1<<10> info;
// ---- Phase 1: 252（ただし途中で 30 本分揃ったら打ち切り）スキャン ----
int cumulative = 0;
for(int mask: masks){
if(cumulative>=30) break;
auto digits = digitsFromMask(mask);
string q = digitsToAscendingQuery(digits); // この mask の代表（昇順）
if(g_asked.count(q)) continue; // 念のため
int prevSolved = g_solvedCount;
Reply rep = ask(q);
g_asked.insert(q);
if(rep.invalid) return 0;
// この mask の本数 = (h+b==5 の個数) - prevSolved
int sum5 = 0;
for(auto &p: rep.hb){
if(p.first + p.second == 5) sum5++;
}
int cnt = sum5 - prevSolved;
if(cnt < 0) cnt = 0; // 念のため
info[mask].cnt = cnt;
info[mask].scanQuery = q;
info[mask].scanHitsAll = extractHitsSameDigitSet(rep, prevSolved);
if(rep.solvedCount > prevSolved){
// q がこの mask のどれかに一致して新規に解けた
recordSolvedString(q);
}
g_solvedCount = rep.solvedCount;
if(rep.allSolved) return 0;
cumulative += cnt;
}
// ---- Phase 2: mask ごとに順列を当てに行く ----
for(int mask: masks){
int need = info[mask].cnt - g_solvedByMask[mask];
if(need<=0) continue;
// 小さいところは賢く、でかいところは brute
while(true){
if(g_solvedCount>=30) return 0;
int rem = info[mask].cnt - g_solvedByMask[mask];
if(rem<=0) break;
if(rem==1) solveSingleInMask(info[mask], mask);
else if(rem==2) solveMultiInMask<2>(info[mask], mask);
else if(rem==3) solveMultiInMask<3>(info[mask], mask);
else {
bruteForceSolveMask(info[mask], mask, rem);
break;
}
}
}
// 念のため（普通ここまで来ない）
return 0;
}