AGC-012-A AtCoder Group Contest

■■■問題■■■

AtCoder Group Contestの参加者に 3N 人が参加します。
i番目の参加者の強さは整数 ai で表されます。
参加者が3人1組となるようにチームをN組作ることにしました。
1人の参加者が複数のチームに所属することはできません。

チームの強さはチームメンバーの強さのうち2番目に大きい値で表されます。
例えば、強さが1,5,2のメンバーからなるチームの強さは2になり、
強さが3,2,3のメンバーからなるチームの強さは3になります。

N組のチームの強さの和としてありうる値のうち、最大の値を求めてください。

■■■入力■■■

N
a1 a2 ・・・ a3N

●1 <= N  <= 10万
●1 <= ai <= 10億
●ai は整数

■■■出力■■■

答えを出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input2";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("5 2 8 5 1 5");
            //10
            //例えば以下のようにチームを作ったとき、
            //チームの強さの和が最大となります。
            //●チーム 1：1,4,5 番目の参加者からなる。
            //●チーム 2：2,3,6 番目の参加者からなる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            var sb = new System.Text.StringBuilder();
            sb.Append("1000000000");
            for (int I = 1; I <= 29; I++) sb.Append(" 1000000000");
            WillReturn.Add(sb.ToString());
            //10000000000
            //チームの強さの和は非常に大きくなることがあります
        }
        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[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        Array.Sort(AArr);

        long Answer = 0;
        int UB = AArr.GetUpperBound(0);
        for (int I = UB - 1; N <= I; I -= 2) {
            Answer += AArr[I];
        }
        Console.WriteLine(Answer);
    }
}

解説

N=3として、1から9までの9つの数で考えます。

1から9まで数を昇順にソートすると
1 2 3 4 5 6 7 8 9
となりますが、小さい順の3件である、1,2,3は3つのグループの最小値に使うのが最適です。

残りの
4 5 6 7 8 9
について考えると、9は、3つのグループでの最大値になり、
8は、そのグループの中央値に使うのが最適です。
なぜなら、
4 5 6 7 8
のどれを中央値に使っても、残る数字は、Row_Number関数で見れば同じですので、
最大値の8を中央値で使うのが、最善だからです。

残りの
4 5 6 7
についても、7は、残りの2グループでの最大値になり、
6は、そのグループの中央値に使うのが最適です。

残りの
4 5
についても、5は、残りの1グループでの最大値になり、
4は、そのグループの中央値に使うのが最適です。