はじめに

競技プログラミング、AtCoder Beginner Contest 117
D - XXOR
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N個の非負整数A1,A2,...,ANおよび非負整数 Kが与えられます。
0以上K以下の整数 Xに対して、f(X)=(X XOR A1)+(X XOR A2)+...+(X XOR AN)とします。
ここで、非負整数 a,bに対して a XOR bは aとbのビットごとの排他的論理和を表します。
fの最大値を求めてください。

XORとは？

整数A,Bのビットごとの排他的論理和Xは、以下のように定義されます。
Xを二進表記した際の 2k(k≥0) の位の数は、
A,Bを二進表記した際の2kの位の数のうち一方のみが1であれば1、そうでなければ0である。
例えば、3 XOR 5=6となります (二進数表記すると:011 XOR 101=110)。

制約

入力は全て整数である
・1≤N≤10^5
・0≤K≤10^12
・0≤Ai≤10^12

入力

入力は以下の形式で標準入力から与えられる。

N K
A1 A2 ... AN

出力

fの最大値を出力せよ。

解き方

こちらの解き方を参考にしています。 goo.gl

①fを最大にするXを考える

fは、
N個の非負整数A1,A2,...,ANと
0以上K以下の整数 Xの
ビットごとの排他的論理和の
和である。

そのため
N個の非負整数A1,A2,...,ANと
ビットごとの排他的論理和をとったときに
全体の和が最大になるような値を選ぶ必要がある。

ビットごとの排他的論理和をとるので
Xの値はN個の非負整数A1,A2,...,ANを
二進数になおした値で考えていく必要がある。

例えば、入力例1を二進数になおすと以下のようになる。
入力例1

3 7
1 6 3

二進数

1→001
6→110
3→011

ここからXに何をとれば
各数字のXORの和が最大になるかを考える。

XORは0に1をあてると1にひっくり返るので
0が多い桁を1にすると
XORをとったときに大きい値を得ることができる。

0 XOR 1 = 1

また、2進数は10進数になおすと左に進むごとに2^Nの意味をもつ。

2^2 2^1 2^0
  0   0   1

これをもとにあらためて
2進数になおした上の数字を見ていくと以下のようになる。

2^2 2^1 2^0
  0   0   1
  1   1   0
  0   1   1

左の桁から考えていくと、
2²の桁に0が2つあるので
Xの2²の桁を1にすれば
XORをとったとき
2²×2 数が得られる。

2¹の桁は
0が1つしかないので
Xの2¹の桁を1にしても
2¹×1しか数が得られない。

逆に
1が2つあるので
Xの2¹の桁を0にすれば
2¹×2を得ることができる。

同じように2⁰の桁についても考える。
こちらも2¹の桁と同じように
0が1つしかなく1が2つあるので
Xの2⁰桁は0をとったほうが
XORで大きい値を得られる。

2^2 2^1 2^0
  0   0   1
  1   1   0
  0   1   1

X 1   0   0

この際、
Xは0以上K以下という条件に注意しなければならない。
KよりXが大きくなりそうであれば
見ている桁を1にすることをやめる必要がある。

この部分のコードを書くと以下のようになる。
・各桁で1になっている箇所を保存

        //各桁で1になっている箇所の数を保存する
        //XはKよりも大きくはならないので、Kの最大の桁までを保存する
        var length = (long)Math.Log(K, 2);
        var count = new int[length + 1];
        var bit = 1L;
        for (int i = 0; i <= length; ++i)
        {
            for (long j = 0; j < N; ++j) if ((bit & A[j]) != 0) count[i]++;
            bit <<= 1;
        }

・Xを求める

        bit = 1L;
        //大きい桁から考える
        bit <<= (int)length;
        //X
        var X = 0L;
        var temp = 0L;
        //大きい桁から順番に1にするかどうかを決める
        for (long i = length; 0 <= i; --i)
        {
            //A全体の数の半分以上が0であればビットを立てる
            if (count[i] < ((N + 1) / 2)) temp |= bit;
            //K以下であればXがとれる値なのでXに代入
            if (temp <= K) X = temp;
            //Kよりも大きければXはとれない値なのでK以下の状態に戻す
            else temp = X;
            //次の桁に進む
            bit >>= 1;
        }

A全体でビットが立っている（＝1である）数が
半分より少ない場合にXのビットを立てる（＝1）としている。
（この考え方でACが出るが、
下のビットを立てたほうが有利なパターンが全くないのか
それとも、たまたま今回は
これでも大丈夫だったのかは分かりませんでした。）

また桁が大きいほうから考えているのは、
K＝8
A＝{7,3,3}
というようなケースで上の桁から決めないと
Xで間違った値が出てきてしまうからである。

②求めたXとAをXORした和を求める

Xと各AiをXORした和を求める

        var ans = 0L;
        for (int i = 0; i < N; ++i) ans += (X ^ A[i]);

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Dmondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var N = line[0];
        var K = line[1];
        var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        //Kが0のときはそののまま和を出力
        if (K == 0)
        {
            Console.WriteLine(A.Sum(x => x));
            return;
        }
        //各桁で1になっている箇所の数を保存する
        //XはKよりも大きくはならないので、Kの最大の桁までを保存する
        var length = (long)Math.Log(K, 2);
        var count = new int[length + 1];
        var bit = 1L;
        for (int i = 0; i <= length; ++i)
        {
            //ビットが立っているものをカウント
            for (long j = 0; j < N; ++j) if ((bit & A[j]) != 0) count[i]++;
            //次の桁に進む
            bit <<= 1;
        }
        bit = 1L;
        //大きい桁から考える
        bit <<= (int)length;
        //X
        var X = 0L;
        var temp = 0L;
        //大きい桁から順番に1にするかどうかを決める
        for (long i = length; 0 <= i; --i)
        {
            //A全体の数の半分以上が0であればビットを立てる
            if (count[i] < ((N + 1) / 2)) temp |= bit;
            //K以下であればXがとれる値なのでXに代入
            if (temp <= K) X = temp;
            //Kよりも大きければXはとれない値なのでK以下の状態に戻す
            else temp = X;
            //次の桁に進む
            bit >>= 1;
        }
        //Xと各AiをXORした和を求める
        var ans = 0L;
        for (int i = 0; i < N; ++i) ans += (X ^ A[i]);
        Console.WriteLine(ans);
    }
}