CADDi 2018 for Beginners D Harlequin

問題へのリンク

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("2");
            WillReturn.Add("1");
            WillReturn.Add("2");
            //first
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("100000");
            WillReturn.Add("30000");
            WillReturn.Add("20000");
            //second
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray();

        if (Array.TrueForAll(AArr, pX => pX % 2 == 0)) {
            Console.WriteLine("second");
        }
        else {
            Console.WriteLine("first");
        }
    }
}

解説

木が2本しかない場合で、後退解析で、
手番を持ったときの勝敗を求めると下記になります。

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

ここから、全ての木のりんごの数が偶数なら先手負け
そうでなければ、先手勝ちと予想されます。

予想が正しいか考えると、

開始状態で、3本以上の木があって、全ての木のりんごが偶数なら
先手と同じ操作を後手が行えば、
後手必勝と分かります。

開始状態で、3本以上の木があって、りんごが奇数の木があればら
全ての木が偶数の状態にして、後手に手番を渡せば、
先手必勝と分かります。