IOI 2018 풀이 (제작중)

Yandex 채점(Day 1) 

현재 스코어 100 / 600. 과연 추가할 수 있을런지는 모르겠다...

myungwoo님의 블로그에서 (아마) 모든 문제의 풀이를 확인할 수 있다. 아직은 보지 않은 상태.

18.09.05 P1 solved.

P1. Combo

꽤 괜찮은 interactive 문제. IOI치고 너무 쉬워서 만점자가 240명 가까이 나왔다는 게 유일한 흠이다.

길이 $N$인 미지의 문자열 $S$가 주어진다.

$S$에 주어진 특징은 A, B, X, Y 4개의 문자로 이루어져 있다는 것이고, $S$의 첫번째 문자는 $S$ 안에서 다시 등장하지 않는다는 것이다.

 

이 때 다음의 함수 press(p)를 최대 $N+2$번 호출하여 $S$를 찾아야 한다 : 

길이가 $4N$ 이하인 문자열 $p$를 사용자 임의로 정하여 함수의 parameter로 넘긴다.

이 함수의 반환값은 $p$의 substring 중 $S$의 가장 긴 prefix의 길이이다.

Solution.

우선 첫 번째 문자를 2번만에 알아낼 수 있다.

press("AB")가 

1인 경우 : 

press("A")가 1이면 A, 0이면 B.

0인 경우 :

press("X")가 1이면 X, 0이면 Y.

첫 번째 문자가 다시 나오지 않는다는 점을 활용하여 $N-1$번째 문자까지를 문자 하나 당 1번만에 알아낼 수 있다. 일반성을 잃지 않고 첫 번째 문자를 A라고 하자.

지금까지 알아낸 $S$의 부분문자열을 $P$라고 하자. $|P| \le N-2$.

"PBB" "PBX" "PBY" "PX"를 붙여서 PBBPBXPBYPX를 쿼리로 날린다.

이 문자열의 press 값에 따라 $|P|+1$번째 문자를 결정할 수 있다.

$|P| + 2$인 경우 : B.

$|P| + 1$인 경우 : X.

$|P|$인 경우 : Y.

하지만 이 방법으로는 마지막 문자를 결정할 수 없다. 마지막 문자는 다시 Naive로 2번만에 결정해 주면 총 호출 횟수는 $N+2$번이 된다.

$p$의 길이를 $3N$으로 줄일 수 있다는 소문이 있는데... 모르겠다.

18.09.07 찾았다!

P2. Seats