ARC109-B log

問題へのリンク

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");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("109109109109109109");
            //109109108641970782
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = long.Parse(InputList[0]);

        long L = 0;
        long R = mN;

        // 答えを二分探索する
        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (IsOK(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    // 引数の購入数でOKかを判定
    static bool IsOK(long pBuyCnt)
    {
        // 初項 1
        // 項数 mN+1-pBuyCnt
        // 公差 1
        // の等差数列の和
        long Prod1 = mN + 1 - pBuyCnt;
        long Prod2 = mN + 1 - pBuyCnt + 1;

        // オーバーフロー対策で、偶数の式を2で割り
        // 不等式を変形する
        if (Prod1 % 2 == 0) {
            Prod1 /= 2;
        }
        else {
            Prod2 /= 2;
        }
        return Prod1 <= (mN + 1) / Prod2;
    }
}

解説

長い丸太は、短い丸太の上位互換なので、
長い丸太から選ぶのが最適です。

選ぶ本数を最小にしたいので、答えを二分探索してます。