ABC013-D 阿弥陀

問題へのリンク

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("5 7 1");
            WillReturn.Add("1 4 3 4 2 3 1");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 7 2");
            WillReturn.Add("1 4 3 4 2 3 1");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 20 300");
            WillReturn.Add("9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long D = wkArr[2];

        long[] AArr = GetSplitArr(InputList[1]);

        // 値[位置]なDict
        var ValDict = new Dictionary<long, long>();
        for (long I = 1; I <= N; I++) {
            ValDict[I] = I;
        }

        foreach (long EachA in AArr) {
            long FromNode = EachA;
            long ToNode = EachA + 1;

            long tmp = ValDict[FromNode];
            ValDict[FromNode] = ValDict[ToNode];
            ValDict[ToNode] = tmp;
        }

        // 位置[値]なDict
        var PosDict = new Dictionary<long, long>();
        foreach (var EachPair in ValDict) {
            PosDict[EachPair.Value] = EachPair.Key;
        }

        // アリごとの現在位置[2べきの値]なDictの配列
        var DoublingDictArr = new Dictionary<long, long>[N + 1];
        for (long I = 1; I <= N; I++) {
            DoublingDictArr[I] = new Dictionary<long, long>();
        }

        // 1日後の位置を設定
        for (long I = 1; I <= N; I++) {
            DoublingDictArr[I][1] = PosDict[I];
            //Console.WriteLine("{0}の1日後の位置={1}", I, PosDict[I]);
        }

        // 2べき日後の位置を設定
        long Beki2 = 2;
        while (Beki2 <= D) {
            long Div2 = Beki2 / 2;
            for (long I = 1; I <= N; I++) {
                long Div2Pos = DoublingDictArr[I][Div2];
                long GoalPos = DoublingDictArr[Div2Pos][Div2];
                DoublingDictArr[I][Beki2] = GoalPos;
            }
            Beki2 *= 2;
        }

        // 回答
        var AnswerDict = new Dictionary<long, long>();
        for (long I = 1; I <= N; I++) {
            long CurrPos = I;
            long RestDay = D;

            while (RestDay > 0) {
                long MaxBeki2 = DeriveMaxBeki2(RestDay);
                CurrPos = DoublingDictArr[CurrPos][MaxBeki2];
                RestDay -= MaxBeki2;
            }
            Console.WriteLine(CurrPos);
        }
    }

    // 引数の数値以下で、最大の2べきを返す
    static long DeriveMaxBeki2(long pTarget)
    {
        long WillReturn = 1;
        for (long I = 1; I < long.MaxValue; I *= 2) {
            if (I <= pTarget) {
                WillReturn = I;
            }
            else {
                break;
            }
        }
        return WillReturn;
    }
}

解説

ダブリングの問題に帰着させてます。