AtCoder Beginner Contest 202 (D - aab aba baa)

解説とは異なる実装をしたので、備忘録代わりに書きます。コードはこちらです。

$a=0, b=1$ と読み替えて、 $a$ と $b$ の並びを $A+B$ 桁の二進数 $N$ と解釈します。読み替える必要はありませんが、こうした方が個人的には理解しやすいです。

最初に $N$ の最上位ビットを決めます。つまり $N$ の最下位ビット(この位置を0とする)から数えて、 $B$ 個目の1が最後に出現する位置 $p$ を決めます。これは $p$ ビット目が1, ${p-1}..0$ ビット目に $A$ 個の0と $B-1$ 個の1が順不同で続くということです。この順不同の組み合わせは $\binom{A+B-1}{A}$ 個あります。

この組み合わせの個数を $p=(B-1)..(A+B-1)$ まで求めて、 $1..p$ について組み合わせの個数の累積和を取れば、 $p$ 桁以内の組み合わせの総数が分かります。これを $K$ について二分探索(C++なら std::lower_bound )で求めることができます。 $p$ が求まったら $K$ から $p-1$ 桁以内の組み合わせの総数を引きます。

以下同様に更新後の $K$ について求めると、残りの1になるビットの位置が順番に求まります。最後の1ビットの位置は、残った $K$ に対して $K-1$ ビット目です。

最後にビット0をa、ビット1をbと読み替えて文字列を出力します。二分探索が無い分だけ、この解法より公式解説の方が速いと思います。