재미있는 문제

Online Judge에 있는지는 모르겠고 겨울학교 모의고사로 나온 문제이다. 인터랙티브 비슷한데 좀 다르다.

 

N = 2025 크기의 배열이 있고 그 중 하나만 1이고 나머지는 0이다. K개의 쿼리를 동시에 보낼 수 있는데 각 쿼리는 확인할 배열의 인덱스를 정해서 그 인덱스 중에 1이 있었으면 1을, 아니면 0을 반환한다. 이때 최대 1개의 쿼리는 답을 거꾸로 할 수도 있다. (즉, 1인데 0이라 할 수도 있고 그 반대일 수도 있다) K <= 15일때 1이 있는 위치를 정확히 알 수 있으면 만점을 받는다.

 

시험 당시에는 문제를 잘못 읽어서(...) 버렸는데, 두번째로 쉬운 문제였다. 끝나고 다시 풀어봤는데 꽤 재밌어서 풀이를 남겨두기 위해 풀이를 작성하겠다.

 

#1. K = 33 (25점)

이건 쉽다. (근데 이것도 못긁었음..)

일단 답을 거꾸로 하는 이상한 녀석이 없다고 가정하면, i번 쿼리는 i번 비트가 켜진 모든 인덱스를 방문한다고 쿼리를 때리면 된다.(0<=i<=10)

이러면 11번의 쿼리를 쓰는데, 답을 거꾸로 하는 놈이 있기 때문에 i번 비트 쿼리를 3번씩 날려주면 답을 거꾸로 하는 놈과 상관없이 항상 답을 찾을 수 있다. 이때 K = 33.

 

#2. K = 24 (52점)

앞으로 답을 거꾸로 하는 쿼리를 스파이라 하겠다. 문제에서도 그렇게 서술했으니까.. 

#1의 풀이는 너무 낭비가 심한 것 같다. 11번 쿼리를 날려놓고 스파이 하나 찾으려고 22번이나 더 날리기 때문이다. 어차피 스파이는 최대 1번이니까 재미있는 생각을 할 수 있다. 일단 0~10번 쿼리는 각각이 i번 비트를 확인했다고 하자.

만약 0~10번 쿼리 안에 스파이가 있다고 치면, 0~10번 쿼리를 기반으로 구성한 답은 원래 답과 비트가 정확히 1개 다를 것이다. 즉 비트의 parity가 다르다. 따라서 11번 쿼리는, "켜진 비트 개수가 홀수개" 인 모든 인덱스를 방문하자. 만약 0~10번 안에 스파이가 있는 것이 확실하다면, 이를 토대로 12~22번 쿼리를 날려 0~10번 비트 확인을 한번 더 해줄 수 있다. 그럼 여기는 스파이가 없으니까 이대로 구성하면 답이 된다.

근데 스파이가 정확히 어디 있는지는 아직 모르니까, 다음과 같은 방안을 마련하자.

0~10번 쿼리는 i번 비트를 확인한다.

11번, 12번 쿼리는 비트가 홀수개인 위치를 모두 방문한다.

13~23번 쿼리는 다시 i번 비트를 확인한다.

이제 0~10을 토대로 비트문자열 S를 구성하고 11번, 12번 쿼리를 확인하자.

1) 11번 쿼리와 12번 쿼리의 결과가 다를 경우, 둘 중 하나가 스파이이므로 0~10번은 스파이가 아니다. 따라서 S가 답이다.

2) 11번 쿼리와 12번 쿼리의 결과가 같을 경우, 둘 다 스파이가 아니므로 답의 비트 개수의 parity를 알 수 있다.

2-1)이것과 S가 일치하면 S가 답이다.

2-2)S와 parity가 다르다면 0~10번 사이에 스파이가 반드시 있다. 따라서 13~23번은 스파이가 아니므로 13~23을 토대로 S를 다시 구성하고 이것이 답이다. 이때 K = 24.

(13~23까지 볼 때 스파이가 반드시 없으므로 13~22까지만 봐줘도 되고 이때는 K = 23으로 54점이다)

 

#3. K = 16 (75점)

parity를 비교하는 접근은 꽤 좋은 방법으로 보인다. 하지만 아직 쿼리의 낭비가 꽤 심하다.

0~10번 쿼리는 똑같이 비트를 확인하자. 그리고 11~15번 쿼리는 다음을 확인한다.

11번 : 0~5번의 parity

12번 : 6~10번의 parity 

13번 : 0~2 + 6~8번의 parity

14번 : 0~1 + 3~4 + 6~7 + 9번의 parity

15번 : 0 + 3 + 5 + 6 + 10번의 parity

뭔가 이상해 보이지만, 이분 탐색 비슷한 걸 한다고 생각하자. 이건 그림으로 그리면 보기 편한데 어차피 100점 풀이와는 큰 관련이 없으니까 생략한다. 암튼 저 쿼리들을 기반으로 케이스를 나누면 된다. 

일단 똑같이 0~10을 토대로 비트문자열 S를 구성한다.

1)11번의 parity와 S의 결과가 다른 경우 : 0~5 중 스파이가 있거나 11번이 스파이이다. 13~15는 스파이가 아니므로 이걸 기반으로 쭉 들어가서 확인해줄 수 있다.

2)12번과 다른 경우 : 6~10 중 스파이가 있거나 12번이 스파이이다. 마찬가지로 확인한다.

3)둘다 같은 경우 : parity가 같으므로 S가 답이다.

뭐 이런 느낌으로 해주면 된다. 이때 K = 16.

#4. K = 15 (100점)

#3에서 딱 쿼리 1개만 줄이면 된다. 근데 이게 쉽지 않다. K = 16 풀이에서 뭔가 최적화를 하면 될 것 같지만 잘 안 된다. 그 이유는 다른 접근으로 알 수 있었는데, K = 15가 거의 모든 정보를 완벽하게 사용해야 딱 맞게 되기 때문이다.

전체적으로 #3과 좀 비슷하지만 이분 탐색은 아니다. 11~14번 쿼리가 확인하는 비트를 1, 아닌 비트를 0이라고 할 때 다음과 같이 구성한다.

11 : 11100011101
12 : 10011010111
13 : 01010111011
14 : 00101101111

 

저 배치는 "열" 별로 보면 비트 개수가 2 이상인 2^4 미만의 모든 수이다. 그게 신기하게도 딱 11개다. 이제 11~14번과 S를 비교한 결과를 일치, 불일치에 따라 O 또는 X로 생각하자.

X가 2개 미만이면 무조건 S 그대로가 답이다. 왜냐하면 스파이가 없을 때 다 O여야 하는데 열별로 봤을 때 비트 개수가 2 이상이기 때문에 스파이가 O->X로 바꿀 때 X는 무조건 2 이상이 된다. 따라서 0~10엔 스파이가 없기 때문에 S가 답이다.

반대로 X가 2개 이상이면 무조건 0~10에 스파이가 있다. 이러면 OX를 01에 대응시킨 다음 그것과 일치하는 열을 찾아서 걔를 바꿔주면 된다.

이때 K = 15.

 

K = 16과 K = 15 사이의 점수 차이가 25점이나 되는데 그 이유를 확실히 알 수 있었다.. 비트 2개 이상인게 정확히 11개인 걸 찾고 놀라웠다.