AGC035-A XOR Circle

問題へのリンク

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("1 2 3");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 2 4 8");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[] mAArr;
    static int UB;

    static Dictionary<int, int> mCntDict = new Dictionary<int, int>();

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

        // 度数分布表を作成
        foreach (var EachItem in mAArr.GroupBy(pX => pX)) {
            mCntDict[EachItem.Key] = EachItem.Count();
        }

        // 値が4通り以上あったら、不可
        if (mCntDict.Count >= 4) {
            Console.WriteLine("No");
            return;
        }

        var AppearedSet = new HashSet<int>();

        for (int I = 1; I <= UB; I++) {
            if (AppearedSet.Add(mAArr[I]) == false) {
                continue;
            }
            bool Result = CanCreate(mAArr[0], mAArr[I]);
            if (Result) {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.WriteLine("No");
    }

    // 最初の2要素を引数として、矛盾しないCircleが作れるかを返す
    static bool CanCreate(int p1, int p2)
    {
        var CurrCntDict = new Dictionary<int, int>();
        IncrementCnt(CurrCntDict, p1);
        IncrementCnt(CurrCntDict, p2);

        int[] CircleArr = new int[UB + 1];
        CircleArr[0] = p1;
        CircleArr[1] = p2;
        for (int I = 2; I <= UB; I++) {
            int NewVal = CircleArr[I - 2] ^ CircleArr[I - 1];
            IncrementCnt(CurrCntDict, NewVal);
            if (mCntDict.ContainsKey(NewVal) == false) {
                return false;
            }
            if (mCntDict[NewVal] < CurrCntDict[NewVal]) {
                return false;
            }
            CircleArr[I] = NewVal;
        }

        if (CircleArr[UB] != (CircleArr[UB - 1] ^ CircleArr[0])) return false;
        if (CircleArr[0] != (CircleArr[UB] ^ CircleArr[1])) return false;
        return true;
    }

    static void IncrementCnt(Dictionary<int, int> pDict, int pKey)
    {
        if (pDict.ContainsKey(pKey) == false) {
            pDict[pKey] = 0;
        }
        pDict[pKey]++;
    }
}

解説

環状に並べるので、最初の1つめは固定して、
2個目に配置する値を全探索して、矛盾なく環状に配置できるかをチェック
すればいいです。

ただし、XORなので1個目と2個目が決まれば、
1個目 XOR 2個目 = 3個目
なので3個目が決まり、
2個目 XOR 3個目 = 4個目ですが
計算式を見ると、4個目 = 1個目と分かります。

同様に、
5個目 = 2個目
6個目 = 3個目
と分かります。
以上により、必要条件として、値をDistinctした結果が3以下であることが分かりました。

値の種類が、高々3以下になったので、
1個目を固定すれば、2個目は2通りしか候補がないため、
この2通りで、環状に配置できるかをチェックすれば、TLEせずに解くことができます。