ABC236-D Dance

問題へのリンク

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("2");
            WillReturn.Add("4 0 1");
            WillReturn.Add("5 3");
            WillReturn.Add("2");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("5");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467");
            WillReturn.Add("369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136");
            WillReturn.Add("138172503 571268336 111747377 595746631 934427285 840101927 757856472");
            WillReturn.Add("655483844 580613112 445614713 607825444 252585196 725229185");
            WillReturn.Add("827291247 105489451 58628521 1032791417 152042357");
            WillReturn.Add("919691140 703307785 100772330 370415195");
            WillReturn.Add("666350287 691977663 987658020");
            WillReturn.Add("1039679956 218233643");
            WillReturn.Add("70938785");
            //1073289207
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int AllBitOn;
    static int mN2;

    static List<int[]> mScoreArrList = new List<int[]>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        mN2 = 2 * N;
        AllBitOn = (1 << mN2) - 1;

        for (int I = 1; I <= InputList.Count - 1; I++) {
            int[] wkArr = InputList[I].Split(' ').Select(pX => int.Parse(pX)).ToArray();
            mScoreArrList.Add(wkArr);
        }
        ExecDFS();
    }

    struct JyoutaiDef
    {
        internal int UseBitSet;
        internal int CurrXOR;
    }

    static void ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.UseBitSet = 0;
        WillPush.CurrXOR = 0;
        Stk.Push(WillPush);

        int Answer = int.MinValue;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // クリア判定
            if (Popped.UseBitSet == AllBitOn) {
                Answer = Math.Max(Answer, Popped.CurrXOR);
                continue;
            }

            // 未使用で最小番号を使う
            for (int I = 0; I <= mN2 - 1; I++) {
                int CurrBit1 = (1 << I);
                if ((Popped.UseBitSet & CurrBit1) > 0) continue;

                for (int J = I + 1; J <= mN2 - 1; J++) {
                    int CurrBit2 = (1 << J);
                    if ((Popped.UseBitSet & CurrBit2) > 0) continue;

                    WillPush.UseBitSet = Popped.UseBitSet;
                    WillPush.UseBitSet |= CurrBit1;
                    WillPush.UseBitSet |= CurrBit2;
                    int XOR = mScoreArrList[I][J - I - 1];
                    WillPush.CurrXOR = Popped.CurrXOR ^ XOR;
                    Stk.Push(WillPush);
                }
                break;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

使用した数を
HashSet<int>ではなく、
Int型でビット演算を使って管理し、
定数倍改善を行ってます。