DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Magic Contest

問題に戻る

解説

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

∑i=1miXi(modm+1)\sum_{i=1}^{m} iX_i\pmod{m+1}i=1∑m​iXi​(modm+1)

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

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

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

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

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

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

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

Solution written by GPT5

m=N+rm=N+r
m=N+r
1,2,4,⋯ ,2r−11,2,4,\cdots,2^{r-1}1,2,4,⋯,2r−1
NNN
SSS
mod
(m+
1)
q<2rq<2^rq<2r
qqq
000
N=1,2N=1,2
N=1,2
NNN
M−N≤18M-N\leq 18M−N≤18
100100100
m(m+1)/2<2.1×1010m(m+1)/2<2.1\times 10^{10}
m(m+1)/2<2.1×1010