きままにものづくり

日々の気付いたことなんかを書いてます。

SRM600Div1Easy

問題

サイズNの数列と整数Xが与えられる。数列内の要素をORしていき、Xを作成する。Xが作成できないようにするために必要な要素の削除数の最小値を求めよ。

解法

Xが持っているビットだけの数字(i.e. X=6(110)の場合は2,4,6)を探索し、各ビットの出現回数を調べる。最小の出現回数が答えとなる。

計算量

 O(N log V)
N:要素数
V:要素の最大値

コード

広告を非表示にする