あらすじ

この問題は Advent Calendar Contest 2025 の最終問題です。

皆様には
【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
を遊んでいただきます。

では、始めましょう。

生成 AI の利用について

本問題について、生成 AI の利用はどのようなものであっても特に禁止しません。
但し、生成 AI を利用した場合、どのように利用したかをコード中のコメントに含めて頂けると助かります。
なお、 Writer が生成 AI を利用せずに達成した得点は $9,995,781$ 点(コンテスト終了後に閲覧可能になります)であり、現在の最高スコアでは生成 AI を利用しています。

問題文

この問題には、 5s の実行時間制限が与えられています。
yukicoder の仕様上、メモリ制限は 512MB です。他のコンテストサイトより制限が厳しいことに注意してください。

ジャッジが長さ $5$ の文字列 $S_0,S_1,\dots,S_{29}$ を隠し持っています。
これらの文字列は以下の条件を満たします。

• $S_i$ の各文字は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかである。
• 全ての文字列 $S_i$ について、 $S_i$ 内の文字は相異なる。
• $i \neq j$ ならば $S_i \neq S_j$ である。

あなたは、これらの文字列に対して以下の質問を $10 \times 9 \times 8 \times 7 \times 6 = 30240$ 回まで行うことができます。

$q$

$q$ は以下の条件を満たす必要があります。

• $q$ は長さ $5$ の文字列である。
• $q$ の各文字は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかである。
• $q$ 内の文字は相異なる。

出力を行った後、必ず標準出力をflushしてください。行わなかった場合TLEする可能性があります。

ジャッジは、この質問に対して以下の手順で返答を作成します。

• まず、 $i=0,1,\dots,29$ に対して整数組 $(h_i,b_i)$ を以下の手続きで作成する。
  • もしこの質問にて $S_i=q$ であるか、以前に $S_i=q'$ なる質問 $q'$ をしたことがある場合、$(h_i,b_i)=(5,0)$ とする。
  • そうでないとき、以下の通りに $(h_i,b_i)$ を定める。
    • $h_i$ は、以下の条件を満たす整数 $k$ の個数とする。
      • $S_i$ の $k$ 文字目と $q$ の $k$ 文字目とが等しい。
    • $b_i$ は、以下の条件を満たす整数組 $(k,l) (k \neq l)$ の個数とする。
      • $S_i$ の $k$ 文字目と $q$ の $l$ 文字目とが等しい。
• その後、整数組 $(h_i,b_i)$ を並べた長さ $30$ の列を辞書順にソートしたものを返答する。

返答される列を $((H_0,B_0),(H_1,B_1),\dots,(H_{29},B_{29}))$ としたとき、ジャッジからの返答は次の形式で返されます。

$H_0$ $B_0$
$H_1$ $B_1$
$\vdots$
$H_{29}$ $B_{29}$

$(H_0,B_0)=(5,0)$ となるまで質問を繰り返すことで、隠された全ての文字列を当ててください。
$(H_0,B_0)=(5,0)$ のとき全ての文字列を当てることができているため、解答プログラムを直ちに終了してください。
もし不当なやり取りが行われた場合、 $30$ 個全ての $(H_i,B_i)$ が $(-1,-1)$ と回答されます。
このとき、プログラムは既に不正解であるとみなされているので、直ちにプログラムを終了してください。
ジャッジの入力を必ず最後まで全て受け取ってください。行わなかった場合WAとなる可能性があります。

採点方法

全ての文字列を当てるまでに要した質問の回数を $Q$ とする。
このとき、 $100000-Q$ がそのテストケースの得点となる。
テストケースは全部で 100 個あり、システムテスト等は行われない。

入力生成方法

${\mathcal S}$ を以下の条件を全て満たす文字列全体の集合とする。( $|{\mathcal S}| = 10 \times 9 \times 8 \times 7 \times 6 = 30240$ であることを確認されたい。)

• 長さ $5$ の文字列である。
• 各文字は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかである。
• 含まれる文字が相異なる。

$S$ を ${\mathcal S}$ の相異なる要素 $30$ 個を並べた列としてありうるもの全ての中から一様ランダムに選択する。

サンプル

入出力

< 01234

> 0 0
> 0 1
> ...
> 5 0

< 56789

> 0 0
> ...
> 3 2
> 5 0

入出力は大きくなるので、大幅に省略して示します。
行頭の > は入力を、 < は出力を表します。
このサンプルでは、 $S$ 中に 01234 が含まれ、 56789 が含まれないとします。
最初に受け取る入力がないので、最初から質問を行ってください。
$1$ 個目の質問について、 $S$ 中に 01234 が含まれていることから、返答の $(H_i,B_i)$ 中に $(5,0)$ が含まれています。
$2$ 個目の質問について、 $S$ 中に 56789 は含まれていませんが、 01234 を既に質問しているので返答の $(H_i,B_i)$ 中に $(5,0)$ が含まれています。

ヒント

以下の C++ のコードは $S_i$ としてありうるものを、文字列が全て当たるまで順に尋ねます。
このコードは期待値で $29300$ 回程度の質問を行うため、実行時間を 2000ms 程度消費します。
しかし、動画中で $161$ 回の質問で正解しているように、この回数よりも大幅に少ない質問回数で全ての文字列を当てることができ、やりとりに要する時間も大幅に低減します。

#include<bits/stdc++.h>

using namespace std;

bool check(string s){
  sort(s.begin(),s.end());
  for(int i=1;i<s.size();i++){
    if(s[i-1]==s[i]){return false;}
  }
  return true;
}

int main(){
  vector<string> s;
  for(int i=0;i<=99999;i++){
    int v=i;
    string cur;
    for(int j=0;j<5;j++){
      cur.push_back('0'+v%10);
      v/=10;
    }
    reverse(cur.begin(),cur.end());
    if(check(cur)){s.push_back(cur);}
  }

  for(auto &nx : s){
    cout << nx << "\n";
    fflush(stdout);
    vector<pair<int,int>> hb(30);
    for(auto &nx : hb){
      cin >> nx.first >> nx.second;
    }
    if(hb[0].first==5){return 0;}
  }
}