ABC034-D 食塩水

問題へのリンク

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("3 2");
            WillReturn.Add("100 15");
            WillReturn.Add("300 20");
            WillReturn.Add("200 30");
            //25.000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct WaterDef
    {
        internal decimal Weight;
        internal decimal Salt;
    }

    static List<WaterDef> mWaterList = new List<WaterDef>();

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

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

        SplitAct(InputList[0]);
        int N = (int)wkArr[0];
        int K = (int)wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            WaterDef WillAdd;
            WillAdd.Weight = wkArr[0];
            WillAdd.Salt = wkArr[0] * wkArr[1] / 100M;
            mWaterList.Add(WillAdd);
        }
        Solve(K);
    }

    //2分法で解を求める
    static void Solve(int pK)
    {
        decimal L = 0;
        decimal R = 100M;
        decimal Mid = (L + R) / 2M;

        for (int I = 1; I <= 1000; I++) {
            decimal SaltSum = 0;
            decimal WeightSum = 0;

            // 貪欲法でK個選ぶ
            var Query = mWaterList.OrderByDescending(pX => pX.Salt - Mid * pX.Weight / 100).Take(pK);
            foreach (WaterDef EachWater in Query) {
                SaltSum += EachWater.Salt;
                WeightSum += EachWater.Weight;
            }

            // 食塩水の濃度
            decimal CurrRate = SaltSum / WeightSum * 100M;

            if (Mid < CurrRate) {
                L = Mid;
            }
            else {
                R = Mid;
            }
            Mid = (L + R) / 2M;
        }
        Console.WriteLine(Mid);
    }
}

解説

目標とする濃度をAとし、
目標を達成するには、

シグマ(塩) / シグマ(塩水) >= A / 100
の不等式が成立し、不等式を変形すると

シグマ(塩) >= A / 100 * シグマ(塩水)
シグマ(塩) - A / 100 * シグマ(塩水) >= 0
シグマ(塩) - シグマ(A / 100 * 塩水) >= 0
シグマ(塩 - A / 100 * 塩水) >= 0
となり、

塩 - A / 100 * 塩水
の降順に選択する貪欲法が使えるので、
目標とする濃度で二分法を使ってます。

類題

M問題 おまかせ