D - Popcount and XOR Editorial by miscalculation53
次の手順で答えを求めることができます。
- \(X\) と \(Y\) を \(0\) で初期化する。
- \(C\) の立っている bit をすべて調べる。各 bit について、\(X\) と \(Y\) のうち、popcount が目標数により足りない方のその bit を立てる。
- \(C\) の立っていない bit をすべて調べる。目標が達成されていない限り、そのような bit を \(X, Y\) の両方で立てる。
- ここまでで目標が達成されていれば \(X, Y\) が解であり、達成されていなければ解は存在しない。
正当性を示します。\(A = a - \mathrm{popcount}(X), B = b - \mathrm{popcount}(Y)\)とします。\(A, B\) は「その時点で、\(X\) や \(Y\) の popcount が目標数にどれだけ足りないか」を表します。目標は、\(A = B = 0\) とすることです。
ここで次の事実が重要です。
\(C\) の立っている bit をひとつ確定させるたびに、\(A + B\) の値は必ず \(1\) 減る。そのため、\(C\) の立っている bit をすべて確定させた時点での \(A + B\) の値は、それらの bit の決め方によらない。
\(C\) の立っていない bit を変化させても、\(A - B\) の値は変化しない。
2. より、\(C\) の立っている bit をすべて確定させた時点で、\(A = B\) となっていなければなりません。さらに 1. より、\(A = B\) となってさえいれば、どのように決めても目標達成の可否に影響しません。(\(A = B = 0 \iff A+B = A-B = 0\) に注意してください。)
したがって、\(C\) の立っている bit を決めるパートで、\(|A - B|\) を最小化するように決めていけばよいです。
posted:
last update: