Tenka1 Programmer Beginner Contest-D：IntegerotS

問題

ある数 k と n つの組 (a_i, b_i) が与えられる。n つの組からいくつか a_i を選び、価値の総和を \displaystyle \sum b_i とする。選んだそれぞれの a_i の or が k を超えないようにするとき、価値の最大値を求めよ。

考え方

満たすべき条件について考える。条件は「選んだ a_i の or が k 以下にならなければならない」ということである。or をとったときに k 以下になる数について考える。

例えば k = 0011010(2) とすると、or をとったときの k 以下になる数の候補としては、

  • 0011010(2)
  • 0001111(2)
  • 0010111(2)
  • 0011001(2)

である。つまり k の i ビット目が 1 であるとき、 i ビット目を 0 として i-1 ビット目以降を 1 とした数が候補となる。すべての候補になりうる数について、各 a_i との or をとって条件を満たす価値の総和を求めればよい。

Submission #3428078 - Tenka1 Programmer Beginner Contest

ポイント

  • 条件を満たす場合について考える

類題