ARC164-A Ternary Decomposition

問題へのリンク

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");
            WillReturn.Add("5 3");
            WillReturn.Add("17 2");
            WillReturn.Add("163 79");
            WillReturn.Add("1000000000000000000 1000000000000000000");
            //Yes
            //No
            //Yes
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 2,8,26,80な、3べきから1引いたList
    static List<long> mMinusKouhoList = new List<long>();

    static void Main()
    {
        long CurrMinusKouho = 2;
        while (true) {
            mMinusKouhoList.Add(CurrMinusKouho);
            if (WillOverProd(CurrMinusKouho, 3, long.MaxValue)) {
                break;
            }
            CurrMinusKouho = (CurrMinusKouho + 1) * 3 - 1;
        }

        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long N = wkArr[0];
            long K = wkArr[1];
            bool Result = Solve(N, K);
            if (Result) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }

    static bool Solve(long pN, long pK)
    {
        // 最低値は1なので、先にその分を引く
        long CurrVal = pN;
        CurrVal -= pK;

        if (CurrVal < 0) {
            return false;
        }

        if (CurrVal == 0) {
            return true;
        }

        for (long I = 1; I <= pK; I++) {
            long MinusVal = 0;
            foreach (long EachMinusKouho in mMinusKouhoList) {
                if (CurrVal - EachMinusKouho >= 0) {
                    MinusVal = EachMinusKouho;
                }
            }
            CurrVal -= MinusVal;
            if (MinusVal == 0) break;
        }

        return CurrVal == 0;
    }

    // 2正数の掛け算が、Limitを超えるかを返す
    static bool WillOverProd(long pA, long pB, long pLimit)
    {
        return pA > pLimit / pB;
    }
}

解説

最低値は、オール1の場合なので
先に合計に計上し

0 0 0 0 0 0 0
の状態から各値を
2 8 26 80 ・・・
のどれかに変形できると考えれば、
残りの値以下での最大値を
貪欲に設定することができます。