ABC317-D President

問題へのリンク

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("1");
            WillReturn.Add("3 8 1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("3 6 2");
            WillReturn.Add("1 8 5");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("3 4 2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("7 2 6");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            WillReturn.Add("1878 2089 16");
            WillReturn.Add("1982 1769 13");
            WillReturn.Add("2148 1601 14");
            WillReturn.Add("2189 2362 15");
            WillReturn.Add("2268 2279 16");
            WillReturn.Add("2394 2841 18");
            WillReturn.Add("2926 2971 20");
            WillReturn.Add("3091 2146 20");
            WillReturn.Add("3878 4685 38");
            WillReturn.Add("4504 4617 29");
            //86
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYZInfoDef
    {
        internal long X;
        internal long Y;
        internal long Z;
    }
    static List<XYZInfoDef> mXYZInfoList = new List<XYZInfoDef>();

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

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

        long ZSum = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.Z = wkArr[2];
            mXYZInfoList.Add(WillAdd);

            ZSum += WillAdd.Z;
        }

        // 既に取ってる議席数
        long CurrSeat = 0;
        for (int I = mXYZInfoList.Count - 1; 0 <= I; I--) {
            if (mXYZInfoList[I].X > mXYZInfoList[I].Y) {
                CurrSeat += mXYZInfoList[I].Z;
                mXYZInfoList.RemoveAt(I);
            }
        }

        // 最小コスト[現在の議席数]
        var PrevDP = new Dictionary<long, long>();
        PrevDP[CurrSeat] = 0;

        foreach (XYZInfoDef EachXYZ in mXYZInfoList) {
            long GoalVal = (EachXYZ.X + EachXYZ.Y) / 2 + 1;
            long NeedCost = GoalVal - EachXYZ.X;

            var CurrDP = new Dictionary<long, long>(PrevDP);
            foreach (var EachPair in PrevDP) {
                if (EachPair.Key >= ZSum / 2 + 1) continue;

                long NewKey = EachPair.Key + EachXYZ.Z;
                long NewVal = EachPair.Value + NeedCost;
                if (CurrDP.ContainsKey(NewKey)) {
                    if (CurrDP[NewKey] <= NewVal) {
                        continue;
                    }
                }
                CurrDP[NewKey] = NewVal;
            }
            PrevDP = CurrDP;
        }

        var AnswerKouho = new List<long>();
        foreach (var EachPair in PrevDP) {
            if (EachPair.Key >= ZSum / 2 + 1) {
                AnswerKouho.Add(EachPair.Value);
            }
        }
        Console.WriteLine(AnswerKouho.Min());
    }
}

解説

最小コスト[現在の議席数]
でDPしてます。

DPの計算量は、状態数 * 遷移数 です。
状態数は、制約により 100000 以下
遷移数は、制約により 100 * 2 以下
なので、
100000 * 200 以下で、
20000000となり間に合います。