ARC135-C XOR to All

問題へのリンク

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("5");
            WillReturn.Add("1 2 3 4 5");
            //19
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("10 10 10 10 10");
            //50
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("3 1 4 1 5");
            //18
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        // Onの件数[2のべき乗]なDict
        var OnCntDict = new Dictionary<long, long>();

        // Offの件数[2のべき乗]なDict
        var OffCntDict = new Dictionary<long, long>();

        long MaxA = AArr.Max();
        for (long Loop2Beki = 1; Loop2Beki <= MaxA; Loop2Beki *= 2) {
            OnCntDict[Loop2Beki] = 0;
            OffCntDict[Loop2Beki] = 0;
            foreach (long EachA in AArr) {
                if ((EachA & Loop2Beki) > 0) {
                    OnCntDict[Loop2Beki]++;
                }
                else {
                    OffCntDict[Loop2Beki]++;
                }
            }
        }

        // 解候補を列挙
        var AnswerKouhoList = new List<long>();
        long DefaultVal = 0;
        foreach (var EachPair in OnCntDict) {
            DefaultVal += EachPair.Key * EachPair.Value;
        }
        AnswerKouhoList.Add(DefaultVal);

        foreach (long EachA in AArr) {
            long AnswerKouho = 0;
            for (long Loop2Beki = 1; Loop2Beki <= MaxA; Loop2Beki *= 2) {
                if ((EachA & Loop2Beki) > 0) {
                    AnswerKouho += Loop2Beki * OffCntDict[Loop2Beki];
                }
                else {
                    AnswerKouho += Loop2Beki * OnCntDict[Loop2Beki];
                }
            }
            AnswerKouhoList.Add(AnswerKouho);
        }
        Console.WriteLine(AnswerKouhoList.Max());
    }
}

解説

A B C D
があるとしてAとXORを取ると
0 (B XOR A) (C XOR A) (D XOR A)
になります。
次に、2項目の(B XOR A)とXORを取ると
(A XOR B) 0 (C XOR B) (D XOR B)
になるので、
2回以上XORを取るのは無駄と分かります。

よって、前処理で
ビットごとに0と件数と1の件数を求めておけば、TLEせずに解けます。