ABC281-F Xor Minimization

問題へのリンク

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");
            WillReturn.Add("12 18 11");
            //16
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("0 0 0 0 0 0 0 0 0 0");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("324097321 555675086 304655177 991244276 9980291");
            //805306368
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = GetSplitArr(InputList[1]);
        if (Array.TrueForAll(AArr, pX => pX == 0)) {
            Console.WriteLine(0);
            return;
        }
        Array.Sort(AArr);

        long MaxA = AArr.Max();

        long CurrBeki2 = 1;
        while (true) {
            if (CurrBeki2 * 2 < MaxA) {
                CurrBeki2 *= 2;
            }
            else {
                break;
            }
        }

        // 2べき値[レベル]なDcit
        var Beki2Dict = new Dictionary<long, long>();
        for (long I = 1; I < long.MaxValue; I++) {
            Beki2Dict[I] = CurrBeki2;
            CurrBeki2 /= 2;
            if (CurrBeki2 == 0) break;
        }
        long LevelLimit = Beki2Dict.Keys.Max();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.KouhoIndSta = 0;
        WillPush.KouhoIndEnd = AArr.GetUpperBound(0);
        WillPush.Level = 0;
        WillPush.CurrVal = 0;
        Stk.Push(WillPush);

        long Answer = long.MaxValue;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.Level == LevelLimit) {
                long CurrMax = long.MinValue;
                for (long I = Popped.KouhoIndSta; I <= Popped.KouhoIndEnd; I++) {
                    CurrMax = Math.Max(CurrMax, AArr[I] ^ Popped.CurrVal);
                }
                Answer = Math.Min(Answer, CurrMax);
                continue;
            }

            long NextLevel = Popped.Level + 1;
            long CurrBit = Beki2Dict[NextLevel];

            // ビットが2通りあるかを調べる
            var AppearBitSet = new HashSet<long>();
            for (long I = Popped.KouhoIndSta; I <= Popped.KouhoIndEnd; I++) {
                AppearBitSet.Add(AArr[I] & CurrBit);
            }

            if (AppearBitSet.Count == 1) {
                WillPush.KouhoIndSta = Popped.KouhoIndSta;
                WillPush.KouhoIndEnd = Popped.KouhoIndEnd;
                WillPush.Level = Popped.Level + 1;
                if (AppearBitSet.Max() == 0) {
                    WillPush.CurrVal = Popped.CurrVal;
                }
                else {
                    WillPush.CurrVal = Popped.CurrVal + CurrBit;
                }
                Stk.Push(WillPush);
                continue;
            }

            // このビットを0にする場合
            var IndList0 = new List<long>();
            for (long I = Popped.KouhoIndSta; I <= Popped.KouhoIndEnd; I++) {
                if ((AArr[I] & CurrBit) > 0) {
                    IndList0.Add(I);
                }
            }
            if (IndList0.Count > 0) {
                WillPush.KouhoIndSta = IndList0.Min();
                WillPush.KouhoIndEnd = IndList0.Max();
                WillPush.Level = Popped.Level + 1;
                WillPush.CurrVal = Popped.CurrVal;
                Stk.Push(WillPush);
            }

            // このビットを1にする場合
            var IndList1 = new List<long>();
            for (long I = Popped.KouhoIndSta; I <= Popped.KouhoIndEnd; I++) {
                if ((AArr[I] & CurrBit) == 0) {
                    IndList1.Add(I);
                }
            }
            if (IndList1.Count > 0) {
                WillPush.KouhoIndSta = IndList1.Min();
                WillPush.KouhoIndEnd = IndList1.Max();
                WillPush.Level = Popped.Level + 1;
                WillPush.CurrVal = Popped.CurrVal + CurrBit;
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal long KouhoIndSta;
        internal long KouhoIndEnd;
        internal long Level;
        internal long CurrVal;
    }
}

解説

まず対象の数列を昇順にソートします。

上位桁から桁ごとに見ていき、
その桁に0と1が混在するなら、両方を試す。
混在しないなら、そり小さくできるビットを採用する。

という方針でDFSで解いてます。