aab aba baa [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） D]

https://atcoder.jp/contests/abc202/tasks/abc202_d

解説

https://atcoder.jp/contests/abc202/submissions/22836918

辞書順に並び替えると、

a????????  
b????????  

の並びになっており、K番目ということを考えると、このどちらのグループに入るかということが分かる。
例えばaが4個あってbが7個ある場合、a???????となる個数は二項定理を使ってC(3+7,7)通りになる。
ざっくり説明すると、残った3つのaと7つのbを使って作れる文字列の個数がそのままそのグループの個数となる。
具体的にはC(a-1+b,b)通りである。

この個数を見れば、最初の文字としてどちらの文字を選択すればいいかが分かる。
この時、aが選択された場合は答えに追加するだけでいいが、bが選択された場合は、a?????????がスキップされることになるので、
K番目のKが少し変わることになる。
bが選択された場合はb????????の先頭から考え始めることになるので、Kからスキップした分のC(a-1+b,b)を引いておく。

あとは、この操作を続けていって文字を決めていけばいい。

実装について

二項係数を用意する必要があるのが面倒。
上限が60なので、手作業で用意してもいいし、
自分の実装のようにaCb(a, b) = aCb(a - 1, b - 1) + aCb(a - 1, b)を使って事前計算してもいい。
long longで用意する必要があり、オーバーフローを気にする必要はあるが、使用する範囲内では問題ないので適当に（祈りを込めて）出す。

int A, B; ll K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> K;
    K--;

    int N = A + B;

    string ans = "";
    rep(i, 0, N) {
        if (0 < A) {
            if (K < aCb(A + B - 1, B)) {
                ans += "a";
                A--;
            }
            else {
                ans += "b";
                K -= aCb(A + B - 1, B);
                B--;
            }
        }
        else {
            ans += "b";
            B--;
        }
    }
    cout << ans << endl;
}