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