G - Good Vertices Editorial by Nyaan
(この解説はユーザー解説です)
想定解より計算量が悪い解法として \(\mathrm{O}(N^4 \log N \log L / W)\) (\(W = 64\)) 解法を簡単に説明します。
こちらの解法でも最終的に (半環 + 行列累乗) テクを利用します。半環を知らない方はまずは公式解説の方を参考にしてください。
まずは \(t\) を固定した場合の問題を考えてみましょう。
- \(dp_t\lbrack i \rbrack \lbrack u \rbrack\lbrack v \rbrack\) : \(t\) 秒後の状態のグラフについて、ちょうど \(i\) 回の移動によって頂点 \(u\) から頂点 \(v\) に到達することができるか？
という true/false を 値として持つ DP を考えてみましょう。この DP は以下の遷移で解くことができます。(\(\bigvee\) は \(\sum\) や \(\prod\) の仲間で、右側のすべての要素の論理和 (OR) を取る演算子です。)
\[ \begin{aligned} dp_t\lbrack 0 \rbrack \lbrack 1 \rbrack \lbrack 1 \rbrack &= \mathrm{true} \\ dp_t\lbrack 0 \rbrack \lbrack u \rbrack\lbrack v \rbrack &= \mathrm{false} &((u,v) \neq (1,1)) \\ dp_t\lbrack i \rbrack \lbrack u \rbrack \lbrack v \rbrack &= \bigvee_{1 \leq w \leq N} \left(dp_t\lbrack i-1 \rbrack \lbrack u \rbrack\right\lbrack w \rbrack) \mathrm{AND} \left(dp_t\lbrack 1 \rbrack \lbrack w \rbrack\lbrack v \rbrack\right) &(i \geq 1) \end{aligned} \]
この DP は、公式解説と同様に行列累乗に変形することができます。これは \(A = \lbrace \mathrm{true,false}\rbrace\)、加法 \(+\) を論理和 (OR)、乗法 \(\cdot\) を論理積 (AND) としたとき\((A, +, \cdot)\) は半環をなすことから従います。(このような構造はブール代数と呼ばれています。)
よって、 \(t\) を固定したときこの問題は \(\mathrm{O}(N^3 \log L)\) で解くことができます。
上記の解法を \(t=1,\dots,T\) について適用すれば答えを得ることができるので、まずは \(\mathrm{O}(N^3 T \log L)\) で解くことができました。しかしこれでは TL に間に合いません。
困ったかのようですが、ここからさらに \(2\) つの高速化を適用することで解決します。
高速化の\(1\) つは bitset 高速化 と呼ばれる高速化です。競技プログラミングで用いられる CPU は 64 bit 整数の AND / OR 演算を \(\mathrm{O}(1)\) で行うことができるので、適切に実装すれば 1 bit の AND / OR 演算は 64 個まとめて行うことができます。よって、 \(t\) を固定した時の問題は \(W = 64\) として \(\mathrm{O}(N^3 \log L / W)\) に計算量を落とすことができます。
ちなみに、C++ では std::bitset ライブラリで上記のAND / OR の \(64\) 倍高速化を容易に実装することができます。これが 上記のテクニックを bitset 高速化と呼ぶ理由です。
高速化のもう \(1\) つはアルゴリズム的改善で、二分探索 を適用します。\(i = 1, \dots, N\) に対して問題を独立に解いて、それぞれの問題に対して二分探索で答えを求めます。一回の二分探索では \(\mathrm{O}(\log T) = \mathrm{O}(\log (N^2)) = \mathrm{O}(\log N)\) 回の行列累乗を行うので、アルゴリズム全体での行列累乗の回数は \(\mathrm{O}(\log N) \times N = \mathrm{O}(N \log N)\) 回になります。よって、行列累乗を行う回数を \(\mathrm{O}(T)\) 回から \(\mathrm{O}(N \log N)\) 回に落とすことができました。
以上よりこの問題を \(\mathrm{O}(N^4 \log N \log L / W)\) で解くことができました。これは適切に実装すれば TL に十分間に合います。
実装例へのリンクを貼ります。(以下の実装では二分探索ではなく並列二分探索を行うことで定数倍をわずかに良くしています。)
追記：さらに頑張ると \(N\) が一個落ちて \(\mathrm{O}(N^3 \log N \log L / W)\) となり、想定解とほとんど変わらない計算量で通すことができます。(アルゴリズムの詳しい説明は省略します。)
posted:
last update: