ABC171-E Red Scarf

問題へのリンク

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("4");
            WillReturn.Add("20 11 9 24");
            //26 5 7 22
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long SumXOR = 0;
        Array.ForEach(AArr, pX => SumXOR ^= pX);

        var AnswerList = new List<long>();
        foreach (long EachLong in AArr) {
            AnswerList.Add(SumXOR ^ EachLong);
        }

        string[] AnswerStrArr = Array.ConvertAll(AnswerList.ToArray(), pX => pX.ToString());
        Console.WriteLine(string.Join(" ", AnswerStrArr));
    }
}

解説

20 11 9 24
というサンプルで考えます。
B XOR C XOR D = 20
A XOR C XOR D = 11
A XOR B XOR D =  9
A XOR B XOR C = 24

未知数4つで式が4つの、連立方程式として考えます。

両方を全て足すと
左辺は、A.B.C.Dが3つずつ登場して、
XORでは、偶数回の同じ数の加算になるので
A XOR B XOR C XOR D = 20 XOR 11 XOR 9 XOR 24
になります。

B XOR C XOR D = 20
を両辺に足せば
A の値が求まります。

同様の方法で、他の未知数も分かります。