ABC 348 F — Oddly Similar

考察

pair(i,j)について一致column数の偶奇だけが必要なので、columnごとの「同じ値groupに属するpair」という0/1寄与をXORで累積できる。N行分のparity vectorをbitsetとして同時更新する。

採用する候補: 各column・値groupのrow maskを作り、該当rowのparity bitsetへXORする

棄却する候補: 全row pairについてM列を比較する

O(N²M)=8×10^9比較となり時間制限に厳しい。

N個のdynamic bitset parityを0初期化する。各column kでA_{i,k}を値1…999ごとにrow bitmaskへまとめ、各groupの全row iについてparity[i]へgroup maskをXORする。最後に各iでj>iのset bit数をpopcountして合計する。

典型の発動条件

bitset高速化

発動条件: 同じboolean演算をN個の対象へ繰り返し、N≤2000でword並列化できる。

row集合を64bit blocksで表しXOR・popcountをまとめて行う。

parityのXOR集計

発動条件: 一致回数そのものではなく奇偶だけが判定条件である。

各columnの一致indicatorをaddition mod 2としてXOR累積する。

問題固有の要素

値ごとにpairを列挙する代わりにgroup maskをgroup内の各rowへXORすると、group内完全graphの隣接vectorをbit並列で生成できる。

別の問題へ持ち帰る視点: 同値class内全pair更新はclass bitmaskを各memberのbitsetへbroadcastできる。

正当性

column kで値vを持つrow集合mask_vを作ると、その集合内の任意pairだけ一致数parityがtoggleされる。各i∈mask_vについてparity[i] xor=mask_vとすれば、全column後のbit jが1 iff i,jの一致列数がoddになる。 64 pair判定を一machine wordで並列化し、O(MN²/word_size)の実用時間に落とせる。

実装上の注意

  • diagonal(i,i)もM回toggleされ得るが必ず集計から除き、j>iだけ数える。columnごとのgroup maskは使い回す前にclearする。

復習の核

  • Mの偶奇でdiagonalが変わる例、全行同一、全値distinct、同じpairが複数列一致する例を三重loopと比較する。

計算量と制約

時間

O(M(N+V)⌈N/w⌉+MN)、w=64、Vは列ごとに初期化する値マスク数。maskを必要な値だけ初期化すればV≤N。

空間

O((N+N_V)⌈N/w⌉)語。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2000; 1 \leq M \leq 2000; 1 \leq A_{i,j} \leq 999; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Oddly Similar の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: bitsetで集合演算をword並列化する

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

      主タグ: bitsetによるword並列集合演算

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

      学習の位置

      体系上の位置: bitsetで集合演算をword並列化する

      • 集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。

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

      • 集合状態そのものを一つずつ遷移するbitmask DP、および単一整数のbit演算だけで完結する処理。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題