[AtCoder] ABC117 D – XXOR

XXOR

https://atcoder.jp/contests/abc117/tasks/abc117_d

考え方

題意

\( f(x) = (x \ \mathrm{XOR} \ A_1) + (x \ \mathrm{XOR} \ A_2) + \cdots + (x \ \mathrm{XOR} \ A_n) \ (0 \leq x \leq k)\)

の最大値を求めます。

方針

\( \mathrm{XOR} \) の性質を調べると、\( x \ \mathrm{XOR} \ y \) の計算は二進数で表記したときの各ビットを比較して、\( i \) ビット目が \( 0 \) と \( 1 \) のとき、計算結果の \( i \) ビット目は \( 1\) となります。逆に、\( 1 \) と \( 1 \) 又は、\( 0 \) と \( 0 \) のとき、\( 0 \) になります。

各ビットの \( 1 \) の個数をカウントする

配列 \( A \) を二進数に変換し、各ビットの \( 1 \) が現れた個数を数え上げます。配列 \( c \) の要素を次のように定義します。 \( c_i \) を \( i \) ビット目に現れた \( 1 \) の個数とします。どのようにしてこのような値を数え上げるかというと、二進数を \( t \) 桁で表記し、上位のビットの左側を \( 0 \) で埋めます。

例えば、\( 2 \) を二進数で表現すると、\( 10 \) ですが、\( 4 \) 桁で表記すると、\( 0010\) となります。このように表すと、全ての \( A \) の二進数表記の文字列の長さが同じになるので、直感的にカウントしやすくなると思います。また、\( c_i \) を \( t – i\) ビット目の \( 1 \) の個数と表すのが自然かと思います。

動的計画法

上位ビットから下位ビットへと考えていきます。

\( c_i \) を \( t – i\) ビット目の \( 1 \) の個数と表すとします。

\( f(x)\) の値は \( x \) のビット毎に計算しても求めることができます。つまり、\( x \) の \( i \) のビット目を\( j \ ( = 0, 1)\) としたときに得られる値の和が \( f (x) \) であるということです。具体的には、\( x \) の \( i \) ビット目が \( 0 \) のときの値は \( 2^{t – i – 1}c_{i} \) となり、\( 1 \) のときの値は \( 2^{t – i – 1}(n – c_{i}) \)

\( dp[i][0] \) を \( i \) ビット目まで見たときの、\( x \) が \( k \) 未満の値のときの \( f(x) \) の最大値とします。

\( dp[i][0] \) を \( i \) ビット目まで見たときの、\( x \) が \( k \) と \( i \) ビット目まで一致しているときの \( f(x) \) の最大値とします。

初期値を\( dp[0][0] = 0 \) とし、それ以外は \( dp[\cdot][\cdot] = -1 \) とします。

どのように更新していくかはコードを見た方が分かりやすいと思います。

コード

感想

桁に関する動的計画法を初めて使ったので、難しかったです。動的計画法をもっと勉強しないといけないと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする