問題一覧 > スコア問題

No.3418 【Despair】Let's Play 30-Parallel Jumbled Hit&Blow!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 28
作問者 : butsurizuki / テスター : simasima_71
お気に入りにしたユーザー ProblemId : 12931 / 自分の提出
問題文最終更新日: 2025-12-25 07:51:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

Synopsis

This problem is the final problem of Advent Calendar Contest 2025.

You will all be playing
【Despair】Let's Play 30-Parallel Jumbled Hit&Blow!
in this problem.

Now, let's begin.

On the Use of Generative AI

For this problem, no use of generative AI of any kind is specifically prohibited.
However, if you use generative AI, it would be helpful if you include a description of how you used it in the comments of your code.
Note that the score the writer achieved without using generative AI is $9,995,781$ points (viewable after the contest ends), and the current highest score uses generative AI.

Problem Statement

This problem has an execution time limit of 5s.
Due to the specifications of yukicoder, the memory limit is 512MB. Note that this is stricter than on other contest sites.

The judge holds hidden strings $S_0,S_1,\dots,S_{29}$ of length $5$.
These strings satisfy the following conditions.

  • Each character of $S_i$ is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • For every string $S_i$, the characters in $S_i$ are pairwise distinct.
  • If $i \neq j$, then $S_i \neq S_j$.

You may ask the following query about these strings up to $10 \times 9 \times 8 \times 7 \times 6 = 30240$ times.

$q$

$q$ must satisfy the following conditions.

  • $q$ is a string of length $5$.
  • Each character of $q$ is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • The characters in $q$ are pairwise distinct.
After each output, be sure to flush standard output. Otherwise, you may get TLE.

The judge creates its response to the query by the following procedure.
  • First, for $i=0,1,\dots,29$, a pair of integers $(h_i,b_i)$ is created by the following procedure.
    • If $S_i=q$ in this query, or if a query $q'$ with $S_i=q'$ has been asked previously, then $(h_i,b_i)=(5,0)$.
    • Otherwise, $(h_i,b_i)$ is determined as follows.
      • $h_i$ is the number of integers $k$ satisfying the following condition.
        • The $k$-th character of $S_i$ and the $k$-th character of $q$ are equal.
      • $b_i$ is the number of integer pairs $(k,l) (k \neq l)$ satisfying the following condition.
        • The $k$-th character of $S_i$ and the $l$-th character of $q$ are equal.
  • Then, the sequence of length $30$ formed by the integer pairs $(h_i,b_i)$, sorted in lexicographical order, is returned as the response.
Letting the returned sequence be $((H_0,B_0),(H_1,B_1),\dots,(H_{29},B_{29}))$, the response from the judge is given in the following format.

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


Guess all the hidden strings by repeating queries until $(H_0,B_0)=(5,0)$.
When $(H_0,B_0)=(5,0)$, you have guessed all the strings, so terminate your program immediately.
If an invalid interaction takes place, all $30$ of the pairs $(H_i,B_i)$ are returned as $(-1,-1)$.
In this case, your program has already been judged as incorrect, so terminate it immediately.
Be sure to read all of the judge's input to the end. Otherwise, you may get WA.

Scoring

Let $Q$ be the number of queries required to guess all the strings.
Then, the score for the test case is $100000-Q$.
There are 100 test cases in total, and there is no system test or the like.

Input Generation

Let ${\mathcal S}$ be the set of all strings satisfying all of the following conditions. (Note that $|{\mathcal S}| = 10 \times 9 \times 8 \times 7 \times 6 = 30240$.)

  • The string has length $5$.
  • Each character is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • The characters it contains are pairwise distinct.
$S$ is chosen uniformly at random from all possible sequences formed by arranging $30$ distinct elements of ${\mathcal S}$.

Sample

Input/Output
< 01234

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

< 56789

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

Since the input and output are large, they are shown here with most of it omitted.
A leading > denotes input, and < denotes output.
In this sample, suppose that 01234 is contained in $S$ and 56789 is not.
There is no input to receive first, so start by asking a query.
For the $1$-st query, since 01234 is contained in $S$, the $(H_i,B_i)$ in the response contain $(5,0)$.
For the $2$-nd query, 56789 is not contained in $S$, but since 01234 has already been queried, the $(H_i,B_i)$ in the response contain $(5,0)$.

Hint

The following C++ code queries the possible candidates for $S_i$ in order until all the strings have been guessed.
This code makes about $29300$ queries in expectation, and therefore consumes about 2000ms of execution time.
However, as the video shows a solve in $161$ queries, it is possible to guess all the strings with far fewer queries than this, which also greatly reduces the time required for the interaction.

#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;}
  }
}

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。