AtCoder Beginner Contest 117 D - XXOR 解説

感想

桁DP（じゃないけど）初めて書いた、、、

問題

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

思考過程

• bit毎に見ていきそう。K以下であるという条件がなかったら簡単なのにな…
• おそらく桁DPみたいなことをしたらうまくいきそう。

実装

• 実装をするにあたって、普通にDPで書くと頭がバグるので、再帰で書いてみる。
• 着目したbit以下、Kに「縛られてる」状態をtrue、「縛られてない」状態をfalseで引数に持たせた。
• 「縛られてる」というのは、無作為に値を選ぶとKを超える可能性があるから注意する必要があるということ。

例えば、K=1001001 (=73)のときに、比較対象の数が上から2bitだけ決まってるとして、L = 10*****であったとしてみる。
すると、もし上から3bit目を1にするとL > Kとなってしまうので、ここのbitは0にせざるを得ない。
このような「Kを超えてしまう可能性があるから値に制約があること」を「縛り」と呼ぶことにする。

void solve(ll bit,ll sum,bool flag){
	if(bit == -1){
		//最後の桁まで見終わったら、答えを更新
		ans = max(ans,sum);
		return;
	}
	if(flag){
		//縛られてる
		if(k & (1ll << bit)){
			//Kにbitがたってる

			//bitをたてる場合は、縛られてるまま下の桁へ
                        //XORをとるので、立ってないbitの総和をとることに注意
			solve(bit-1,sum + dp[1][bit],true);

                        //bitをおろす場合は、縛りを解除して下の桁へ
			solve(bit-1,sum + dp[0][bit],false);
		}else{
			//Kにbitがたってない
			//この場合はbitをおろすしかない
			//縛りもそのまま
			solve(bit-1,sum + dp[0][bit],true);
		}
	}else{
		//すでに縛られてないので、この桁は好きにしていい
		solve(bit-1,ans + max(dp[0][bit],dp[1][bit]),false);
	}
	return;
}

int main(){
	for(i=0;i<n;i++){
		for(j=0;j<=60;j++){
			if(x[i] & (1ll << j)){
                                //立っているbitの分の総和
				dp[0][j] += (1ll << j);
			}else{
                                //立ってないbitの分の総和
				dp[1][j] += (1ll << j);
			}
		}
	}
	solve(60,0,true);
	p(ans);
	return 0;
}