問題

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

考え方

考えていた解法(貪欲)

bitのXORを考える問題なので、bitの桁ごとに考えていこう。bitごとに独立して考えることができる。 $f(X)$ について $X \le K$ という制約がなければ本当にbitごとに上から貪欲でOK。ただし $X \le K$ であるから少し工夫が必要である。

まず各bitごとに $\{A_N\}$ に含まれる $0$ or $1$ のbitの個数を求めよう。上位 $i$ 桁目のビットが $1$ である個数を $cnt_1$ とする。そのとき $X$ の上位 $i$ 桁目のbitが $1$ であれば、 $x = max(cnt_1, n - cnt_1)$ を選択できる。そうでなく $X$ の上位 $i$ 桁目のbitが $0$ であれば $x = cnt_1$ を選ぶしかない。このようにして数を選んだときの和 $\sum 2^i * x$ が解の一つである。

次に $K$ 未満の数で各桁のbitがなるべく多くなる数の集合を求めよう。つまり $11010110_{(2)}, 214_{(10)}$ と表される数を考えると

$01111111_{(2)}, 127_{(10)}$
$10111111_{(2)}, 191_{(10)}$
$11001111_{(2)}, 207_{(10)}$
$11010011_{(2)}, 211_{(10)}$
$11010101_{(2)}, 213_{(10)}$

が候補になる。これらの数は上位 $i$ 桁目のbitが $1$ である場合のみ考えればよいので高々 $logK$ 個である。

あとは候補になる数それぞれについて実際に計算して最大値を求めれば良い。

Submission #4169898 - AtCoder Beginner Contest 117

別解(桁DP)

$dp[d][tight] :=$ 上位 $d$ 桁目まで見て、今の桁まで $K$ ぴったり(tight=1)かどうかの場合の最大値

とする。ぴったりでない場合はゆるい(tight=0)と表現することとする。桁DPは基本的に

ぴったり → ぴったり
ぴったり → ゆるい
ゆるい → ゆるい

の3通りの遷移のみを考えれば良い。(実際はこの問題は $d$ 桁目が 0 の場合と 1 の場合で場合分けするが本質ではない)

よって $d=50$ 程度の数から順番に桁ごとの最大値を求めればよい。 $max(dp[0][0], dp[0][1])$ が解となる。

Submission #4174488 - AtCoder Beginner Contest 117

どこに着目して考察するべきだったか

$K$ を超えないような数とXORを取る、ということを考えることが重要。

何がバグっていたか

ある数以下のビットの組み合わせの実装がバグっていた。以下のようにすればよい。

List<Long> list = new ArrayList<>();
for (int i = 50; i >= 0; i--) {
    long tmp = k;
    if ((tmp >> i & 1) == 1) {
        tmp -= 1L << i;
        tmp |= ((1L << i) - 1);
        list.add(tmp);
    }
}