ABC202-D aab aba baa

問題へのリンク

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 2 4");
            //baab
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("30 30 118264581564861424");
            //bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
        }
        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 A = wkArr[0];
        long B = wkArr[1];
        long K = wkArr[2];

        long RestACnt = A;
        long RestBCnt = B;
        long LenCnt = A + B;
        string Answer = "";
        long TargetRank = K;

        // 先頭から埋めていく
        for (long I = 1; I <= LenCnt; I++) {
            if (RestACnt == 0) {
                Answer += 'b';
                continue;
            }
            if (RestBCnt == 0) {
                Answer += 'a';
                continue;
            }

            // 先頭がaでの、場合の数
            long GroupCntA = DeriveCombi(LenCnt - I, RestACnt - 1);

            if (TargetRank <= GroupCntA) {
                Answer += 'a';
                RestACnt--;
            }
            else {
                Answer += 'b';
                RestBCnt--;

                // 求める順位を更新
                TargetRank -= GroupCntA;
            }
        }
        Console.WriteLine(Answer);
    }

    //nCrを求める
    static long DeriveCombi(long pN, long pR)
    {
        long WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        var DivList = new List<long>();
        for (long I = 2; I <= pR; I++) {
            DivList.Add(I);
        }

        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;

            for (int J = DivList.Count - 1; 0 <= J; J--) {
                if (WillReturn % DivList[J] == 0) {
                    WillReturn /= DivList[J];
                    DivList.RemoveAt(J);
                }
            }
        }
        return WillReturn;
    }
}

解説

aが3文字、bが3文字
で5番目の文字列について考えます

先頭がaの場合 a????? で 5C2 で 10通りの文字列があります。
先頭がbの場合 b????? で 5C2 で 10通りの文字列があります。
5番目の文字列を求めたいので、先頭文字は、aで確定します。

続いて、a?????について考えます
2番目の文字がaの場合 aa???? で 4C1 で 4通りの文字列があります。
2番目の文字がbの場合 ab???? で 4C2 で 6通りの文字列があります。
5番目の文字列を求めたいので、2番目の文字は、bで確定します。

??????の5番目の文字列は
ab????の1番目と、一致するので
簡単のため、後者を求める問題に変更して考えます。

続いて、ab????について考えます
3番目の文字がaの場合 aba??? で 3C1 で 3通りの文字列があります。
3番目の文字がbの場合 abb??? で 3C2 で 3通りの文字列があります。
1番目の文字列を求めたいので、3番目の文字は、aで確定します。

続いて、aba???について考えます
4番目の文字がaの場合 abaa?? で 2C2 で 1通りの文字列があります。
4番目の文字がbの場合 abbb?? で 2C2 で 1通りの文字列があります。
1番目の文字列を求めたいので、4番目の文字は、aで確定します。

以上により
abaaまで確定したので残りのbを右に埋め、解は、abaabbになります。