ABC469-D The Big Two

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct ABInfoDef
    {
        internal long A;
        internal long B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long M = wkArr[1];

        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long A = wkArr[0];
            long B = wkArr[1];
            ABInfoDef WillAdd;
            WillAdd.A = A;
            WillAdd.B = B;
            mABInfoList.Add(WillAdd);
        }

        long Kouho1 = mABInfoList[0].A;
        long Kouho2 = mABInfoList[0].B;

        // 件数[ペアのハッシュ値]
        var PairCntDict = new Dictionary<long, long>();
        foreach (ABInfoDef ABInfoDef in mABInfoList) {
            long CurrHash = GetHash(ABInfoDef.A, ABInfoDef.B);
            if (PairCntDict.ContainsKey(CurrHash) == false) {
                PairCntDict[CurrHash] = 0;
            }
            PairCntDict[CurrHash]++;
        }

        // 件数[各値]
        long[] CntArr = new long[N + 1];
        foreach (ABInfoDef ABInfoDef in mABInfoList) {
            CntArr[ABInfoDef.A]++;
            CntArr[ABInfoDef.B]++;
        }

        var AnswerSet = new HashSet<long>();

        for (long I = 1; I <= N; I++) {
            if (I == Kouho1) continue;
            long OrCnt = CntArr[Kouho1] + CntArr[I];
            long CurrHash = GetHash(Kouho1, I);
            if (PairCntDict.ContainsKey(CurrHash)) {
                OrCnt -= PairCntDict[CurrHash];
            }
            if (OrCnt == M) {
                AnswerSet.Add(CurrHash);
            }
        }

        for (long I = 1; I <= N; I++) {
            if (I == Kouho2) continue;
            long OrCnt = CntArr[Kouho2] + CntArr[I];
            long CurrHash = GetHash(Kouho2, I);
            if (PairCntDict.ContainsKey(CurrHash)) {
                OrCnt -= PairCntDict[CurrHash];
            }
            if (OrCnt == M) {
                AnswerSet.Add(CurrHash);
            }
        }
        Console.WriteLine(AnswerSet.Count);
    }

    static long GetHash(long pA, long pB)
    {
        long Min = Math.Min(pA, pB);
        long Max = Math.Max(pA, pB);

        return Max * 1000000 + Min;
    }
}

解説

最初の1つ目の決勝にいるのが
必要条件なことをふまえて、候補なペアを減らし、

個数定理
n(AまたはB) = n(A) + n(B) - n(AかつB)
を使い

AまたはBが登場する決勝戦の数 = M
かで判定してます。