yukicoder No.2069 み世界数式解説

問題

yukicoder No.2069 み世界数式

無駄に高速化します。

非負整数・足し算・掛け算・括弧からなる式を解読し、式の計算過程を表す二分木を構築します。

たまたま持っていた昔のライブラリ（再帰関数を呼ばない拘りライブラリ）を引き出して使いました。式を計算する代わりに二分木のノードを生成して返すのがポイントです。

二分木の各ノードについて、長さ $M+1$ の真理値列を管理し、その時点の計算過程を $0,1,\ldots ,M$ にすることがそれぞれ可能かどうかを表すことにします。これをボトムアップに計算し、その後トップダウンに数式を復元します。

bitset 高速化ができます。計算量は $O(\frac{M^2}{w})$ です。

結果が $M$ を超えないような組の個数は $O(M \log M)$ なので、全探索します。

$a/b=c$ とすると、 $b,c$ の組の個数は $O(M \log M)$ なので、これを全探索します。これを満たす $a$ は区間になるので、累積和を用いて判定すると各イテレーションの計算量は $O(1)$ になります。

$c$ の値はわかっているので、 $b$ を全探索し、累積和の判定がヒットしたところで $a$ を探索します。計算量は $O(M)$ です。

全体の計算量は $O\left(\lvert\text{expr}\rvert M \left( \frac{M}{w}+\log M \right) \right)$ です。