yukicoder No.2069 み世界数式 解説

問題

yukicoder No.2069 み世界数式

No.2069 み世界数式 - yukicoder
競技プログラミングの練習サイト

解説

無駄に高速化します。

構文解析

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

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

DP

二分木の各ノードについて、長さ $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)$ です。

#796363 (C++17) No.2069 み世界数式 - yukicoder
競技プログラミングの練習サイト
タイトルとURLをコピーしました