ABC255-C ±1 Operation 1

問題へのリンク

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("6 2 3 3");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 0 0 1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("998244353 -10 -20 30");
            //998244363
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("-555555555555555555 -1000000000000000000 1000000 1000000000000");
            //444445
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long X = wkArr[0];
        long A = wkArr[1];
        long D = wkArr[2];
        long N = wkArr[3];

        long L = 1;
        long R = N;

        // Indを引数として、関数値を返す
        Func<long, long> CalcFunc = pInd =>
        {
            return Math.Abs(X - DeriveVal(A, D, pInd));
        };

        var PairHashSet = new HashSet<string>();
        while (L + 1 < R) {
            long C1 = (L * 2 + R) / 3;
            long C2 = (L + R * 2) / 3;

            long C1Val = CalcFunc(C1);
            long C2Val = CalcFunc(C2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }

            string Hash = string.Format("{0},{1}", L, R);
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }
        var MinKouhoList = new List<long>();
        for (long I = L; I <= R; I++) {
            MinKouhoList.Add(CalcFunc(I));
        }
        Console.WriteLine(MinKouhoList.Min());
    }

    // 等差数列の初項と公差と項番を引数として、項の値を返す
    static long DeriveVal(long pSyokou, long pKousa, long pBanme)
    {
        return pSyokou + pKousa * (pBanme - 1);
    }
}

解説

等差数列の項番を考えると、
Xとの差は、下に凸なので
等差数列の項番を三分探索してます。