CODE FESTIVAL 2016予選C B K個のケーキ

■■■問題■■■

K個のケーキがあります。
高橋君は、1日に一つずつ、K日かけてこれらのケーキを食べようと考えています。
ケーキはT種類あり、種類i(1 <= i <= T)のケーキはai個あります。

二日連続で同じ種類のケーキを食べると飽きてしまうため、
高橋君は、うまくケーキを食べる順番を決めて、
前日と同じ種類のケーキを食べる日数を最小にしようと考えました。

高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。

■■■入力■■■

K T
a1 a2 ・・・ aT

●1 <= K <= 10000,1 <= T <= 100
●1 <= ai <= 100
●a1 + a2 + ・・・ + aT = K

■■■出力■■■

前日と同じ種類のケーキを食べる日数の最小値を出力せよ。

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("7 3");
            WillReturn.Add("3 2 2");
            //0
            //ケーキは7個あります。
            //例えば種類2,1,2,3,1,3,1の順で食べると
            //一度も前日と同じ種類のケーキを食べなくてすみます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3");
            WillReturn.Add("1 4 1");
            //1
            //ケーキは6個あります。
            //種類2,3,2,2,1,2の順で食べると
            //4日目だけ前日と同じ種類2のケーキを食べることになり、
            //これが最小になるので答えは1です。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 1");
            WillReturn.Add("100");
            //99
            //高橋君は一種類のケーキしか持っていないため、
            //2日目以降は毎日前日と同じ種類のケーキを食べるしかありません。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var wkDict = new Dictionary<int, int>();
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            wkDict.Add(I, AArr[I]);
        }

        int SameCnt = 0;
        int PrevKey = -1;

        while (wkDict.Count > 0) {
            //前日に選んでない中で、個数が最大の種類を選ぶ
            int MaxKey = -1;
            int MaxValue = -1;
            foreach (var EachPair in wkDict) {
                if (PrevKey == EachPair.Key) continue;

                if (EachPair.Value > MaxValue) {
                    MaxKey = EachPair.Key;
                    MaxValue = EachPair.Value;
                }
            }

            if (MaxKey == -1) {
                SameCnt++;
                if (--wkDict[PrevKey] == 0) wkDict.Remove(PrevKey);
            }
            else {
                if (--wkDict[MaxKey] == 0) wkDict.Remove(MaxKey);
                PrevKey = MaxKey;
            }
        }
        Console.WriteLine(SameCnt);
    }
}

解説

前日に選んでない中で、個数が最大の種類を選ぶ戦略を
シュミレーションしてます。