Magic Contest

길이가 $m$인 이진 문자열 $X$에 대해 다음 체크섬을 생각하자.

$$\sum_{i=1}^{m} iX_i\pmod{m+1}$$

체크섬이 $0$인 문자열들의 집합은 하나의 삽입 또는 삭제를 교정하는 Varshamov--Tenengolts 부호이다.

원문 길이가 $N$일 때, $2^r\geq N+r+1$을 만족하는 최소의 $r$을 고르고 $$로 둔다. 위치가 인 곳을 체크 비트로 비우고, 나머지 개 위치에 를 순서대로 넣는다.

데이터 비트가 만드는 체크섬을 $a$라 하자. $q=(-a)\bmod(m+1)$를 $0\leq q\leq m$인 정수로 잡는다. 이므로 의 이진 표현을 체크 비트 위치에 넣을 수 있다. 그러면 완성된 문자열의 체크섬은 이다.

$N\geq 3$이고 $N\leq 200\,000$이면 $r\leq 18$이고 $m\leq 2N$이다. 인 경우에는 각 비트를 두 번 반복한 문자열을 사용한다. 이 짧은 반복 부호도 삽입 하나를 교정할 수 있다. 따라서 앨리스는 항상 조건을 만족하고, 모든 에서 이므로 점을 얻는다.

밥이 받은 문자열의 길이는 $m+1$이다. 각 삭제 위치 $j$에 대해 그 문자를 삭제한 뒤의 체크섬을 계산하고, 체크섬이 $0$이 되는 위치를 찾는다. 삽입 하나를 교정하는 부호의 성질에 따라 복원되는 부호어는 유일하다. 모든 후보 체크섬은 가중 합과 접미사 1 개수를 이용해 전체 $O(m)$에 계산할 수 있다.

부호어를 복원한 뒤, 위치가 2의 거듭제곱이 아닌 문자만 순서대로 모으면 $S$를 얻는다.

각 실행의 시간 복잡도는 $O(\sum N_i)$이고, 보조 공간 복잡도는 $O(\max N_i)$이다. 체크섬 계산에서 필요한 가장 큰 정수는 이므로 부호 있는 64비트 정수 범위 안에 있다.

Solution written by GPT5