B - Minimize Topological Order 解説
by 
PCTprobability
\(f(T) = P\) を満たす \(T\) の条件としては、まず根が頂点 \(P_1\) である必要があります。以降これを仮定します。
また、\(T\) が根付き木となるため、\(T\) のトポロジカルソートとして \(P\) が取れるために \(i \ge 2\) に対して頂点 \(P_i\) の親は頂点 \(P_1,P_2,\dots,P_{i-1}\) のいずれかである必要があります。
更に、\(P_i > P_j(i < j)\) を満たす \(i,j\) に対して、頂点 \(P_j\) の親は頂点 \(P_i,P_{i+1},\dots,P_{j-1}\) のいずれかである必要があります。もしこれを満たさないとすると、辞書順最小のトポロジカルソートを頂点 \(P_{i-1}\) まで構築した時に頂点 \(P_j\) の親は既に選ばれているため、次に選ぶ頂点は少なくとも頂点 \(P_i\) ではなくなってしまうためです。
そして、これらが十分条件です。根が頂点 \(P_1\) な根付き木 \(T\) に対して \(f(T) = P\) を満たすためには \(1 \le i < N\) を満たす整数 \(i\) に対して、親が頂点 \(P_1,P_2,\dots,P_i\) のいずれかである頂点のうち、番号が最小なものは頂点 \(P_{i+1}\) であると言えればよいですが、これは上記の条件から導出できます。
よって、\(2 \le i \le N\) に対して \(L_i\) を「\(P_j > P_i(j < i)\) を満たす最大の \(j\)(存在しなければ \(1\))」とすると、この問題は以下の問題に帰着出来ます。
長さ $N$ の整数列 $c=(0,0,\dots,0)$ がある。今から $i = 2,3,\dots,N$ に対して以下の操作を行う。
- $L_i \le j \le i-1$ を満たす整数 $j$ を選び、$c_j$ を $1$ 増やす。
操作終了時の $\sum_{i=1}^{N} A_i c_i^2$ としてあり得る最小値を求めよ。
重要な性質として、区間 \([L_2,1],[L_3,2],\dots,[L_N,N-1]\) から区間を \(2\) 個取ってくると、共通部分を持たないか内包の関係にあるかのどちらかを満たします。つまり、区間 \([L_x,x-1],[L_y,y-1]\) であって \(L_x < L_y \le x-1 < y-1\) を満たすものは存在しません。もしこのような \(x,y\) が存在したとすると、以下を全て満たします。
- $L_y < x < y$ より、$P_x < P_y$
- $L_x < L_y < x$ より、$P_{L_y} < P_x$
- $L_y$ の条件より、$P_{L_y} > P_y$
これは矛盾するため、交差する \(2\) 区間は存在しないことが証明出来ました。また、\(x^2\) の凸性により上記の問題を以下のように言い換えることが出来ます。
点 $1,2,\dots,N$ があり、点 $i$ には $A_i,3A_i,5A_i,\dots$ が書かれている。今から $i = 2,3,\dots,N$ に対して以下の操作を行う。
- 点 $L_i,L_i+1,\dots,i-1$ のいずれかに書かれている整数を $1$ 個選び、消す。
選んだ $N-1$ 個の整数の総和としてあり得る最小値を求めよ。
狭い区間から順に、今選べる中で最小の整数を選ぶ貪欲法が正当です。タイブレークは何でもよいです。
証明をします。もし区間 \([l,r]\) 内の最小の整数のいずれかである \(m\) を選ばず、\(m'\) を選んだ操作があったとします。そのような操作のうち、始めてのものを取ってきます。
- $m$ を $N-1$ 回の操作全体で選ばない場合
- $m$ をこれ以降のある区間 $[l',r']$ で選ぶ場合
今回の操作で $m'$ ではなく $m$ を選んだことにしても損しません。
$[l,r],[l',r']$ が $m'$ という共通部分を持つこと、また $r-l \le r'-l'$ であること、そして先ほど示した区間の性質から $[l',r']$ は $[l,r]$ を内包します。よって、$[l,r]$ で $m$ を、$[l',r']$ で $m'$ を選んだことにしても損しません。
よって、\([l,r]\) で \(m\) を選ぶ最適解の存在が証明出来ました。この議論を繰り返すことで、貪欲法によって得られる解が最適解であることも証明できます。
\(L\) を求める部分は stack で \(\mathrm{O}(N)\) で、貪欲法はセグメント木を使えば \(\mathrm{O}(N \log N)\) で行えるため、この解法は全体 \(\mathrm{O}(N \log N)\) です。