ABC117 D - XXOR
解法
2進数の桁DPです。
としたとき、は現在見ている桁を表し、下から桁目、は桁目で0を使うか1を使うか、は桁DPで毎回出てくる、以下が確定しているかどうか、です。
今回は、が大きい方から見ていきます。そして、現時点での答え、すなわち最大値を格納していきます。
答えはです。
前計算として、個の数字について、桁目が1である個数を計算しておきます。これをとします。
遷移をざっと書きます。
の桁目がだった場合
となります。対して、
の桁目がだった場合
です。ここで、注意すべき点がいくつかあります。
まず、DPを開始する地点です。より大きい最小のではなく、との最大値より大きい、最小のになります。これはサンプルの3でわかります。
そして、これにより、の桁目がだった場合のは、DPの開始直後のだった場合は計算してはいけません。同様に、の桁目がだった場合も、でないと、の遷移を行ってはいけません。どちらのパターンも、まだ以下とは確定していないからです。
あとは、このDPを計算すれば、答えを求めることができます。