No.3418 【Despair】Let's Play 30-Parallel Jumbled Hit&Blow!
タグ : / 解いたユーザー数 28
作問者 :
butsurizuki
/ テスター :
simasima_71
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.
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.
- $h_i$ is the number of integers $k$ satisfying the following condition.
- Then, the sequence of length $30$ formed by the integer pairs $(h_i,b_i)$, sorted in lexicographical order, is returned as the response.
$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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。