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

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

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

データを送ろう

問題に戻る

解説

長さ7のハミング符号を使い、左から位置を1始まりで数える。原文の四ビットを順に 3,5,6,73,5,6,73,5,6,7 番目へ置く。

この四位置のうちビットが1である位置番号をすべてXORした値を xxx とする。x=(b2b1b0)2x=(b_2b_1b_0)_2x=(b2​b1​b0​)2​ と表し、1,2,41,2,41,2,4 番目へそれぞれ b0,b1,b2b_0,b_1,b_2b0​,b1​,b2​ を置く。完成した文字列の1の位置番号をすべてXORすると x⊕x=0x\oplus x=0x⊕x=0 になる。

通信中に kkk 番目が反転したとする。受信文字列の1の位置番号のXORには kkk が一回加わるか消えるため、結果はちょうど kkk である。そのビットを戻し、3,5,6,73,5,6,73,5,6,7 番目を読めばよい。必ず一ビットが反転するので、この戦略での受信時のXOR値は1以上7以下となる。

長さは常に7なので制約内である。検査ビット1,2,4が反転しても、データビット3,5,6,7が反転しても同じ手順で復元できる。

素朴な復元方法として、16通りの原文をすべて符号化し、受信文字列とちょうど一か所異なる符号語を探してもよい。異なる符号語の距離は3以上である。距離1なら検査XOR値が等しくならず、距離2なら異なる二つの位置番号のXORが0となる必要があり矛盾する。したがって候補は一意である。入力サイズは固定なので、素朴解法も全条件を通過する。

主解法の時間と追加領域は O(1)O(1)O(1)。素朴解法の比較回数は最大 16⋅7=11216\cdot7=11216⋅7=112 で、これも O(1)O(1)O(1)。位置のXOR値は最大7、原文の数値表現は最大15、8ビットのマスクは最大255なので、すべての整数計算は符号付き64ビットの範囲内である。

Solution written by GPT6