第1回PAST G 組分け

問題へのリンク

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

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];
        var ADict = new Dictionary<string, int>();

        for (int I = 1; I <= N - 1; I++) {
            wkArr = InputList[I].Split(' ').Select(X => int.Parse(X)).ToArray();
            for (int J = 0; J <= wkArr.GetUpperBound(0); J++) {
                string wkKey = string.Format("{0},{1}", I, I + 1 + J);
                ADict[wkKey] = wkArr[J];
            }
        }

        var GroupList = DeriveGroupList(N);

        int MaxScore = int.MinValue;
        foreach (JyoutaiDef EachGroup in GroupList) {
            int Score = 0;

            Action<List<int>> wkAct = (pList) =>
            {
                for (int I = 0; I <= pList.Count - 1; I++) {
                    for (int J = I + 1; J <= pList.Count - 1; J++) {
                        string wkKey = string.Format("{0},{1}", pList[I], pList[J]);
                        Score += ADict[wkKey];
                    }
                }
            };
            wkAct(EachGroup.Group1);
            wkAct(EachGroup.Group2);
            wkAct(EachGroup.Group3);

            if (MaxScore < Score) MaxScore = Score;
        }
        Console.WriteLine(MaxScore);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal List<int> Group1;
        internal List<int> Group2;
        internal List<int> Group3;
    }

    // 3つ以下のグループに配置して返す
    static List<JyoutaiDef> DeriveGroupList(int pN)
    {
        var WillReturn = new List<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.Group1 = new List<int>();
        WillPush.Group2 = new List<int>();
        WillPush.Group3 = new List<int>();

        var Stk = new Stack<JyoutaiDef>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.Level == pN) {
                WillReturn.Add(Popped);
                continue;
            }

            WillPush.Level = Popped.Level + 1;
            WillPush.Group1 = new List<int>(Popped.Group1) { Popped.Level + 1 };
            WillPush.Group2 = Popped.Group2;
            WillPush.Group3 = Popped.Group3;
            Stk.Push(WillPush);

            // 1人目は、必ずグループ1に配置する
            if (Popped.Level == 1) continue;

            WillPush.Group1 = Popped.Group1;
            WillPush.Group2 = new List<int>(Popped.Group2) { Popped.Level + 1 };
            WillPush.Group3 = Popped.Group3;
            Stk.Push(WillPush);

            WillPush.Group1 = Popped.Group1;
            WillPush.Group2 = Popped.Group2;
            WillPush.Group3 = new List<int>(Popped.Group3) { Popped.Level + 1 };
            Stk.Push(WillPush);
        }

        return WillReturn;
    }
}

解説

10人を最大で3グループに分けるので
場合の数は、3の9乗 = 19683 通り
ですので、DFSで全ての組合せを列挙してます。