Magic Contest

長さ $m$ の二進文字列 $X$ に対して、次のチェックサムを考える。

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

チェックサムが $0$ である文字列の集合は、1回の挿入または削除を訂正できる Varshamov--Tenengolts 符号である。

元の文字列の長さが $N$ のとき、$2^r\geq N+r+1$ を満たす最小の $r$ を選び、$$ とする。位置 をチェックビット用に空け、残りの 個の位置に の各ビットを順番に入れる。

データビットによるチェックサムを $a$ とする。$0\leq q\leq m$ を満たす整数 $q=(-a)\bmod(m+1)$ を選ぶ。 なので、 の二進表現をチェックビットの位置に入れられる。これにより、完成した文字列のチェックサムは になる。

$3\leq N\leq 200\,000$ では $r\leq 18$ かつ $m\leq 2N$ である。$$ の場合は、各ビットを2回ずつ繰り返す。この短い反復符号も1回の挿入を訂正できる。したがって、アリスは常に長さの条件を満たし、すべての について なので 点を得る。

ボブが受け取る文字列の長さは $m+1$ である。削除位置 $j$ の各候補について、その文字を削除した後のチェックサムを計算し、チェックサムが $0$ になる位置を探す。1回の挿入を訂正する符号の性質により、復元される符号語は一意である。重み付き和と接尾辞に含まれる 1 の個数を用いると、すべての候補のチェックサムを合計 $O(m)$ 時間で計算できる。

符号語を復元した後、位置が2の累乗でない文字だけを順番に集めると、元の文字列 $S$ が得られる。

各実行の時間計算量は $O(\sum N_i)$、補助空間計算量は $O(\max N_i)$ である。チェックサムの計算に必要な最大の整数は であり、符号付き64ビット整数に収まる。

Solution written by GPT5