blog.bouzuya.net

2022-05-31 ARC135 C を解いた / IS NULL でもインデックスが効く

ARC135 : AtCoder Regular Contest 135 の C - XOR to All https://atcoder.jp/contests/arc135/tasks/arc135_c を解いた。

提出: https://atcoder.jp/contests/arc135/submissions/32127862

解説 AC 。

まず 2 回以上の操作は不要である。 XOR は可換性を持ち、同じ値を逆元とすることから 2 回以上の操作はすべて打ち消されて最後に選んだ x 以外は無視しても良くなる。 N = 3 で仮に A_1 → A_2 と選んだ際の変化で確かめる。

A_1                    , A_2                  , A_3

-- A_1 を選択する
A_1 ⊕ A_1              , A_1 ⊕ A_2            , A_1 ⊕ A_3
-- A_1 ⊕ A_1 = 0
0                      , A_1 ⊕ A_2            , A_1 ⊕ A_3

-- A_2 (= A_1 ⊕ A_2) をさらに選択する
A_1 ⊕ A_2              , A_1 ⊕ A_2 ⊕ A_1 ⊕ A_2, A_1 ⊕ A_3 ⊕ A_1 ⊕ A_2
-- A_1 ⊕ A_2 ⊕ A_1 ⊕ A_2 = 0 で A_1 ⊕ A_3 ⊕ A_1 ⊕ A_2 = A_2 ⊕ A_3
A_1 ⊕ A_2              , 0                    , A_3 ⊕ A_2
-- この結果は初期状態から A_2 を選んだときと変わらない

あとはどれを選んだときに総和が最大になるのかを確かめる必要がある。 愚直に 1 個ごとに全体を走査して計算すると O(N^2) で間に合わない。

そこで各ビット (2 進法で見たときの位) に注目する。 x のある位のビットが 0 のとき A_i のその位のビットはそのままで 1 のときその位のビットを反転する。

つまり事前に各位のビットの個数を数えておけば 0 なら (1 の個数) * 2^{位} 1 なら (N - 1 の個数) * 2^{位} の和で総和を求められる。 これで O(N log 2^30) 程度で求められる。

ずっと SQL での IS NULL にはインデックスが効かないと思い込んでいた。 PostgreSQL などでは普通に効くらしい。 https://www.postgresql.jp/document/13/html/indexes-types.html

「思い込みって良くないな。知識を更新していかないといけないな」と思った。

ただ NULL の設定可能な列を追加する設計はあまりしていない。 kawasima さんのイミュータブルデータモデル (https://scrapbox.io/kawasima/%E3%82%A4%E3%83%9F%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%96%E3%83%AB%E3%83%87%E3%83%BC%E3%82%BF%E3%83%A2%E3%83%87%E3%83%AB) に出てくる「イベント」の日時項目などがそうなのだけどデータの発生タイミングごとにテーブルを別にすることが多いので。この辺の話はまた別で書くかもしれない。

bouzuya/rust-sandbox の bex 0.1.1 をつくった。

bex open の残骸を削除した。テストを追加した。

ずっと使っていた GitHub のマグが割れた。すこし悲しい。

今日のコミット。