ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC117 D - XXOR

問題
提出コード

解法

2進数の桁DPです。
dp[i][j][k]としたとき、iは現在見ている桁を表し、下からi+1桁目、ji桁目で0を使うか1を使うか、kは桁DPで毎回出てくる、K以下が確定しているかどうか、です。
今回は、iが大きい方から見ていきます。そして、現時点での答え、すなわち最大値を格納していきます。
答えはdp[0][j][k]です。
前計算として、N個の数字Aについて、i桁目が1である個数を計算しておきます。これをc_{i}とします。
遷移をざっと書きます。
Ki桁目が1だった場合
dp[i][0][1] = max(dp[i+1][j][k]) +c_{i} \times 2^{i}
dp[i][1][k] = max(dp[i+1][j][k]) + (N-c_{i})\times 2^{i}
となります。対して、
Ki桁目が0だった場合
dp[i][0][k] = max(dp[i+1][j][k]) + c_{i} \times 2^{i}
dp[i][1][1] = max(dp[i+1][j][1]) + (N-c_{i}) \times 2^{i}
です。ここで、注意すべき点がいくつかあります。
まず、DPを開始する地点です。Kより大きい最小の2^{i}ではなく、AKの最大値より大きい、最小の2^{i}になります。これはサンプルの3でわかります。
そして、これにより、Ki桁目が1だった場合のdp[i][1][1]は、DPの開始直後のiだった場合は計算してはいけません。同様に、Ki桁目が0だった場合も、2^{i} \leqq Kでないと、dp[i][j][1]の遷移を行ってはいけません。どちらのパターンも、まだK以下とは確定していないからです。
あとは、このDPを計算すれば、答えを求めることができます。