IOI 2024 Message

아직 정해를 읽지 않았지만 정황상 본인의 풀이가 정해와 다르다는 확실한 증거가 있기 때문에, 본인의 풀이를 서술해본다. 해당 풀이는 본인의 두뇌가 발상하는 과정의 순서대로 작성되었다.

 

일단, 1024비트 이내의 문자열이지만, 문자열의 길이가 다를 수도 있음을 고려하면 실질적으로 보내야 하는 정보량은 1025비트이다.

 

편의상, Cleopatra 를 캬루라고 하고, Aisha를 에나, Basma를 미즈키라고 하겠다.

 

Observation 1. 정확히 4번 메세지를 보내서 미즈키가 어떤 안전한 위치 하나를 알도록 만들 수 있다.

이를 하는 방법은, 맨 처음에 16개의 안전한 위치중 8개는 0, 나머지 8개는 1을 표기해서 보내는 것이다.

캬루가 나머지 15개를 어떻게 칠하더라도, 절반 미만으로 등장하는 색깔이 존재할 것이고, 미즈키 입장에서는 이를 선택한다. 이렇게 하면 미즈키는 15개 이하 어떤 후보들중에 8개는 안전한 위치라는 정보를 얻는다.

당연히, 똑같은 과정을 (15,8)->(7,4)->(3,2)->(1,1)처럼 진행할 수 있고, 마지막에는 확실한 안전한 위치를 얻게 된다.

 

풀이는 해당 Observation을 가능한 한 빡세게 활용해서, 사용가능한 모든 정보량을 사용하는 것이다.

 

첫 1~4번째 스텝에서 미즈키가 안전한 위치를 알게 되고 나면, 에나는 5~???번 스텝에서 해당 안전한 위치를 통해 미즈키한테 모든 안전한 위치의 정보를 30번 이내에 보낼 수 있다. 물론, 이 스텝들이 돌아가는 동안 다른 안전한 위치들은 순도 100%의 메세지를 전달할 수 있다. 이후 미즈키가 모든 안전한 위치를 알게 되고 나면, 모든 안전한 위치를 정보 전달에만 사용할 수 있게 된다.

 

물론, 이정도의 분석으로는 효율이 부족하기 때문에(아마 본인의 기억으로는 70번정도의 전달이 필요했을 것이다) 더욱 많은 개선이 필요하다.

 

개선방안 1: 잘 생각해보면, 어차피 나중에는 모든 안전한 위치를 알게 되기 때문에 1~4번에서 어떤 안전한 위치들에 0/1을 칠하는가 또한 정보로 작용할 수 있다. 1번 스텝에서는 가능한 16개중 8개를 골라 0을 칠하는 \( \binom{16}{8}\)의 가짓수를 추가로 얻을 수 있고, 2번, 3번, 4번에서도 비슷하게 \( \binom{8}{4} \), \( \binom{4}{2} \), \( \binom{2}{1} \)만큼의 정보를 얻을 수 있다.

 

개선방안 2: 1~4번에서 어떤 안전한 위치들은 안전함에도 불구하고, 미즈키가 후보로 고려하지 않게 될 것이다. 이러한 위치들의 개수는 각각 8,12,14이다. 따라서 해당 위치들을 정보전달에 사용하면 \( 2^{8+12+14} \)만큼의 정보량을 추가로 얻게 된다.

 

여기까지 생각하고 나면 아마 67번의 메세지 전달로 문제가 해결되었던 것으로 기억한다. 게다가, 67->66을 위해 추가로 필요한 비트는 6정도이다.

 

마지막으로 개선할 수 있는 점을 생각해보면, 사실 안전한 위치들의 정보를 30번만에 보낼 필요가 없다는 것이다. 그냥 간단하게만 생각해봐도 가짓수가 \( \binom{30}{15} \)이므로 3비트를 절약할 수 있다. 조금 더 생각해보면, 1~4의 매 스텝마다 안전한 위치 후보에서 제외되는 위치들중 각각 정확히 8,4,2,1개가 안전한 위치임을 알 수 있다. 따라서 엄밀하게 말하자면, 매 스텝에서 제외된 위치의 개수를 각각 \( x,y,z,w \)로 생각해보면 해당 상황에 모든 안전한 위치를 알리기 위해 필요한 정보량은 \( \binom{x}{8} \binom{y}{4} \binom{z}{2} \binom{w}{1}(x+y+z+w=30)    \)와 같이 나타남을 알 수 있다. 이것이 최대가 되는 최악의 시점은 공교롭게도 \( x=16,y=8,z=4,w=2 \)인데, 이를 증명하는 것은 이항계수의 증분이 단조감소한다는 점을 통해서 해당 값이 최대가 되는 시점이 minkowski sum과 같은 느낌의 그리디적 논법으로 인해 증분이 큰걸 그리디하게 선택하는 것이고, 그 결과가 저 상황이라는 것으로 이해할 수 있고, 그게 아니어도 그냥 전탐색해보면 증명가능하다. 아무튼 저 값은 \(2^{24}\) 이하이기 때문에, 6비트를 아낄 수 있게 되고, 결과적으로 66번의 연산으로 정확히 1025비트를 보낼 수 있게 되어 문제가 해결된다.

https://codeforces.com/blog/entry/142741 본인이 작성한 해당 글도 참조하면 좋다.

 

P.S. 방금 정해 풀이를 읽어보고 왔는데, 상당히 신기하긴 했는데 개인적으로는 본인의 풀이가 훨씬 직관적인 방향을 따른다고 생각한다.