C11 Election

問題へのリンク

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("4 10");
            WillReturn.Add("1000000 700000 300000 180000");
            //5 3 1 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 3");
            WillReturn.Add("6000 3000");
            //2 1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15 50");
            WillReturn.Add("18256245 7845995 6771945 6181431 3618432 3159625 2319156 1768385 1258501 1253872 193724 148020 109045 77861 65107");
            //18 8 7 6 3 3 2 1 1 1 0 0 0 0 0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2 1");
            WillReturn.Add("900000000 100000000");
            //1 0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("2 1");
            WillReturn.Add("9 1");
            //1 0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 閾値を二分探索する
        double L = 0;
        double R = mAArr.Max();

        while (L + 0.0000001D < R) {
            double Shikiiti;
            if (R == double.MaxValue) {
                Shikiiti = R / 2D;
            }
            else {
                Shikiiti = (L + R) / 2D;
            }

            if (IsOKShikiiti(Shikiiti)) {
                R = Shikiiti;
            }
            else {
                L = Shikiiti;
            }
        }

        var AnswerList = new List<long>();
        foreach (long EachA in mAArr) {
            long CurrDeriveSeatCnt = DeriveSeatCnt(EachA, R);
            AnswerList.Add(CurrDeriveSeatCnt);
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    // 閾値を引数とし、議席合計がK以下かを返す
    static bool IsOKShikiiti(double pShikiiti)
    {
        long SeatCntSum = 0;

        foreach (long EachA in mAArr) {
            SeatCntSum += DeriveSeatCnt(EachA, pShikiiti);
            if (SeatCntSum > mK) return false;
        }
        return true;
    }

    // 票数と閾値を引数として、議席数を二分探索で求める
    static long DeriveSeatCnt(long pHyousu, double pShikiiti)
    {
        if (pHyousu < pShikiiti) return 0;

        long L = 1;
        long R = pHyousu;

        while (L + 1 < R) {
            long SeatCnt = (L + R) / 2;

            double Syou = (double)pHyousu / SeatCnt;

            if (Syou >= pShikiiti) {
                L = SeatCnt;
            }
            else {
                R = SeatCnt;
            }
        }
        return L;
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

閾値を二分探索してます。