[JOISC 2022] Broken Device 2

oj.uz / acmicpc.net

문제

Anna, Bruno, D-taro가 게임을 진행합니다. 게임을 시작할 때, Anna는 $1$ 이상 $2000$ 이하의 정수 $m$ 하나를 선언합니다. 이후 게임은 $Q$개의 라운드로 구성되며, 각 라운드는 다음과 같이 진행됩니다.

1. D-taro가 Anna에게 정수 $A$를 줍니다.
2. Anna는 $s, t$를 기계에 입력합니다. $s$와 $t$는
   • 각 원소가 $0$ 혹은 $1$이어야 하고,
   • 두 배열의 길이가 같아야 하며,
   • 길이가 $1$ 이상 $m$ 이하여야 합니다.
3. $s$와 $t$를 리플 셔플해서 얻은 배열 $u$를 Bruno에게 보냅니다.
   • $s$와 $t$를 리플 셔플한 결과가 $u$라는 것은, $u$에 있는 수를 두 그룹으로 나눴을 때 첫째 그룹은 $s$, 둘째 그룹은 $t$와 순서를 유지한 채 일치한다는 의미입니다.
4. Bruno는 D-taro에게 정수를 보냅니다. 이 정수가 $A$와 일치하면, Anna와 Bruno는 이 라운드에서 승리합니다.

Anna와 Bruno의 필승전략을 구현해야합니다.

Subtask

Subtask는 다음과 같습니다. (괄호 안 점수는 누적 점수입니다.)

1. $A \le 2,000$ (5pts)
2. $A \le 4,000,000$ (10pts)
3. $A \le10^7$ (13pts)
4. $A \le 10^8$ (25pts)
5. $A \le 10^{11}$ (40pts)
6. $A \le 10^{18}$이고, 선언한 $m$에 따라 다음과 같이 점수가 주어집니다.
   1. $201 \le m \le 2,000$ ($\left\lfloor40 - 25 \times \log_{10} \left(\frac{m}{200}\right)\right\rfloor + 40$ pts)
   2. $161 \le m \le 200$ (80pts)
   3. $156 \le m \le 160$ (84pts)
   4. $151 \le m \le 155$ (88pts)
   5. $146 \le m \le 150$ (92pts)
   6. $141 \le m \le 145$ (96pts)
   7. $m \le 140$ (100pts)

풀이

풀이를 생각한 순서대로 작성합니다.

10pts

다음 두 가지의 기초적이지만 유용한 관찰을 합시다.

• 길이를 $1$ 이상 $m$ 이하로 보낼 수 있다는 것은, 길이 자체도 하나의 정보가 될 수 있다는 것입니다.
• 셔플에서 사라지지 않는 성질은, 수의 개수가 유지된다는 것입니다.

둘 중 하나만 이용하면 $5$점을 받을 수 있고, 길이 $A$의 배열에서 $1$의 개수를 $0$개부터 $2A$개까지 바꿔가며 전송하면, 총 $1+3+5+\cdots+2001 = 4,000,000$개의 정보를 전달할 수 있습니다.

코드(5pts): https://oj.uz/submission/643079

코드: https://oj.uz/submission/643080

13pts

리플 셔플이 순서를 유지한다는 것을 관찰합시다.

• $u$의 가장 앞 수는 $s$의 가장 앞 수 혹은 $t$의 가장 앞 수입니다. 이 둘을 동일하게 보내면 정보를 추가로 전달할 수 있습니다.
• 이는 뒤에서도 마찬가지입니다.

그렇기 때문에, 우리는 길이 $A$의 배열에서 가장 앞 두 수를 동일하게 보내고, 가장 뒤 두 수를 동일하게 보내고, 나머지를 $1$의 개수를 바꿔 보내가면 길이 $A$의 배열에서 $4(2(A-2)+1)$개의 정보를 보낼 수 있습니다.

코드: https://oj.uz/submission/643086

40pts?

이후, 저는 "두 수의 동일함"을 이용하겠다는 끔찍한 발상을 해 버렸습니다.

두 수의 동일함을 이용하겠다고 생각한 이유는, 다른 인덱스가 많으면 많을수록 셔플의 경우의 수가 더 많아졌기 때문입니다. (가령이면, $0$을 $A$개 쓴 수열과 $1$을 $A$개 쓴 수열을 리플셔플하면 $\binom{2A}{A}$개의 경우가 나옵니다.)

여기서 몇가지 틀렸지만 도움이 되어 버린 발상을 했습니다.

• $s$와 $t$의 각 자리수가 다르면 안 좋다! (틀렸습니다)
  • $s=00, t = 11$이 만드는 $u$가 $s=t=10$이 만드는 $u$보다 많았기 때문에, 최대한 $s$와 $t$를 같도록 유지하려고 했습니다.
• $s=t=0101$과 $s=t=0011$은 서로 구분할 수 없다.
  • $u=00110011$이 둘 모두의 결과로 만들어질 수 있습니다.

둘 중 하나의 수만 선택할 수 있었고, $1010$은 사용하기 어렵다는 결론을 내렸습니다. 즉 $1100$과 같은 수들을 사용하기로 했습니다. 비트 하나를 전송하기 위해서 수 "여러개"를 붙여서 전달하려 했습니다. 이 경우 다음과 같은 관찰이 가능합니다.

• $u$의 앞 $2k-1$개를 뽑으면 적어도 수 $k$개를 볼 수 있습니다.

이를 이용하면, 같은 수를 $1$개, $2$개, $4$개, ... 붙여나가면 앞의 $1$개, $3$개, $7$개의 수의 합을 보고 답을 알 수 있을 거라 생각했습니다.

그리고 처참하게(https://oj.uz/submission/643092) 망했습니다.

하나는, 저 방법을 사용하기에는 수의 개수가 너무 모자랐다는 것이고, 어쨌든 저 방법을 사용하더라도 $k$개의 비트를 전송하는데 $O(2^k)$개의 수를 사용해야하기 때문에, 끽해봐야 $A$의 다항함수에 해당하는 정보밖에 전달할 수 없습니다.

이후 다음과 같은 생각을 했습니다.

• $u$를 볼 때 $s$의 어디까지 사용했고, $t$의 어디까지 사용했는지 알 수 있을까?

이 때, $u$를 $(s, t)$문자열의 오토마타로 생각해서 가능한 상태들을 들고 있고, 이 상태가 겹치지 않도록 문자열 $(s, t)$ 쌍을 보내는 것을 생각했습니다.

이미 앞에 있는 수의 개수 정보를 활용하면 다양한 것들을 할 수 있지 않을까? 하는 생각 이었습니다. 이 경우 수의 개수를 줄일 수 있습니다. 그리고 앞에서 수를 붙이고 뒤에서 수를 붙이고 가운데는 수의 개수를 잘 세어주고... 이를 DP를 이용해서 앞/뒤/가운데의 최적의 수 개수를 찾을 수 있었지만... 구현한 DP가 $O(N^3)$이었을 뿐더러, $10^{18}$에는 한참 못미치는 수였기 때문에, 기각했습니다.

80pts

이후 저는 $s = t$는 답이 없다고 생각해서 $s \ne t$인 경우를 생각했습니다. 그리고 한 $20$분 정도 생각하고 위의 $0101$케이스를 다시 보기로 했습니다.

$t = 010101 \dots$인 경우에 $s$를 구분하는 법을 찾으려고 했습니다. $s$에 연속된 $0$이 $3$개 있을 경우, 가운데에 $1$이 끼어들어가도 연속되어 $0$이 두 개 나오는 위치가 있다는 것을 찾았습니다. $s$에 연속된 $1$이 $3$개 있을 경우도 마찬가지라는 것을 알았습니다.

위의 오토마타 아이디어를 사용해서 현재 $(s, t)$상태에 따라서 $s$가 어떤 상태이고 $t$가 어떤 상태인지 확인해 보기로 했습니다. 그리고 나온 상태 전이가 다음과 같습니다. ($s$에서 현재까지 본 문자열, $t$에서 앞으로 봐야하는 문자열과 같은 방식으로 표현하고, $P$는 출력을 의미합니다.)

이를 구현하면 80점을 받습니다.

코드: https://oj.uz/submission/643188

80pts+?

여기서 다양한 $m$에 대해 전송하든 어떻든 방법이 없다는 걸 알아서, 여러가지 시도를 해 보기로 했습니다. 하나는 $0$과 $1$을 두개씩 삽입하는 것이고, 이는 $0011$과 $10$이 있으면, $010101$과 같은 방식으로 셔플을 할 수 있어서 안 된다는 것을 알았습니다.

그리고 제 실수는 다음에서 나오는데... $0$은 $3$개씩 쓰고, $1$은 $2$개씩 쓰는 경우, 그리고 같은 수를 $3$개/$2$개/$3$개/$2$개... 번갈아가면서 쓰는 경우 두 가지에서 위와 같은 상태를 만들어 보려고 했습니다. 만든 상태의 일부를 보여드리면...

문제는 제가 이걸 열심히 쓰면서도 이게 정말 될 거라고 생각한 것이 문제였습니다...

그래도 얻은 교훈이 있었습니다. 위의 상태들을 보면, 각 상태가 여러개의 상태들로 묶이는데 이 묶이는 방법이 현재까지 보았던 $1$의 개수 혹은 $0$의 개수와 관련이 있다는 것이었습니다.

80pts again

위의 상태를 이용한 복잡한 코드를 고쳤습니다.

누적합을 생각해서 $0$을 $-2$, $1$을 $+2$로 생각합시다. 최초 상태는 $+1$입니다. 이 때 $t$에서 수를 하나 뽑으면 누적합은 $-1, +1, -1, +1$과 같은 형태가 되며, $s$에서 수를 뽑으면 $0$을 $3$개 뽑은 경우 누적합이 $-6$, $1$을 $3$개 뽑은 경우 누적합이 $+6$이 됩니다. $s$와 $t$에서 뽑은 누적합의 합이 $-5$ 혹은 $+5$라는 것은 $s$에서 $0$ 혹은 $1$이 나왔다는 것을 의미하므로, $0$과 $1$에 해당하는 경우의 수 처리를 해 주고, $s$에 $-6$혹은 $+6$에 해당하는 상태를 원래대로 되돌려줬습니다. (현재 누적합에 $+6$, $-6$을 해줍니다.)

코드: https://oj.uz/submission/643418

92pts

이렇게 누적합으로 바꾸고서야 $3, 2$개 사용의 올바른 방법을 알았습니다.

앞까지 본 $1$의 개수가 $3$개라고 하고 누적합이 $5$인 시점에서 멈췄다고 하면, 현재 상태는 $+6 + (-1)$ 혹은 $+4 + (+1)$ 일 것입니다. 여기서 $+6$에 해당하는 값을 원래대로 되돌려 준다면 $+0 + (-1)$ 혹은 $(-2) + (+1)$이 나옵니다.

여기서 $t$의 진동만으로 나올 수 있는 값은 $+1, -1, -3$입니다. 즉 $0$과 $1$의 진동만으로 나올 수 없는 $+3$ 혹은 $-5$가 나온 경우에 $s$의 다음 수가 $0$ 혹은 $1$이라는 것을 알 수 있습니다. 그래서 $1$은 $2$개, $0$은 $3$개를 써 넣어야 합니다. 이를 종합하면, 이전에 써 있는 수와 같은 수를 다시 쓸 경우에는 해당 수를 $2$개, 다른 수를 쓸 경우에는 해당 수를 $3$개 써야합니다. 가장 앞에 있는 수는 상관 없이 $2$개만 써도 됩니다.

$D_i$가 $i$자리를 길이 $2$인 블럭과 길이 $3$인 블럭으로 채우는 경우의 수라고 했을 때, $D_i = D_{i-2} + D_{i-3}$ 점화식이 이후 표현 가능한 경우의 수가 몇 개인지 알려줍니다.

길이 $A$가 표현 가능한 경우의 수는 $2D_{A-2}$이고, $2(D_1 + \cdots + D_{150-2}) > 10^{18}$입니다. $m = 150$입니다.

코드: https://oj.uz/submission/643436

100pts

다음과 같은 두 가지 최적화를 거쳤습니다.

• $0$과 $1$을 굳이 끝까지 쓸 필요 없고, 중간에 멈춰도 됩니다. 멈추는 방식은 $S$의 나머지 항을 $T$와 같은 방법으로 진동하게 만드는 것입니다($S$의 마지막 수의 반대 수를 계속 넣습니다.)
  • 표현 가능한 경우의 수는 $D_i = D_{i-2} + D_{i-3} + 1$이 되고, $2(D_1+ \cdots + D_{141-2}) > 10^{18}$입니다. $m = 141$입니다.
  • 코드: https://oj.uz/submission/643439
• 13점의 아이디어를 다시 가지고 옵시다. $s, t$의 가장 앞 두 수가 $0$이면 $0$, $1$이면 $1$입니다. 그렇기에 처음에 $s$를 $2$개 쓰는 것이 아닌 $1$개만 쓰고, $s$의 앞 글자에따라 $t$의 앞 글자도 맞춰주면 됩니다.
  • 이 경우, 길이 $A$가 표현 가능한 수가 $2D_{A-2}$에서 $2D_{A-1}$로 늘어나고, $m$이 $1$ 줄어서 $m = 140$이 됩니다.
  • 코드: https://oj.uz/submission/643445

위의 코드를 정리한 최종 코드는 다음과 같습니다: https://oj.uz/submission/643446

느낀 점

이 문제를 풀면서

• "나는 왜 이걸 하고 있지?"
• "바쁘다면서 사실 일 안하고 문제 생각만 하고 10시간 동안 하는거 보면 안 바쁜거 아닌가?"
• "나는 왜 안 바쁜데 바쁘다고 징징대지?"
• "난 왜 이렇게 나약하지? 난 좀 더 다른걸 열심히 해야하는 거 아닐까?"
• "해야 할 거 안하고 이런거나 하고 있다니 쓰레기야 우울해..."

같은 것들을 느꼈습니다.

혹시 너무 기분이 좋아서 조증이 온 경우 풀어보기 좋은 문제인 것 같습니다.