ABC139-E League

問題へのリンク

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

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

        int N = int.Parse(InputList[0]);
        int RestMatchCnt = N * (N - 1) / 2;

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        var QueDict = new Dictionary<int, Queue<int>>();
        for (int I = 1; I <= InputList.Count - 1; I++) {
            SplitAct(InputList[I]);

            QueDict[I] = new Queue<int>(wkArr);
        }

        // 件数[試合のハッシュ値]な度数分布表
        var WaitMatchSet = new HashSet<int>();
        var WaitMatchCntDict = new Dictionary<int, int>();
        foreach (var EachPair in QueDict) {
            int Player1 = EachPair.Key;
            int Player2 = EachPair.Value.Dequeue();
            int Hash = GetHash(Player1, Player2);
            if (WaitMatchCntDict.ContainsKey(Hash) == false) {
                WaitMatchCntDict[Hash] = 0;
            }
            WaitMatchCntDict[Hash]++;
            if (WaitMatchCntDict[Hash] == 2) {
                WaitMatchSet.Add(Hash);
            }
        }

        int Days = 0;
        while (RestMatchCnt > 0) {
            if (WaitMatchSet.Count == 0) {
                Console.WriteLine(-1);
                return;
            }
            Days++;
            var ExceptSet = new HashSet<int>();
            foreach (int EachHash in WaitMatchSet.ToArray()) {
                int Player1 = EachHash % 10000;
                int Player2 = EachHash / 10000;
                if (ExceptSet.Contains(Player1)) continue;
                if (ExceptSet.Contains(Player2)) continue;
                ExceptSet.Add(Player1);
                ExceptSet.Add(Player2);

                //Console.WriteLine("{0}日目に{1}と{2}が試合します", Days, Player1, Player2);

                RestMatchCnt--;

                Action<int> DequeuAct = (pPlayer) =>
                {
                    if (QueDict[pPlayer].Count > 0) {
                        int Hash = GetHash(pPlayer, QueDict[pPlayer].Dequeue());
                        if (WaitMatchCntDict.ContainsKey(Hash) == false) {
                            WaitMatchCntDict[Hash] = 0;
                        }
                        WaitMatchCntDict[Hash]++;
                        if (WaitMatchCntDict[Hash] == 2) {
                            WaitMatchSet.Add(Hash);
                        }
                    }
                };
                DequeuAct(Player1);
                DequeuAct(Player2);

                WaitMatchSet.Remove(EachHash);
                WaitMatchCntDict.Remove(EachHash);
            }
        }
        Console.WriteLine(Days);
    }

    static int GetHash(int pA, int pB)
    {
        int Min = Math.Min(pA, pB);
        int Max = Math.Max(pA, pB);
        return Min * 10000 + Max;
    }
}

解説

次に行う対戦をQueueで管理しつつ、
可能になった対戦から、貪欲に進めてます。