yukicoder 1595 The Final Digit

問題へのリンク

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("11 11 11 7");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("86 91 20 1001");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("31415 92653 58979 1000000000000000000");
            //5
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 10 10 4");
            //0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("500095722 275276874 360324360 4");
            //6
        }
        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(pX => long.Parse(pX)).ToArray();
        long A1 = wkArr[0] % 10;
        long A2 = wkArr[1] % 10;
        long A3 = wkArr[2] % 10;
        long K = wkArr[3];

        var AppearList = new List<string>();
        var AppearSet = new HashSet<string>();

        string[] PreCycleArr;
        string[] CycleArr;

        K -= 3;

        var CurrList = new List<long>() { A1, A2, A3 };
        while (true) {
            string CurrHash = GetHash(CurrList);
            if (AppearSet.Contains(CurrHash)) {
                PreCycleArr = AppearList.TakeWhile(pX => pX != CurrHash).ToArray();
                CycleArr = AppearList.SkipWhile(pX => pX != CurrHash).ToArray();
                break;
            }
            AppearList.Add(CurrHash);
            AppearSet.Add(CurrHash);

            DeriveNextList(CurrList);
        }

        if (K <= PreCycleArr.Length) {
            string PrevHash1 = PreCycleArr[K - 1];
            Console.WriteLine(DeriveResult(PrevHash1));
            return;
        }
        long RestK = K - PreCycleArr.Length;
        string PrevHash2 = CycleArr[(RestK - 1) % CycleArr.Length];
        Console.WriteLine(DeriveResult(PrevHash2));
    }

    static long DeriveResult(string pHash)
    {
        long Result = 0;
        string[] SplitArr = pHash.Split(',');
        foreach (string EachStr in SplitArr) {
            Result += long.Parse(EachStr);
            Result %= 10;
        }
        return Result;
    }

    // 現在の値のListを引数として、次をList設定
    static void DeriveNextList(List<long> pList)
    {
        long SumVal = pList.Sum() % 10;
        pList.Add(SumVal);
        pList.RemoveAt(0);
    }

    // 現在の3つの値からハッシュ値を求める
    static string GetHash(List<long> pList)
    {
        return string.Format("{0},{1},{2}", pList[0], pList[1], pList[2]);
    }
}

解説

トリボナッチ数列であり
mod 10で 考えれば、
3つの項の組み合わせは、10*10*10で1000通りです。

後は、鳩ノ巣原理をふまえて、サイクルを検出すれば良いです。