ARC109-C Large RPS Tournament

問題へのリンク

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("3 2");
            WillReturn.Add("RPS");
            //P
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("11 1");
            WillReturn.Add("RPSSPRSPPRS");
            //P
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 100");
            WillReturn.Add("S");
            //S
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int K = wkArr[1];

        string S = InputList[1];
        int UB_Str = S.Length - 1;

        // 優勝者の手[2の指数,開始Ind]なDP表
        char[,] DPArr = new char[K + 1, UB_Str + 1];

        // 2の指数でループ
        for (int I = 1; I <= K; I++) {
            // 区間Staでループ
            for (int J = 0; J <= UB_Str; J++) {

                if (I == 1) {
                    char Te1 = S[J];
                    char Te2 = S[(J + 1) % (UB_Str + 1)];
                    char WinTe = GetWin(Te1, Te2);
                    DPArr[I, J] = WinTe;
                }
                else {
                    int Sisuu = I - 1;
                    char Te1 = DPArr[Sisuu, J];
                    int Ind2 = J + DeriveBekijyou(2, Sisuu, UB_Str + 1);
                    Ind2 %= (UB_Str + 1);
                    char Te2 = DPArr[Sisuu, Ind2];
                    char WinTe = GetWin(Te1, Te2);
                    DPArr[I, J] = WinTe;
                }
            }
        }

        Console.WriteLine(DPArr[K, 0]);
    }

    // 2手を引数として、勝つ手を返す
    static char GetWin(char p1, char p2)
    {
        if (p1 == 'R' && p2 == 'S') return 'R';
        if (p1 == 'S' && p2 == 'R') return 'R';

        if (p1 == 'R' && p2 == 'P') return 'P';
        if (p1 == 'P' && p2 == 'R') return 'P';

        if (p1 == 'S' && p2 == 'P') return 'S';
        if (p1 == 'P' && p2 == 'S') return 'S';

        return p1;
    }

    // 繰り返し2乗法で、(NのP乗) Mod Mを求める
    static int DeriveBekijyou(int pN, int pP, int pM)
    {
        int CurrJyousuu = pN % pM;
        int CurrShisuu = 1;
        int WillReturn = 1;

        while (true) {
            // 対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

解説

優勝者の手[2の指数,開始Ind]なDP表を
区間DPで更新してます。