ABC-059-D Alice&Brown

■■■問題■■■

AliceとBrownはゲームをするのが好きです。今日は以下のゲームを思いつきました。

2つの山があり、はじめにX,Y個の石が置かれています。
AliceとBrownは毎ターン以下の操作を交互に行い、
操作を行えなくなったプレイヤーは負けとなります。

●片方の山から2i個の石を取り、
  そのうちi個の石を捨て、残りのi個の石をもう片方の山に置く。
  ここで、整数 i(1 <= i) の値は山に十分な個数の石がある範囲で自由に選ぶことができる。

Aliceが先手で、二人とも最適にプレイすると仮定したとき、
与えられた X,Y に対しどちらのプレイヤーが勝つか求めてください。

■■■入力■■■

X Y

●0 <= X,Y <= 10の18乗

■■■出力■■■

Aliceが勝つときAliceと、Brownが勝つときBrownと出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 1");
            //Brown
            //Aliceは2個石のある山から2個取るしかありません。
            //その結果、山の石の数はそれぞれ 0,2 個となり、
            //Brownは2個の石を取り、山の石の数はそれぞれ 1,0 個となります。
            //Aliceはこれ以上操作を行うことができないので、Brownの勝ちです。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 0");
            //Alice
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("0 0");
            //Brown
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 8");
            //Alice
        }
        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(A => long.Parse(A)).ToArray();
        long X = wkArr[0];
        long Y = wkArr[1];

        Console.WriteLine(Math.Abs(X - Y) <= 1 ? "Brown" : "Alice");
    }
}

解説

X,Yが5以下での、ゲーム木の勝敗を求めると
下記になります。

  0 1 2 3 4 5
0 L L W W W W
1 L L L W W W
2 W L L L W W
3 W W L L L W
4 W W W L L L
5 W W W W L L

ノード間の遷移は、下記のいずれかです。
●Xを2i減らして、Yをi増やす
●Yを2i減らして、Xをi増やす

ゲーム木の葉ノードである
(X,Y)=(0,0),(0,1),(1,0),(1,1)の勝敗は先手負けですので、
この4つの葉ノードを起点として、ゲーム木の各ノードの勝敗を求めてます。