IOI 2018 Day 1 Combo

작성일 | In

문제

문제 링크 (oj.uz)

IOI 2018 Day 1 첫 번째 문제입니다.

재밌고 쉬운 문제입니다.

풀이

첫 번째 문자는 2번만에 찾을 수 있습니다.

press("AB")가 1인 경우 첫 번째 문자는 A 혹은 B이므로 press("A")의 결과로 알아낼 수 있습니다.

press("AB")가 0인 경우에는 X 혹은 Y이므로 마찬가지로 press("X")로 알아낼 수 있습니다.

일반성을 잃지 않고 첫 번째 문자를 A라 합시다.

그리고 이때까지 우리가 알아낸 $S$의 접두사를 P라 합시다.

$S$의 첫 번째 문자는 뒤에서 다시 나타나지 않으므로 $S$의 접두사를 여러개 붙여서 press를 호출하면 각 접두사마다 press값의 최댓값을 얻는 것과 같습니다.

다음 문자가 B인 경우, X인 경우, 그렇지 않은 경우(Y인 경우)로 나누어지게 잘 접두사를 붙여봅시다.

B인 경우는 P + "B"로 테스트 해 볼 수 있습니다.

X인 경우를 똑같이 P + "X"로 테스트하면 둘을 구분할 수 없으므로 다음 글자가 X인 경우 무조건 길이가 하나 더 길게 나오도록 가능한 모든 경우(P + "XB", P + "XX", P + "XY")를 다 붙여줍시다.

이제 이를 전부 붙여서 press를 호출하면 다음 글자가 무엇인지 한 번만에 알 수 있습니다.

다만 문자열의 길이가 $4N$을 넘어가면 안 되므로 길이를 계산해봅시다.

$\lvert P \rvert + 1 + 3(\lvert P \rvert + 2) = 4\lvert P \rvert + 3$

따라서 식을 정리하면 $\lvert P \rvert \leq N - 2$까지만 한 번만에 다음 글자를 찾을 수 있습니다.

첫 번째 글자를 찾는데 press를 두 번 호출했으므로 $N$번의 호출로 $N - 1$개의 글자를 찾을 수 있습니다.

2번의 호출을 더 할 수 있으므로 마지막은 naive하게 테스트 해 주면 됩니다.

코드

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "combo.h"
#include <algorithm>
#include <vector>
using namespace std;

#define all(v) (v).begin(), (v).end()

vector<char> chr = {'A', 'B', 'X', 'Y'};

string guess_sequence(int N) {
    string S;

    if (press("AB") == 0) {
        if (press("X"))
            S += 'X';
        else
            S += 'Y';
    } else {
        if (press("A"))
            S += 'A';
        else
            S += 'B';
    }
    chr.erase(remove(all(chr), S[0]), chr.end());

    while ((int)S.size() <= N - 2) {
        string p;

        for (int i = 0; i < 3; i++) {
            p += S;
            p += chr[0];
            p += chr[i];
        }
        p += S;
        p += chr[1];

        int coin = press(p);

        if (coin == S.size() + 2) {
            S += chr[0];
        } else if (coin == S.size() + 1) {
            S += chr[1];
        } else {
            S += chr[2];
        }
    }

    if (S.size() < N) {
        for (int i = 0; i < 2; i++) {
            if (press(S + chr[i]) == N) {
                S.push_back(chr[i]);
                break;
            }
        }
        if (S.size() != N)
            S += chr[2];
    }

    return S;
}

IOI 2018 Day 1 Combo