ABC027-C 倍々ゲーム

問題へのリンク

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("1");
            //Aoki
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            //Takahashi
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7");
            //Aoki
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            //Takahashi
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("123456789123456789");
            //Aoki
        }
        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 RightLimitList = DeriveRightLimitList();
        decimal LeftLimit = 1;

        for (int I = 0; I <= RightLimitList.Count - 1; I++) {
            if (LeftLimit <= N && N <= RightLimitList[I]) {
                if (I % 2 == 0) {
                    Console.WriteLine("Aoki");
                }
                else {
                    Console.WriteLine("Takahashi");
                }
            }
            LeftLimit = RightLimitList[I] + 1;
        }
    }

    static List<decimal> DeriveRightLimitList()
    {
        var RightLimitList = new List<decimal>();
        RightLimitList.Add(1);
        decimal Base2 = 1;
        for (int I = 1; I <= 45; I++) {
            Base2 *= 2 * 2;
            decimal LastVal = RightLimitList.Last();
            RightLimitList.Add(LastVal + Base2);
            RightLimitList.Add(LastVal + Base2 * 2);
        }
        //RightLimitList.ForEach(pX => Console.WriteLine(pX));
        return RightLimitList;
    }

    static void SolveNaive(long pN)
    {
        long UB = pN;

        // 手番を持った時に勝ち [Nの値] なDP表
        bool[] DPArr = new bool[UB + 1];

        for (long I = UB - 1; 0 <= I; I--) {
            var SeniList = new List<bool>();

            long Seni1Ind = I * 2;
            long Seni2Ind = I * 2 + 1;

            if (Seni1Ind <= UB) {
                SeniList.Add(DPArr[Seni1Ind]);
            }
            if (Seni2Ind <= UB) {
                SeniList.Add(DPArr[Seni2Ind]);
            }

            // 相手が負けになる遷移が1つでもあれば勝ち
            if (SeniList.Contains(false)) {
                DPArr[I] = true;
            }
            else {
                DPArr[I] = false;
            }
        }

        if (DPArr[1]) {
            Console.WriteLine("{0}の場合、Takahashi", pN);
        }
        else {
            Console.WriteLine("{0}の場合、Aoki", pN);
        }
    }
}

解説

DPでナイーブに後退解析すると
N=1 なら Aoki
Nが2以上5以下 なら Takahashi
Nが6以上9以下 なら Aoki
Nが10以上25以下 なら Takahashi
Nが26以上41以下 なら Aoki
Nが42以上105以下 なら Takahashi
Nが106以上169以下 なら Aoki
Nが170以上425以下 なら Takahashi
Nが426以上681以下 なら Aoki
Nが682以上1705以下 なら Takahashi
Nが1706以上2729以下 なら Aoki

範囲の右端の階差数列を考えると
4,4,16,16,64,64,256,256,1024,1024
になっているので、この階差数列を順に求めてます。