ABC202 D - aab aba baa 別解 - 赤い星と強い星

ABC202 D - aab aba baaの桁DP+二分探索を用いた解法の解説です．

問題リンク

提出コード

問題概要

$A$ 個のaと $B$ 個のbからなる長さ $A+B$ の文字列のうち，辞書順で $K$ 番目のものを求めてください．

制約

・ $1 \leq A,B \leq 30$

・ $A$ 個のaと $B$ 個のbからなる長さ $A+B$ の文字列が少なくとも $K$ 個は存在することが保証される

解法

aを $0$ ，bを $1$ に直します．すると，aとbからなる文字列は2進数とみなすことができます．

この操作をしたあと，元の問題は「 $1$ が $B$ 回使われている2進数の小さいほうから $K$ 番目の数は何か」と言い換えることができます．

$A+B$ 桁に満たないものは $A+B$ 桁になるまで先頭に $0$ をつけ足せば $0$ が $A$ 個という条件を満たします．また，同じ桁数同士の整数の大小関係はそれを文字列として見たときの辞書順の大小関係と一致します．よって，上の言い換えが成立することがわかります．

次に以下の小問題 $f(x)$ を考えます．

・ $f(x):=$ 2進法表記された整数 $x$ 以下に $1$ が $B$ 回使われている数は $K$ 個未満かどうか

$f(0)=True$ であって，十分大きな整数 $c$ に対しては $f(c)=False$ です．また， $x'$ が $f(x')=True$ となるならば $0 \leq y \leq x'$ を満たす任意の $y$ に対して $f(y)=True$ です．同様に， $x'$ が $f(x')=False$ となるならば $x' \leq y$ を満たす任意の $y$ に対して $f(y)=False$ です．よってこの小問題には単調性があり，ある $m$ が存在して $f(m)=True,f(m+1)=False$ となります．この時の $m+1$ が答えとなります．

小問題の判定について考えてみましょう．「〇〇以下の条件を満たすものの個数」という問題は桁DPというアルゴリズムを用いて求めることができる場合が多く，今回もそれを用いて判定することを考えます．

配列の定義

$dp[i][j][?]:=$ 上から $i$ 桁目まで見て， $1$ の個数が $j$ 個で， $x$ より小さいことが確定しているかどうか( $?$ が $0$ なら $x$ ちょうど， $1$ なら $x$ より小さいことが確定)

遷移

・ $?=1$ からは $?=1$ にのみ遷移

・ $?=0$ から $?=1$ に遷移

・ $?=0$ から $?=0$ に遷移

それぞれの遷移ごとに $j$ の値を増やしたりそのままにしたりして遷移します(詳しくは僕の提出を参考にしてください)．

判定内容

$x$ を2進数表記して，その桁数を $n$ とすると， $dp[n][B][0]+dp[n][B][1] \lt K$ かどうか

以上の方法を用いて小問題を構成します．

先に述べたようにこの小問題には単調性があるので，二分探索を用いて答えとなる整数を求めることができます．最後に求めた答えを2進数に変換し， $0$ をaに， $1$ をbに変更した文字列が最終的な答えとなります．

小問題を $1$ 回解くごとに， $x$ の桁数を $n$ とすると $O(n ^ 2)$ であり，二分探索の探索範囲を $l,r$ とすると小問題を $\mathbf{log}(r-l)$ 回程度行うので，全体としての計算量は $O(n ^ 2 \mathbf{log}(r-l))$ となり，この問題の条件下では十分高速です．