第6回PAST H カンカンマート

問題へのリンク

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 3 2 10");
            WillReturn.Add("15 1");
            WillReturn.Add("25 0");
            WillReturn.Add("20 0");
            WillReturn.Add("10 1");
            WillReturn.Add("5 1");
            WillReturn.Add("20 0");
            //45
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 2 5 40");
            WillReturn.Add("120 0");
            WillReturn.Add("1 1");
            WillReturn.Add("90 0");
            WillReturn.Add("10 0");
            WillReturn.Add("50 0");
            //51
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("16 9 1 631593942");
            WillReturn.Add("758234071 1");
            WillReturn.Add("872232933 0");
            WillReturn.Add("928146137 0");
            WillReturn.Add("141777768 0");
            WillReturn.Add("339097211 1");
            WillReturn.Add("590423762 1");
            WillReturn.Add("656886697 1");
            WillReturn.Add("164443392 0");
            WillReturn.Add("181259343 0");
            WillReturn.Add("509224290 0");
            WillReturn.Add("973377384 0");
            WillReturn.Add("934014075 1");
            WillReturn.Add("167877698 1");
            WillReturn.Add("549037938 0");
            WillReturn.Add("94228809 1");
            WillReturn.Add("898548470 0");
            //4841818525
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        SplitAct(InputList[0]);
        long M = wkArr[1];
        long K = wkArr[2];
        long Q = wkArr[3];

        var T0List = new List<long>();
        var T1List = new List<long>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            if (wkArr[1] == 0) T0List.Add(wkArr[0]);
            if (wkArr[1] == 1) T1List.Add(wkArr[0]);
        }
        // 昇順にソート
        T0List.Sort();
        T1List.Sort();

        // 累積和を設定
        for (int I = 1; I <= T0List.Count - 1; I++) {
            T0List[I] += T0List[I - 1];
        }
        for (int I = 1; I <= T1List.Count - 1; I++) {
            T1List[I] += T1List[I - 1];
        }

        // T0からの取得数を全探索
        long Answer = long.MaxValue;
        for (int I = 0; I <= Math.Min(M, T0List.Count); I++) {
            long AnswerKouho = 0;
            if (I > 0) {
                AnswerKouho += T0List[I - 1];
            }

            long Rest = M - I;
            if (Rest > T1List.Count) continue;
            if (Rest > 0) {
                AnswerKouho += T1List[(int)(Rest - 1)];

                // 必要な缶切りの数
                long NeedKankiriCnt = Rest / K;
                if (Rest % K > 0) NeedKankiriCnt++;

                AnswerKouho += NeedKankiriCnt * Q;
            }
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }
}

解説

缶切りが不要な缶詰から何個選ぶかを全探索してます。

選んだ個数を決めた後の、
総和の計算を高速化するために、前処理で累積和を求めてます。