ARC174-B Bought Review

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            long[] ScoreArr = InputList[I].Split(' ').Select(pX => long.Parse(pX)).ToArray();
            long[] CostArr = InputList[I + 1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

            long Result = Solve(ScoreArr, CostArr);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long[] pScoreArr, long[] pCostArr)
    {
        long CostSum = 0;

        // 仮平均を3とし、差の総和
        long DiffSum = 0;

        DiffSum += (-2) * pScoreArr[0];
        DiffSum += (-1) * pScoreArr[1];
        DiffSum += (+1) * pScoreArr[3];
        DiffSum += (+2) * pScoreArr[4];

        if (DiffSum >= 0) return 0;

        long Rest = Math.Abs(DiffSum);

        // +2するのに、コストの安い方
        long BetterCost = Math.Min(pCostArr[3] * 2, pCostArr[4]);

        if (Rest >= 2) {
            long DivVal = Rest / 2;
            CostSum += BetterCost * DivVal;
            Rest %= 2;
        }

        if (Rest == 1) {
            // +1か+2するのに、コストの安い方
            CostSum += Math.Min(pCostArr[3], pCostArr[4]);
        }

        return CostSum;
    }
}

解説

仮平均を星3とすれば、
星1を-2
星2を-1
星3を0
星4を+1
星5を+2
として、総和を0以上にする最小コストを求める問題に帰着できます。