백준20060 Combo

작성일 | In

문제 링크

  • http://icpc.me/20060

문제 출처

  • 2018 IOI Day1 1번

풀이

맨 앞에 오는 글자는 이진 탐색의 아이디어를 이용하면 press함수를 2번만 이용해서 구할 수 있습니다.
press(“AB”) 의 값이 0보다 크다면 맨 앞에 나오는 글자는 A 혹은 B입니다. 이 경우에는 press(“A”) 의 값에 따라 A 혹은 B로 결정해주면 됩니다.
press(“AB”) 의 값이 0이라면 맨 앞에 나오는 글자는 X 혹은 Y입니다. 이 경우에는 press(“X”) 의 값에 따라 X 혹은 Y로 결정해주면 됩니다.
위 과정에서 선택된 글자를 S라고 칭합시다.

S가 아닌 다른 문자 3개를 각각 p, q, r이라고 합시다. 문제의 조건에 의해 문자열의 첫 번째 글자 이후로는 S가 더 이상 나오지 않습니다.

두 번째부터 N-1번째까지의 글자는 아래의 방법으로 구합니다.
press(SppSpqSprSq) 의 결과를 res, S의 길이를 sz라고 합시다.
만약 뒤에 p가 온다면 res는 sz+2가 되고, q가 온다면 res는 sz+1, r이 온다면 sz가 됩니다. 세 가지 경우로 나누어 한 글자씩 구해나가면 N-1번째 글자까지 구할 수 있습니다.

마지막 글자는 두 번 만에 구할 수 있습니다. S+p와 S+q로 각각 쿼리를 날려 결과를 봐주면 됩니다.

첫 번째 글자를 2번, 마지막 글자도 2번, 나머지 N-2글자는 각각 1번만에 구해서 총 N+2번만에 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "combo.h"
#include <vector>
using namespace std;

string guess_sequence(int n){
	string S;
	if(press("AB")){
		if(press("A")) S = "A";
		else S = "B";
	}else{
		if(press("X")) S = "X";
		else S = "Y";
	}

	vector<string> v;
	if(S != "A") v.push_back("A");
	if(S != "B") v.push_back("B");
	if(S != "X") v.push_back("X");
	if(S != "Y") v.push_back("Y");

	string p = v[0], q = v[1], r = v[2];

	for(int i=2; i<n; i++){
		int sz = S.size();
		int now = press(S+p+p + S+p+q + S+p+r + S+q);
		if(now == sz+2) S += p;
		else if(now == sz+1) S += q;
		else S += r;
	}

	if(n != 1){
		if(press(S+p) > S.size()) S += p;
		else if(press(S+q) > S.size()) S += q;
		else S += r;
	}

	return S;
}