\(S,T\) を以下のような \(0\) 以上 \(2^N\) 未満の非負整数に変換します。

• \(i\) 文字目が A ならば \(2^{i-1}\) の位が \(0\)、B ならば \(1\) であるような非負整数

すると、\(S\) に対する操作は \(2^i\) の位が \(0\) であるような \(i\) を選んで \(3 \times 2^i\) を足す操作と見なせます。

非負整数列 \((x_0,x_1,\ldots,x_{N-1})\) に対して、\(2^i\) に対する操作を \(x_i\) 回行って \(S=T\) にできるかを考えます。当然、\(\sum 2^i x_i = \frac{T-S}{3}\) が必要です。\(2^i\) に対する操作は、まず \(S\) の \(2^i\) の位が \(0\) ならば \(1\) 回行えます。また、それより下の位に対する操作で \(2^i\) の位が変化すると再び行えますが、この回数は最大で \(\lfloor \frac{S + \sum_{j=0}^{i-1} 3 \times 2^j x_j}{2^i}\rfloor - \lfloor \frac{S}{2^i}\rfloor\) 回です。よって、\(x_i\) はこれらの和以下であることが必要です。

ここで、\(2^i\) の位が \(0\) かつ \(2^i\) に対する操作がまだ必要な \(i\) のうち最大のものを選んで操作をすることにすると、上記が十分条件でもあることが \(i\) の昇順に示せます。

\(x_0,\ldots,x_{N-1}\) は以下の手続きによって定められます。\(y_i\) を \(2^i\) に対して操作を行える回数の最大値とし、初め \(y_i\) を \(\frac{T-S}{3}\) の \(2^i\) の位と定めます。\(i=N-1,\ldots,0\) の順に、\(x_i\) を \(x_i \leq \lfloor \frac{S + \sum_{j=0}^{i-1} 3 \times 2^j x_j}{2^i}\rfloor - \lfloor \frac{S}{2^i}\rfloor\) となるように定め、\(y_{i-1}\) を \(2(y_i-x_i)\) 増やします。便宜的に \(y_{-1}\) を考えることにすると、\(y_{-1}=0\) ならば正当な \((x_0,\ldots,x_{N-1})\) が求められたことになります。

上記手続きの各 \(i\) において \(x_i\) を可能な限り大きな値にする貪欲戦略が最適なことを示します。貪欲でない戦略の結果得られる \(x_i,y_i\) を \(x_i',y_i'\) とします。この戦略において \(x_i\) を\(1\) 増やせるにも関わらずそうしなかった最後の位置を \(k\) とし、そこで \(1\) 増やしてそれ以降貪欲な戦略を取った場合の \(x_i,y_i\) を \(x_i'', y_i''\) とします。戦略の変化によって \(y_{k-1}' \lt y_{k-1}''\) となりますが、以降貪欲な戦略を取った場合には \(y_{k-2}' \leq y_{k-2}'', y_{k-3}' \leq y_{k-3}'', \ldots, y_{-1}' \leq y_{-1}''\) となります。そのため、貪欲でない戦略を貪欲なものに置き換えた場合に \((x_0,\ldots,x_{N-1})\) の正当性は保たれます。また、\(x_{k-1}' \leq x_{k-1}'', \ldots x_0' \leq x_0''\) も成り立ちます。\(x_k\) は貪欲な戦略に置き換えることで \(1\) 増えますが、ある \(k'(0 \leq k' \lt k)\) が存在して \(x_{k'}' \gt x_{k'}''\) が成り立つ(そうでないと \(2^i x_i\) の総和が合わなくなる)ため、\(\sum x_i\) が悪化しないことも言えます。以上より貪欲でない戦略が最適な場合はそれを貪欲な戦略に置き換えてもなお最適であることが言え、貪欲が正当と言えました。

後は上記手続きをシミュレーションすれば良いです。挙動を追うと \(y_i\) は常に \(3\) 以下であることが確かめられ、管理する値の最上位bitは \(i\) の数桁上までと分かります。そのため、足し算・引き算は \(\mathrm{O}(1)\) で行え、全体で \(\mathrm{O}(N)\) で本問を解くことができます。