ABC015-C 高橋くんのバグ探し

問題へのリンク

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 4");
            WillReturn.Add("1 3 5 17");
            WillReturn.Add("2 4 2 3");
            WillReturn.Add("1 3 2 9");
            //Found
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 3");
            WillReturn.Add("89 62 15");
            WillReturn.Add("44 36 17");
            WillReturn.Add("4 24 24");
            WillReturn.Add("25 98 99");
            WillReturn.Add("66 33 57");
            //Nothing
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            mTArrList.Add(EachStr.Split(' ').Select(pX => int.Parse(pX)).ToArray());
        }
        List<int[]> SelectedValArrList = ExecDFS();

        foreach (int[] EachSelectedValArr in SelectedValArrList) {
            //string[] WillOutArr = Array.ConvertAll(EachSelectedValArr, pX => pX.ToString());
            //Console.WriteLine(string.Join(",", WillOutArr));

            long XOR = EachSelectedValArr[0];
            for (int I = 1; I <= EachSelectedValArr.GetUpperBound(0); I++) {
                XOR ^= EachSelectedValArr[I];
            }

            if (XOR == 0) {
                Console.WriteLine("Found");
                return;
            }
        }
        Console.WriteLine("Nothing");
    }

    struct JyoutaiDef
    {
        internal List<int> SelectedValList;
        internal int CurrInd;
    }

    // 深さ優先探索で、選択値のListを返す
    static List<int[]> ExecDFS()
    {
        var WillReturn = new List<int[]>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.SelectedValList = new List<int>();
        WillPush.CurrInd = 0;
        Stk.Push(WillPush);

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

            if (Popped.CurrInd > mTArrList.Count - 1) {
                WillReturn.Add(Popped.SelectedValList.ToArray());
                continue;
            }
            for (int I = 0; I <= mTArrList[Popped.CurrInd].GetUpperBound(0); I++) {
                WillPush.SelectedValList = new List<int>(Popped.SelectedValList);
                WillPush.SelectedValList.Add(mTArrList[Popped.CurrInd][I]);
                WillPush.CurrInd = Popped.CurrInd + 1;
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

解説

深さ優先探索で、全ての選択肢の組合せを列挙してます。