ARC124-B XOR Matching 2

問題へのリンク

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");
            WillReturn.Add("6 4 7");
            //1
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("0 1");
            WillReturn.Add("0 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("24");
            WillReturn.Add("14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481");
            WillReturn.Add("805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010");
            //8
            //107543995
            //129376201
            //139205201
            //160626723
            //312334911
            //323172429
            //481902037
            //493346727
        }
        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();
        int[] BArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        Array.Sort(AArr);
        int UB = AArr.GetUpperBound(0);

        // Xの候補をHashSetに格納
        var XSet = new HashSet<int>();
        foreach (int EachB in BArr) {
            XSet.Add(AArr[0] ^ EachB);
        }

        foreach (int EachX in XSet.ToArray()) {
            var BList = new List<int>();
            foreach (int EachB in BArr) {
                BList.Add(EachX ^ EachB);
            }
            BList.Sort();

            if (AArr.SequenceEqual(BList) == false) {
                XSet.Remove(EachX);
            }
        }

        Console.WriteLine(XSet.Count);
        foreach (int EachX in XSet.OrderBy(pX => pX)) {
            Console.WriteLine(EachX);
        }
    }
}

解説

最初にXの候補を列挙します。

次に下記の連立方程式を考えます。
a1 XOR b1 = X
a2 XOR b2 = X
a3 XOR b3 = X

移項して変形が可能です。
a1 = X XOR b1
a2 = X XOR b2
a3 = X XOR b3

以上により
aの集合と
(X XOR bの各要素) の集合
が等しいかを調べれば良いと分かります。