ABC242-D ABC Transform

問題へのリンク

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("ABC");
            WillReturn.Add("4");
            WillReturn.Add("0 1");
            WillReturn.Add("1 1");
            WillReturn.Add("1 3");
            WillReturn.Add("1 6");
            //A
            //B
            //C
            //B
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("CBBAACCCCC");
            WillReturn.Add("5");
            WillReturn.Add("57530144230160008 659279164847814847");
            WillReturn.Add("29622990657296329 861239705300265164");
            WillReturn.Add("509705228051901259 994708708957785197");
            WillReturn.Add("176678501072691541 655134104344481648");
            WillReturn.Add("827291290937314275 407121144297426665");
            //A
            //A
            //C
            //A
            //A
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long T = wkArr[0];
            long K = wkArr[1];

            if (T == 0) {
                Console.WriteLine(S[(int)K - 1]);
                continue;
            }

            long LeafCnt = DeriveLeafCnt(T);

            // 根ノードの文字を求める
            long MapInd = (K - 1) / LeafCnt;
            char RootChar = S[(int)MapInd];

            long ModK = (K - 1) % LeafCnt;

            // 木の高さ = 左への移動回数 + 右への移動回数
            long RightCnt = PopCount(ModK);
            long LeftCnt = T - RightCnt;

            RightCnt %= 3;
            LeftCnt %= 3;

            long AddVal = LeftCnt;
            AddVal += 2 * RightCnt;
            AddVal %= 3;

            for (int I = 1; I <= AddVal; I++) {
                if (++RootChar == 'D') {
                    RootChar = 'A';
                }
            }
            Console.WriteLine(RootChar);
        }
    }

    // 完全二分木の高さを引数として、葉ノード数を返す
    static long DeriveLeafCnt(long pHeight)
    {
        long LeafCnt = 1;
        for (long I = 1; I <= pHeight; I++) {
            if (WillOverProd(LeafCnt, 2, long.MaxValue)) {
                return long.MaxValue;
            }
            LeafCnt *= 2;
        }
        return LeafCnt;
    }

    // 2正数の掛け算が、Limitを超えるかを返す
    static bool WillOverProd(long pA, long pB, long pLimit)
    {
        return pA > pLimit / pB;
    }

    ////////////////////////////////////////////////////////////////
    // C++のPopCount
    ////////////////////////////////////////////////////////////////
    static long PopCount(long pVal)
    {
        long WillReturn = 0;
        while (pVal > 0) {
            if (pVal % 2 == 1) WillReturn++;
            pVal /= 2;
        }
        return WillReturn;
    }
}

解説

Aの変換について考えると、下記の完全二分木になってると分かります。
レベル1      A
レベル2     BC
レベル3  CA    AB
レベル4 AB BC  BC CA

後は、木の高さから各完全二分木の葉のノード数を求めて
対応する根の値を求めます。

完全二分木なので
左の根ノードから0,1,2,3,4,5,6,を二進数に変換した
PopCntが右に移動した回数と分かります。

木の高さ = 左に移動した回数 + 右に移動した回数
なので移項すれば
左に移動した回数 = 木の高さ - 右に移動した回数
なので
mod3で考えて解が分かります。