ABC 291 G — OR Sum

考察

ORはbitごとに独立で、あるbitのORが0なのは対応するA,Bのbitが両方0の位置だけである。

採用する候補: 補bit列の巡回相互相関を畳み込みで計算

Aを二周、Bを反転して畳み込めば全回転で両bitが0の個数が得られ、各bitのOR和を全shiftへ加算できる。

棄却する候補: 全N回転を一つずつ評価

各回転にN要素必要で二次時間になる。

巡回shift jの添字和は、二周した列と逆順列の通常畳み込みの係数N-1+jとして取り出せる。

各5bitについて補数化したA二周列と逆順B列を畳み込み、全shiftのOR個数N-c[N-1+j]を2^bit倍して得点へ加え、最大得点を選ぶ。

典型の発動条件

畳み込みによる相互相関

発動条件: 全shiftに対する二列の位置ごとの積和が必要になる。

一方を反転し、もう一方を二周して巡回相関を得る。

bit分解

発動条件: 値域が0..31で論理和に繰り上がりがない。

5bitを独立な0/1列として処理し2^b倍で合成する。

問題固有の要素

ORの1を直接数える代わりにDe Morganで「両方0」の相関を数えると積和になり、FFT/NTTへ接続できる。

別の問題へ持ち帰る視点: 論理演算の全shift集計は、補集合やbit分解で積和へ変形する。

正当性

ORが0の位置は当該bitの両列が0である位置だけなので、OR1個数はNからzero同士の対応数を引けばよい。Aを二周、Bを反転した畳み込みのN−1+j係数は巡回shift jの対応積和に等しい。5bitの重み2^bを足して全shiftの正確な得点を得るため、その最大が答えになる。

実装上の注意

  • Aの二周長2Nと反転Bの係数位置N-1+jを確認し、各shiftの得点は64ビットで持つ。

復習の核

  • 小さいNの全shift全評価と比較し、全0・全1、Nが変換長の境界付近、shift0とN-1を確認する。

計算量と制約

時間

O(N log N)。5bitそれぞれをNTT相関に変える。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 8 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 5\times 10^5; 0\leq A_i,B_i \leq 31; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

OR Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: NTT・FFTで畳み込みと相互相関を求める

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 畳み込み・相互相関

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: NTT・FFTで畳み込みと相互相関を求める

      • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。

      この解説で扱わないこと:

      • 組合せ解釈を必要とする生成関数の設計、および逆数・対数・指数などのFPS演算。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題