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

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: butsurizuki
• 提出日時: 2025-12-14 21:25:36
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 13,809 bytes
• コンパイル時間: 5,097 ms
• コンパイル使用メモリ: 338,404 KB
• 実行使用メモリ: 26,356 KB
• スコア: 0
• 平均クエリ数: 1986.05
• 最終ジャッジ日時: 2025-12-25 01:41:24
• 合計ジャッジ時間: 448,782 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

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

ソースコード

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

// ---------------- RNG (fast) ----------------
struct XorShift64 {
  uint64_t x = 88172645463325252ull;
  inline uint64_t next() {
    x ^= x << 7;
    x ^= x >> 9;
    return x;
  }
  inline int nextInt(int n) { return (int)(next() % (uint64_t)n); }
  inline double nextDouble() { return (next() >> 11) * (1.0 / (1ull << 53)); }
} rng;

// ---------------- utilities ----------------
static inline int popcount10(int m) { return __builtin_popcount((unsigned)m); }

struct Cand {
  array<int,5> d;
  int mask; // 10-bit
  string s;
};

// (h,b) categories for length 5 without repeats.
// We'll map (h,b) to id via table.
static int catId[6][6]; // -1 if invalid
static vector<pair<int,int>> idToHB;

static void initCats() {
  for(int h=0; h<=5; h++) for(int b=0; b<=5; b++) catId[h][b] = -1;
  idToHB.clear();
  for(int h=0; h<=5; h++){
    for(int b=0; b<=5; b++){
      if(h==5 && b!=0) continue;
      if(h+b>5) continue;
      // b can be 0..5-h, that's ok
      catId[h][b] = (int)idToHB.size();
      idToHB.push_back({h,b});
    }
  }
}

// score between candidate c and query q (both length 5, distinct digits)
static inline pair<int,int> scoreHB(const Cand& c, const array<int,5>& qd, int qmask){
  int h=0;
  for(int i=0;i<5;i++) if(c.d[i]==qd[i]) h++;
  int common = popcount10(c.mask & qmask);
  int b = common - h;
  return {h,b};
}

static inline int scoreId(const Cand& c, const array<int,5>& qd, int qmask){
  auto [h,b] = scoreHB(c, qd, qmask);
  return catId[h][b];
}

// ---------------- build all 30240 candidates ----------------
static vector<Cand> buildAll() {
  vector<Cand> all;
  all.reserve(30240);
  array<int,10> a;
  iota(a.begin(), a.end(), 0);
  // generate all 5-permutations of digits 0..9
  // We'll do nested loops (fast, simple).
  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.mask = (1<<d0)|(1<<d1)|(1<<d2)|(1<<d3)|(1<<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;
}

// ---------------- interactive I/O ----------------
static vector<pair<int,int>> ask(const string& q){
  cout << q << "\n";
  cout.flush();
  vector<pair<int,int>> hb(30);
  for(int i=0;i<30;i++){
    if(!(cin >> hb[i].first >> hb[i].second)){
      // EOF / error
      exit(0);
    }
  }
  if(hb[0].first==-1 && hb[0].second==-1){
    // invalid interaction -> already judged wrong
    exit(0);
  }
  return hb;
}

// ---------------- SA solver ----------------
struct Solver {
  const vector<Cand>& all;
  int Tq; // number of probe queries
  int K;  // number of already-found secrets
  int N;  // remaining secrets to find = 30-K

  vector<array<int,5>> qd;
  vector<int> qmask;

  // targetCounts[q][cat] = how many remaining secrets produce this (h,b) for query q
  vector<vector<int>> targetCounts;

  // Precomputed score id for each candidate and each query: sc[candIndex][q]
  vector<vector<uint16_t>> sc;

  // SA state: selected indices (in all), and inSel marker
  vector<int> sel;
  vector<uint8_t> inSel;

  // currentCounts[q][cat]
  vector<vector<int>> curCounts;
  int curScore = 0;

  Solver(const vector<Cand>& all_, int Tq_)
    : all(all_), Tq(Tq_) {}

  static inline int l1diff(const vector<int>& a, const vector<int>& b){
    int s=0;
    for(size_t i=0;i<a.size();i++) s += abs(a[i]-b[i]);
    return s;
  }

  void buildScoreTable(){
    sc.assign(all.size(), vector<uint16_t>(Tq));
    for(size_t i=0;i<all.size();i++){
      for(int t=0;t<Tq;t++){
        sc[i][t] = (uint16_t)scoreId(all[i], qd[t], qmask[t]);
      }
    }
  }

  void initTargets(const vector<vector<pair<int,int>>>& rawHB, int foundK){
    // rawHB[t] is the 30 pairs returned (sorted), AFTER asking probe t
    // We will compute target counts for the remaining N=30-foundK secrets:
    // For each t, remove (5,0) pairs which correspond to already-found secrets (persistent)
    K = foundK;
    N = 30 - K;

    int C = (int)idToHB.size();
    targetCounts.assign(Tq, vector<int>(C, 0));

    for(int t=0;t<Tq;t++){
      // Count all categories
      vector<int> cntAll(C, 0);
      for(auto [h,b] : rawHB[t]){
        int id = catId[h][b];
        if(id<0){
          // should never happen
          exit(0);
        }
        cntAll[id]++;
      }
      // Remove persistent (5,0) caused by already found secrets
      int id50 = catId[5][0];
      if(cntAll[id50] < K){
        // This can happen if we mis-tracked foundK; be safe.
        // We'll clamp.
        cntAll[id50] = K;
      }
      cntAll[id50] -= K;

      // Now cntAll describes remaining secrets for this query.
      targetCounts[t] = std::move(cntAll);
    }
  }

  int computeScoreFromCounts(const vector<vector<int>>& counts){
    int s=0;
    for(int t=0;t<Tq;t++){
      for(size_t c=0;c<counts[t].size();c++){
        s += abs(counts[t][c] - targetCounts[t][c]);
      }
    }
    return s;
  }

  void applyAdd(int idx){
    for(int t=0;t<Tq;t++){
      curCounts[t][sc[idx][t]]++;
    }
  }
  void applyRemove(int idx){
    for(int t=0;t<Tq;t++){
      curCounts[t][sc[idx][t]]--;
    }
  }

  void initRandomState(){
    int M = (int)all.size();
    inSel.assign(M, 0);
    sel.clear();
    sel.reserve(N);

    // random pick N distinct
    while((int)sel.size() < N){
      int x = rng.nextInt(M);
      if(inSel[x]) continue;
      inSel[x]=1;
      sel.push_back(x);
    }

    int C = (int)idToHB.size();
    curCounts.assign(Tq, vector<int>(C, 0));
    for(int idx : sel) applyAdd(idx);
    curScore = computeScoreFromCounts(curCounts);
  }

  // Return true if found exact (score==0) within time iterations
  bool solveSA(double timeLimitSec){
    using Clock = chrono::high_resolution_clock;
    auto st = Clock::now();

    const int M = (int)all.size();
    const int C = (int)idToHB.size();

    int bestScore = INT_MAX;
    vector<int> bestSel;

    // Multi-start SA
    int restarts = 0;
    while(true){
      initRandomState();
      if(curScore < bestScore){
        bestScore = curScore;
        bestSel = sel;
      }
      // SA parameters
      double T0 = 2.0;
      double T1 = 0.02;

      // iterations in this restart
      for(int iter=0; iter<400000; iter++){
        auto now = Clock::now();
        double elapsed = chrono::duration<double>(now - st).count();
        if(elapsed > timeLimitSec) break;

        if(curScore==0) return true;

        double prog = elapsed / timeLimitSec;
        double Temp = T0 * pow(T1/T0, prog);

        // neighbor: swap one in sel with one out
        int pos = rng.nextInt(N);
        int outIdx = sel[pos];

        int inIdx;
        for(;;){
          inIdx = rng.nextInt(M);
          if(!inSel[inIdx]) break;
        }

        // delta update: remove outIdx, add inIdx
        // We'll compute delta score by applying and measuring change in L1 fast.
        int delta = 0;
        for(int t=0;t<Tq;t++){
          int cOut = sc[outIdx][t];
          int cIn  = sc[inIdx][t];

          // current count before move
          int beforeOut = curCounts[t][cOut];
          int beforeIn  = curCounts[t][cIn];

          // For L1, only affected categories.
          auto adjustOne = [&](int cat, int newCount){
            int oldCount = curCounts[t][cat];
            int target   = targetCounts[t][cat];
            delta -= abs(oldCount - target);
            delta += abs(newCount - target);
          };

          if(cOut == cIn){
            // net 0
          } else {
            adjustOne(cOut, beforeOut - 1);
            adjustOne(cIn,  beforeIn  + 1);
          }
        }

        bool accept = false;
        if(delta <= 0) accept = true;
        else {
          double p = exp(-(double)delta / max(1e-9, Temp));
          if(rng.nextDouble() < p) accept = true;
        }

        if(accept){
          // apply
          applyRemove(outIdx);
          applyAdd(inIdx);
          inSel[outIdx]=0;
          inSel[inIdx]=1;
          sel[pos]=inIdx;
          curScore += delta;

          if(curScore < bestScore){
            bestScore = curScore;
            bestSel = sel;
            if(bestScore==0) return true;
          }
        }
      }

      // time check
      auto now = Clock::now();
      double elapsed = chrono::duration<double>(now - st).count();
      if(elapsed > timeLimitSec) break;

      restarts++;
      // continue restart
    }

    // If failed, keep best found (not exact).
    sel = bestSel;
    curScore = bestScore;
    return (curScore==0);
  }

  vector<int> getSolutionIndices() const { return sel; }
};

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

  initCats();
  auto all = buildAll();

  // --- 20 fixed probe queries (deterministic, distinct digits) ---
  // We pick permutations produced by a simple rng seeded constant.
  // (Any fixed set works; these are chosen to have good variety.)
  const int PROBES = 20;
  vector<string> probeStr;
  {
    XorShift64 rr;
    rr.x = 1234567891234567ull;

    // generate random 5-permutations without repetition; avoid duplicates
    unordered_set<string> used;
    while((int)probeStr.size() < PROBES){
      array<int,10> d; iota(d.begin(), d.end(), 0);
      // shuffle
      for(int i=9;i>0;i--){
        int j = rr.nextInt(i+1);
        swap(d[i], d[j]);
      }
      string s;
      for(int i=0;i<5;i++) s.push_back(char('0'+d[i]));
      if(used.insert(s).second) probeStr.push_back(s);
    }
  }

  // Track found secrets (by accidental exact hits during probes)
  vector<string> found;
  unordered_set<string> foundSet;

  // Record raw HB responses for each probe (always read 30 lines)
  vector<vector<pair<int,int>>> rawHB(PROBES);

  int solvedK = 0; // number of already-found secrets (persistent (5,0) count)

  for(int t=0;t<PROBES;t++){
    auto hb = ask(probeStr[t]);
    rawHB[t] = hb;

    // Count (5,0) in this response
    int cnt50 = 0;
    for(auto [h,b] : hb) if(h==5 && b==0) cnt50++;

    // If (5,0) count increased, then this probe exactly matched a new secret.
    // We know the exact string: probeStr[t].
    if(cnt50 > solvedK){
      // Add this as found (may happen multiple at once? cannot, because only one secret equals this query)
      if(!foundSet.count(probeStr[t])){
        found.push_back(probeStr[t]);
        foundSet.insert(probeStr[t]);
      }
      solvedK = cnt50;
    }

    // If already solved all, we can exit immediately.
    if(hb[0].first==5 && hb[0].second==0){
      return 0;
    }
  }

  // Prepare solver with remaining constraints
  Solver solver(all, PROBES);
  solver.qd.resize(PROBES);
  solver.qmask.resize(PROBES);
  for(int t=0;t<PROBES;t++){
    array<int,5> qd;
    int m=0;
    for(int i=0;i<5;i++){
      int v = probeStr[t][i]-'0';
      qd[i]=v;
      m |= 1<<v;
    }
    solver.qd[t]=qd;
    solver.qmask[t]=m;
  }
  solver.buildScoreTable();
  solver.initTargets(rawHB, solvedK);

  // SA solve within ~4.2 seconds (leave time for final guessing I/O)
  bool ok = solver.solveSA(4.2);

  vector<string> answerList;
  answerList.reserve(30);

  // Add already found (during probes)
  for(auto &s : found) answerList.push_back(s);

  // Add solved by SA (remaining candidates)
  auto idxs = solver.getSolutionIndices();
  for(int idx : idxs){
    answerList.push_back(all[idx].s);
  }

  // Deduplicate just in case (should not happen)
  sort(answerList.begin(), answerList.end());
  answerList.erase(unique(answerList.begin(), answerList.end()), answerList.end());

  // If SA failed or dedup removed something, fallback:
  // (Worst-case: just try all candidates sequentially - too many, but we keep something reasonable.)
  // Here we do a small safety net: if not 30, pad with probe strings (harmless).
  while((int)answerList.size() < 30){
    // add more random unique strings
    string s = probeStr[rng.nextInt(PROBES)];
    if(!binary_search(answerList.begin(), answerList.end(), s)){
      answerList.insert(lower_bound(answerList.begin(), answerList.end(), s), s);
    } else {
      // random from all
      string t = all[rng.nextInt((int)all.size())].s;
      if(!binary_search(answerList.begin(), answerList.end(), t)){
        answerList.insert(lower_bound(answerList.begin(), answerList.end(), t), t);
      }
    }
  }
  if((int)answerList.size() > 30) answerList.resize(30);

  // Now, ask each candidate in answerList to "lock" them to (5,0).
  // We may re-ask ones already asked in probes; it's okay (it just stays (5,0) if already solved),
  // but to reduce noise, we can skip those in probeStr set.
  unordered_set<string> asked;
  for(auto &s: probeStr) asked.insert(s);

  // We must eventually reach hb[0]==(5,0) which means all 30 have been solved :contentReference[oaicite:6]{index=6}
  for(auto &s : answerList){
    if(asked.count(s)) continue; // already asked during probe
    auto hb = ask(s);
    if(hb[0].first==5 && hb[0].second==0){
      return 0;
    }
  }

  // If still not finished (due to SA failure), brute-force a bit more (bounded).
  // This is just a safety net; good runs should finish above.
  for(int tries=0; tries<2000; tries++){
    string s = all[rng.nextInt((int)all.size())].s;
    if(asked.count(s)) continue;
    asked.insert(s);
    auto hb = ask(s);
    if(hb[0].first==5 && hb[0].second==0) return 0;
  }

  return 0;
}