公式解説とは異なる方針を紹介します。

「振りなおすことを選択した時のコストの期待値」を \(X\) とおきます。はじめは、\(T\) が出るまで必ず振りなおすと仮定して、\(X:=BN\) とします。

この期待値をより正確にすることを考えます。まず、振りなおして \(T\) より大きい数が出た場合、明らかにコスト \(X\) で振りなおすべきです。

\(T\) 以下の数が出た場合、出目を \(1\) ずつ増やして \(T\) にするときのコストが \(X\) 以上のとき、またそのときに限りコスト \(X\) で振りなおすべきです。このボーダーラインは単調なため二分探索で求められるほか、単純な四則演算で \(O(1)\) で求めることも可能です。

よって、\(X:=\frac{X(N-T)+\sum_{i=1}^{T}\min(X,A(T-i))}{N}+B\) と表せます。最後の \(+B\) は、必ず \(1\) 回は振りなおすと仮定しているためです。先述の通り、これは \(O(\log N)\) や \(O(1)\) で求めることが可能です。

あとはこの計算を時間の許す限り行い、\(T<S\) の場合 \(X\) を、それ以外の場合 \(\min(X,A(T-S))\) を出力することでACすることが可能です。

未証明ですが、許容される誤差までの収束は非常に速いです。厳密な証明をしていただける方はご一報いただければ幸いです。

解答例(PyPy3,149ms)