ABC246-D 2-variable Function

問題へのリンク

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("9");
            //15
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("999999999989449206");
            //1000000000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var AnswerKouho = new List<long>();

        // aを全探索し、bは二分探索
        for (long LoopA = 0; LoopA < long.MaxValue; LoopA++) {
            AnswerKouho.Add(ExecNibunhou(LoopA, N));

            if (LoopA * LoopA * LoopA > N) {
                break;
            }
        }
        Console.WriteLine(AnswerKouho.Min());
    }

    // aとNを引数として、関数の結果のN以上での最小値を返す
    static long ExecNibunhou(long pA, long pN)
    {
        if (DeriveFuncResult(pA, 0) >= pN) {
            return DeriveFuncResult(pA, 0);
        }

        long L = 0;

        // (Nの3乗根) + 1 なら確実にN以上になる
        long R = (long)(Math.Pow(pN, 1D / 3D) + 1);

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

            if (DeriveFuncResult(pA, Mid) >= pN) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return DeriveFuncResult(pA, R);
    }

    // aとbを引数として、関数の結果を返す
    static long DeriveFuncResult(long pA, long pB)
    {
        return pA * pA * pA +
            pA * pA * pB +
            pA * pB * pB +
            pB * pB * pB;
    }
}

解説

X = a*a*a + a*a*b + a*b*b + b*b*b
なので、
aは、0から a*a*a が Nを超えるまで
全探索します。

aごとのbは、二分探索で求めてます。