#1140380 (C++23) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-14 22:16:11
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 10,100 bytes
• コンパイル時間: 4,497 ms
• コンパイル使用メモリ: 324,260 KB
• 実行使用メモリ: 26,356 KB
• スコア: 0
• 平均クエリ数: 50.00
• 最終ジャッジ日時: 2025-12-25 01:49:25
• 合計ジャッジ時間: 479,627 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	WA * 100

ソースコード

// by GPT 5.2 2nd attempt
#include <bits/stdc++.h>
using namespace std;

// -------------------- RNG --------------------
struct XorShift {
  uint64_t x = 88172645463325252ULL;
  inline uint32_t next_u32() {
    x ^= x << 7;
    x ^= x >> 9;
    return (uint32_t)x;
  }
  inline int next_int(int n) { return (int)(next_u32() % (uint32_t)n); }
  inline double next_double() { return (next_u32() + 0.5) / 4294967296.0; }
} rng;

// -------------------- Encode/Decode (h,b) -> code --------------------
// possible (h,b) with h+b<=5, b>=0.  (5,0) included.
// We'll map to 21 codes (triangular).
static int hb_to_code(int h, int b) {
  // code order: (0,0),(0,1)..(0,5),(1,0)..(1,4),...,(5,0)
  int code = 0;
  for (int hh = 0; hh < h; hh++) code += (6 - hh);
  code += b;
  return code; // 0..20
}
static constexpr int HBK = 21;

// -------------------- generate all 10P5 strings --------------------
struct Cand {
  array<int,5> d;
  string s;
};

static vector<Cand> gen_all() {
  vector<Cand> all;
  array<int,10> a;
  iota(a.begin(), a.end(), 0);
  // iterate permutations of length 5: choose 5 digits, permute.
  // simplest: enumerate all 10P5 by nested loops with used mask.
  for (int d0=0; d0<10; d0++)
    for (int d1=0; d1<10; d1++) if (d1!=d0)
      for (int d2=0; d2<10; d2++) if (d2!=d0 && d2!=d1)
        for (int d3=0; d3<10; d3++) if (d3!=d0 && d3!=d1 && d3!=d2)
          for (int d4=0; d4<10; d4++) if (d4!=d0 && d4!=d1 && d4!=d2 && d4!=d3) {
            Cand c;
            c.d = {d0,d1,d2,d3,d4};
            c.s.resize(5);
            c.s[0]=char('0'+d0);
            c.s[1]=char('0'+d1);
            c.s[2]=char('0'+d2);
            c.s[3]=char('0'+d3);
            c.s[4]=char('0'+d4);
            all.push_back(c);
          }
  return all; // size 30240
}

static inline int eval_hb_code(const array<int,5>& s, const array<int,5>& q){
  // digits are unique; compute hit and blow
  int pos_s[10]; for(int i=0;i<10;i++) pos_s[i]=-1;
  for(int i=0;i<5;i++) pos_s[s[i]]=i;
  int h=0, m=0;
  for(int i=0;i<5;i++){
    int p=pos_s[q[i]];
    if(p!=-1){
      m++;
      if(p==i) h++;
    }
  }
  int b = m - h;
  return hb_to_code(h,b);
}

// -------------------- time --------------------
static inline double now_sec(){
  using namespace chrono;
  return duration_cast<duration<double>>(steady_clock::now().time_since_epoch()).count();
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vector<Cand> all = gen_all();

  // ---------- Phase 1: feature queries ----------
  // K chosen to aim total ~ K + 30 <= 50.
  const int K = 20;

  vector<array<int,5>> queries;
  queries.reserve(K);

  // hist[k][code] counts for UNKNOWN secrets only (excluding (5,0) entries)
  vector<array<int,HBK>> hist;
  hist.reserve(K);

  unordered_set<string> asked; asked.reserve(1024);
  unordered_set<string> knownSecretsSet; knownSecretsSet.reserve(64);
  vector<string> knownSecrets;

  int knownCount = 0;

  auto pick_random_query = [&](){
    // random permutation of digits then take first 5
    array<int,10> d; iota(d.begin(), d.end(), 0);
    for(int i=9;i>0;i--){
      int j = rng.next_int(i+1);
      swap(d[i], d[j]);
    }
    array<int,5> q = {d[0],d[1],d[2],d[3],d[4]};
    return q;
  };

  auto q_to_string = [&](const array<int,5>& q){
    string s(5,'0');
    for(int i=0;i<5;i++) s[i]=char('0'+q[i]);
    return s;
  };

  for(int t=0; t<K; t++){
    array<int,5> q;
    string qs;
    while(true){
      q = pick_random_query();
      qs = q_to_string(q);
      if(!asked.count(qs)) break;
    }
    asked.insert(qs);

    cout << qs << "\n" << flush;

    vector<pair<int,int>> hb(30);
    for(int i=0;i<30;i++){
      if(!(cin >> hb[i].first >> hb[i].second)) return 0;
      if(hb[i].first==-1 && hb[i].second==-1) return 0; // invalid interaction
    }

    // count (5,0)
    int f=0;
    for(auto &p: hb) if(p.first==5 && p.second==0) f++;

    // If f increased and qs is not already known, it means qs is one of secrets.
    if(!knownSecretsSet.count(qs) && f == knownCount + 1){
      knownSecretsSet.insert(qs);
      knownSecrets.push_back(qs);
      knownCount++;
    }

    array<int,HBK> H{};
    H.fill(0);
    for(auto &p: hb){
      if(p.first==5 && p.second==0) continue; // remove known/found parts
      int code = hb_to_code(p.first, p.second);
      H[code]++;
    }
    queries.push_back(q);
    hist.push_back(H);
  }

  int N = 30 - knownCount;
  if(N < 0) N = 0;

  // If already all found (rare), terminate by asking nothing further.
  // But judge terminates only when H0,B0 == (5,0) after some query,
  // so we still need to trigger it: easiest is query any known secret if exists.
  if(N == 0){
    // ask one known secret (or any asked query) to receive all (5,0)
    string qs = knownSecrets.empty() ? *asked.begin() : knownSecrets[0];
    cout << qs << "\n" << flush;
    for(int i=0;i<30;i++){
      int h,b; cin >> h >> b;
      if(h==-1 && b==-1) return 0;
    }
    return 0;
  }

  // ---------- Build candidate list excluding already known secrets ----------
  vector<int> candIds;
  candIds.reserve(all.size());
  for(int i=0;i<(int)all.size();i++){
    if(!knownSecretsSet.count(all[i].s)) candIds.push_back(i);
  }

  // Precompute outcome code table: outcome[id_in_candIds][k]
  // We'll store per original index for easy lookup.
  vector<array<uint8_t, 20>> out; // K==20 fixed here
  out.resize(all.size());
  for(int idx: candIds){
    for(int k=0;k<K;k++){
      out[idx][k] = (uint8_t)eval_hb_code(all[idx].d, queries[k]);
    }
  }

  // ---------- Phase 2: solve constraint by SA ----------
  // target hist per query already for unknown-only and sums to N.
  // We'll find subset S of size N such that for all k, counts match exactly.

  // Prepare quick target as int target[K][HBK]
  vector<array<int,HBK>> target = hist;

  // current subset indices (original all-index)
  vector<int> subset(N, -1);
  vector<char> inSubset(all.size(), 0);

  auto random_init = [&](){
    fill(inSubset.begin(), inSubset.end(), 0);
    for(int i=0;i<N;i++){
      int pick;
      while(true){
        pick = candIds[rng.next_int((int)candIds.size())];
        if(!inSubset[pick]) break;
      }
      subset[i]=pick;
      inSubset[pick]=1;
    }
  };

  // current counts cur[k][HBK]
  vector<array<int,HBK>> cur(K);
  auto rebuild_cur = [&](){
    for(int k=0;k<K;k++){
      cur[k].fill(0);
    }
    for(int id: subset){
      for(int k=0;k<K;k++){
        cur[k][ out[id][k] ]++;
      }
    }
  };

  auto calc_D = [&](){
    int D=0;
    for(int k=0;k<K;k++){
      for(int c=0;c<HBK;c++){
        D += abs(cur[k][c] - target[k][c]);
      }
    }
    return D;
  };

  random_init();
  rebuild_cur();
  int D = calc_D();

  double t0 = now_sec();
  const double TL = 4.6; // leave time for final queries

  // SA parameters
  double T_start = 2.5;
  double T_end   = 0.05;

  // helper: apply replace subset[pos] = nid
  auto try_replace = [&](int pos, int nid){
    int oid = subset[pos];
    if(oid==nid) return false;
    if(inSubset[nid]) return false;

    // compute delta D efficiently
    int delta = 0;
    for(int k=0;k<K;k++){
      int oc = out[oid][k];
      int nc = out[nid][k];
      if(oc==nc) continue;
      // before:
      int a1 = cur[k][oc], a2 = cur[k][nc];
      int t1 = target[k][oc], t2 = target[k][nc];
      int before = abs(a1 - t1) + abs(a2 - t2);
      int after  = abs((a1-1) - t1) + abs((a2+1) - t2);
      delta += (after - before);
    }

    double elapsed = now_sec() - t0;
    double p = elapsed / TL;
    if(p>1.0) p=1.0;
    double T = T_start * pow(T_end / T_start, p);

    if(delta <= 0 || rng.next_double() < exp(-(double)delta / T)){
      // accept
      for(int k=0;k<K;k++){
        int oc = out[oid][k];
        int nc = out[nid][k];
        if(oc==nc) continue;
        cur[k][oc]--;
        cur[k][nc]++;
      }
      inSubset[oid]=0;
      inSubset[nid]=1;
      subset[pos]=nid;
      D += delta;
      return true;
    }
    return false;
  };

  // multi-start + SA
  int bestD = D;
  vector<int> bestSubset = subset;

  while(true){
    double elapsed = now_sec() - t0;
    if(elapsed > TL) break;
    if(D==0) break;

    // random move
    int pos = rng.next_int(N);
    int nid = candIds[rng.next_int((int)candIds.size())];
    try_replace(pos, nid);

    if(D < bestD){
      bestD = D;
      bestSubset = subset;
      if(bestD==0) break;
    }

    // occasional restart if stuck
    if((rng.next_u32() & 8191) == 0 && elapsed < TL*0.9 && bestD > 0){
      random_init();
      rebuild_cur();
      D = calc_D();
      if(D < bestD){
        bestD = D;
        bestSubset = subset;
      }
    }
  }

  subset = bestSubset;
  // If still not exact, we proceed anyway (may fail), but usually bestD==0 with K=20.
  // You can increase K slightly if you want more robustness.

  // ---------- Phase 3: query found secrets to finish ----------
  vector<string> finalSecrets = knownSecrets;
  finalSecrets.reserve(30);

  for(int id: subset) finalSecrets.push_back(all[id].s);

  // As a safety: unique-ify in case of unexpected collision
  sort(finalSecrets.begin(), finalSecrets.end());
  finalSecrets.erase(unique(finalSecrets.begin(), finalSecrets.end()), finalSecrets.end());

  // If we somehow have not exactly 30, pad by best guesses (rare).
  // (In practice, with bestD==0, it becomes exactly 30.)
  if((int)finalSecrets.size() < 30){
    // add random candidates not in final
    unordered_set<string> used(finalSecrets.begin(), finalSecrets.end());
    for(int idx: candIds){
      if((int)finalSecrets.size() == 30) break;
      if(!used.count(all[idx].s)){
        used.insert(all[idx].s);
        finalSecrets.push_back(all[idx].s);
      }
    }
  }

  // Now actually ask them; judge ends when all are found and we ask anything (including last secret).
  for(string &s: finalSecrets){
    cout << s << "\n" << flush;
    int h0=-2,b0=-2;
    for(int i=0;i<30;i++){
      int h,b; cin >> h >> b;
      if(h==-1 && b==-1) return 0;
      if(i==0){ h0=h; b0=b; }
    }
    if(h0==5 && b0==0) return 0; // all found
  }

  return 0;
}