ABC117-D XXOR

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 7");
            WillReturn.Add("1 6 3");
            //14
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 9");
            WillReturn.Add("7 4 0 3");
            //46
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 0");
            WillReturn.Add("1000000000000");
            //1000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long K = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long MaxA = AArr.Max();

        // Nの桁数が少ない場合は、前ゼロを補完する
        string MaxABinStr = Convert.ToString(MaxA, 2);
        string KBinStr = Convert.ToString(K, 2);
        if (KBinStr.Length < MaxABinStr.Length) {
            KBinStr = KBinStr.PadLeft(MaxABinStr.Length, '0');
        }

        // ビットごとの集計を行う配列を作成
        int UB = KBinStr.Length - 1;

        // 対象桁に対応する、2のべき乗の配列
        long[] BekijyouArr = new long[UB + 1];
        long Base = 1;
        for (int I = UB; 0 <= I; I--) {
            BekijyouArr[I] = Base;
            Base *= 2;
        }

        // 対象桁ごとの、件数の配列
        long[] OnCntArr = new long[UB + 1];
        long[] OffCntArr = new long[UB + 1];
        for (int I = 0; I <= UB; I++) {
            foreach (long EachLong in AArr) {
                if ((EachLong & BekijyouArr[I]) > 0) {
                    OnCntArr[I]++;
                }
                else {
                    OffCntArr[I]++;
                }
            }
        }

        // 確定桁分の合計の最大値[数字自由フラグ]なDP表
        long?[] PrevDP = new long?[2];
        PrevDP[0] = 0;

        for (int I = 0; I <= UB; I++) {
            long?[] CurrDP = new long?[2];

            for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                if (PrevDP[J].HasValue == false) continue;

                for (int L = 0; L <= 1; L++) {
                    if (J == 0 && KBinStr[I] - '0' < L) continue;

                    int NewJ = J;
                    if (KBinStr[I] - '0' > L) NewJ = 1;

                    // 今の桁での確定分を足す
                    long AddVal = 0;

                    // 今の桁が0なら、XArrで1の件数 * 桁の重みを計上
                    if (L == 0) {
                        AddVal = OnCntArr[I] * BekijyouArr[I];
                    }

                    // 今の桁が1なら、XArrで0の件数 * 桁の重みを計上
                    if (L == 1) {
                        AddVal = OffCntArr[I] * BekijyouArr[I];
                    }

                    long NewVal = PrevDP[J].Value + AddVal;
                    if (CurrDP[NewJ].HasValue) {
                        CurrDP[NewJ] = Math.Max(CurrDP[NewJ].Value, NewVal);
                    }
                    else {
                        CurrDP[NewJ] = NewVal;
                    }
                }
            }

            //Console.WriteLine("{0}桁目のDP結果", I);
            //for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
            //    Console.WriteLine("CurrDP[{0}]={1}", J, CurrDP[J]);
            //}

            PrevDP = CurrDP;
        }

        long Answer = 0;
        for (int I = 0; I <= PrevDP.GetUpperBound(0); I++) {
            if (PrevDP[I].HasValue) {
                Answer = Math.Max(Answer, PrevDP[I].Value);
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

2進数で桁DPしてます。