May 23, 2021

ABC202_D

Table of Contents

AtCoder Beginner Contest 202 D

お題

問題

ポイント

とりあえず、重複する値がある順列の計算のために、階乗を計算しておく。

それを使ってaがA個、bがB個の順列を計算する関数を作っておく(関数f)。

方針としては、一番左の文字から順番に決めていく。

一番左がaになるのは、f(a-1, b)通りあって、これがKより小さければ、Kから引いて、bに確定。そうでなければaに確定。 aなら–a, bなら–bを繰り返す。

回答

fac = [1, 1, 2]
for i in range(3, 61):
    fac.append(fac[-1] * i)


def f(a, b):
    return fac[a + b] // fac[a] // fac[b]


def main():
    A, B, K = map(int, input().split())
    current = 0
    a = A
    b = B
    k = K
    ans = []
    for i in range(A + B):
        if a == 0:
            ans = ans + (["b"] * b)
            break
        elif b == 0:
            ans = ans + (["a"] * a)
            break
        _k = f(a-1,b)
        if _k < k:
            k -= _k
            ans.append("b")
            b -= 1
        else:
            ans.append("a")
            a -= 1
        ans

    print("".join(ans))


if __name__ == "__main__":
    main()