ABC188-F +1-1x2

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mX;
    static long mY;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mX = wkArr[0];
        mY = wkArr[1];
        long Result = DFS(mY);
        Console.WriteLine(Result);
    }

    // メモ化再帰で現在値がpKの時の、Xまでのコストを返す
    static Dictionary<long, long> MemoDict = new Dictionary<long, long>();
    static long DFS(long pK)
    {
        if (pK == mX) return 0;

        if (MemoDict.ContainsKey(pK)) {
            return MemoDict[pK];
        }

        var SeniList = new List<long>();
        SeniList.Add(Math.Abs(mX - pK));

        Action<long> KagenAndDiv = (pPlusMinus) =>
        {
            long Cost = 0;
            long NewK = pK;
            while (NewK % 2 > 0) {
                NewK += pPlusMinus;
                Cost++;
            }
            NewK /= 2;
            Cost++;

            if (NewK != pK) {
                SeniList.Add(Cost + DFS(NewK));
            }
        };

        KagenAndDiv(-1);
        KagenAndDiv(+1);
        return MemoDict[pK] = SeniList.Min();
    }
}

解説

2倍するより、2で割るほうが制限かきついので、
XからYにするのではなく、逆方向で
YからXにすると考えます。

すると、遷移は下記の3通りになり、メモ化再帰で解くことができます。
●+1か-1でXにする
●+1を繰り返し、2の倍数になったら2で割る
●-1を繰り返し、2の倍数になったら2で割る

なお、+1を繰り返し、2の倍数を通り越して、次の2の倍数で、2で割るような遷移は、
双方向探索なので、Xからの遷移を考えれば損な遷移だと分かります。

類題

AGC044-A Pay to Win