1003 †

問題原文

問題 †

最大 10 億桁の 0，1 のビット列がある（ことになっている）．入力として，ある範囲における 1 の個数の偶奇（パリティ）が与えられる（ただし正しいとは限らない）．具体的にはこんな感じ．

1. ビット 1 からビット 2 まで 1 が偶数個．
2. ビット 3 からビット 4 まで 1 が奇数個．
3. ビット 5 からビット 6 まで 1 が偶数個．
4. ビット 1 からビット 6 まで 1 が偶数個．
5. ビット 7 からビット 10 まで 1 が奇数個．

ここで，上から何番目 Consistent な情報であるかを答える．たとえば上の例では 1. から 3. までは正しい可能性があるが，4. は明らかに嘘なので 3 と出力する．全部の情報が正しい可能性がある場合は与えられた情報の数（上の例では 5）を出力する．

解法 †

自然言語で記述するとややこしいのでエッセンスだけ．

たとえば上の例であれば

• 範囲 [1,2] が偶数個
• 範囲 [3,4] が奇数個
• 範囲 [5,6] が偶数個

というようなデータ構造を作る．ここでたとえば

• 範囲 [1,4] が偶数個
• 範囲 [3,4] が奇数個

というデータが与えられたら

• 範囲 [1,2] が奇数個
• 範囲 [3,4] が奇数個

というデータに改変する必要がある．

泉のプログラム †

1003.cpp