E - All Pair Shortest Paths Editorial
by 
maspy
ヒント → https://atcoder.jp/contests/arc158/editorial/5901
\(L, L+1, \ldots, R\) 列目のことを単に \([L, R]\) と書くことにします．\(X\) が \([L,R]\) 内のマスであることを \(X\in [L,R]\) と書くことにします．半開区間 \([L,R) = \{i\mid L\leq i<R\}\) についても同様の記法を用います．
[1] 解法 1
簡単のため \(x_i = x_{1,i}\), \(y_i = x_{2,i}\) と書くことにします．
\(1\leq i \leq N\) および，\(X\in [1, i]\) に対して次のように \(a_{i, X}\), \(b_{i, X}\) を定めます：
\[a_{i, X} = f\bigl((1,i), X),\quad b_{i, X} = f\bigl((2,i), X).\]
整数の \(2\) つ組の多重集合 \(S_i\) を \(S_i = \bigl\{(a_{i,X},b_{i,X})\mid X \in [1, i]\bigr\}\) により定めます．本問の答 \(\sum_{X,Y}f(X,Y)\) の計算に対して，\(X,Y\) の列番号のうち大きい方が \(i\) に等しいものの答を計算することを考えれば，各 \(i\) に対して \(\sum_{(a,b)\in S_i}(a+b)\) が計算できればよいことが分かります．以下この方法を考えます．
\(i\) 列目内の \(2\) マスがパスに含まれるかどうかで場合分けすれば，\(X\in [1,i-1]\) に対して次が成り立つことが分かります：
\[a_{i,X} = \min\bigl(a_{i-1,X} + x_i, b_{i-1,X} + x_i+y_i\bigr),\qquad b_{i,X} = \min\bigl(a_{i-1,X} + x_i + y_i, b_{i-1,X} + y_i\bigr),\]
よって整数の \(2\) つ組の多重集合 \(S_i\) を \(S_i = \bigl\{(a_{i,X},b_{i,X})\mid X \in [1, i]\bigr\}\) により定めると，
\[S_{i} = \bigl\{ \min\bigl(a + x_i, b + x_i+y_i\bigr),\min\bigl(a + x_i + y_i, b + y_i\bigr)\mid (a,b) \in S_{i-1}\bigr\} \cup \{(x_i,x_i+y_i), (x_i+y_i,y_i)\}\]
となります．
組 \(\bigl(\min\bigl(a + x_i, b + x_i+y_i\bigr),\min\bigl(a + x_i + y_i, b + y_i\bigr)\bigr)\) を，場合分けによって計算すれば，
\[\begin{cases} (a+x_i,a+x_i+y_i) & (a-b < -x_i)\\ (a+x_i,b+y_i) & (-x_i\leq a-b \leq y_i)\\ (b+x_i+y_i,b+y_i) & (y_i < a-b) \end{cases} \]
のようになります．この計算式が \(a-b\) の範囲で変わることや，興味のある値が \(a+b\) であることに注目して，\(S_i\) の代わりに \(T_i = \{(a-b,a+b)\mid (a,b)\in S_i\}\) を考えることにすれば，\((a,b)\in T_{i-1}\) に対する \(T_{i}\) の元は
\[\begin{cases} (-y_i,b+a+2x_i+y_i) & (a < -x_i)\\ (a+x_i-y_i, b+x_i+y_i) & (-x_i\leq a \leq y_i)\\ (x_i,b-a+x_i+2y_i) & (y_i < a) \end{cases} \]
となります．
目的のためには \(\sum_{(a,b)\in T_{i-1}} b\) と \(\sum_{(a,b)\in T_i} b\) の差分を求めればよく，これは \(a\) ごとの \(T_i\) の要素数を適切なデータ構造で管理することによって行えます． 例えば，C++ の std::map を利用して \(O(N\log N)\) 時間で解くことができます．また必要となるのは，最小値・最大値の取り出し・挿入だけなので，C++ std::deque を利用して \(O(N)\) 時間で解くこともできます．
[2] 解法 2
分割統治を利用します．
\(2\) マスとも \([L, R)\) 内に含まれるようなマスの \(2\) つ組 \((X,Y)\) に対する \(f(X,Y)\) の総和を求める問題を考えます（\(L=1, R=N+1\) とした場合が本問の答です）．
\(R - L \geq 2\) のとき，\(M = \lfloor\frac{L+R}{2}\rfloor\) として，次のように計算しましょう．
- \(X, Y \in [L, M)\) の場合について計算する．
- \(X, Y\in [M, R)\) の場合について計算する．
- \(X\in [L, M)\)，\(Y\in [M, R)\) の場合について計算する．
- \(Y\in [L, M)\)，\(X\in [M, R)\) の場合について計算する．
1 と 2 は，\([L, M)\) と \([M, R)\) について再帰的に同じ問題を解くという実装をします．3 と 4 の答は同じです．
以下では，3 を \(O\bigl((R-L)\log (R-L)\bigr)\) 時間で計算する方法を解説します（したがって，本問全体の計算量は \(O(N\log^2N)\) 時間です）．
\([L, M)\) に含まれるマス \(X\)， \([M, R)\) に含まれるマス \(Y\) に対して，次のように \(a_X, b_X, c_Y, d_Y\) を定めます：
- \(a_X = f\bigl((1,M-1), X\bigr)\)
- \(b_X = f\bigl((2,M-1), X\bigr)\)
- \(c_Y = f\bigl((1,M), Y\bigr)\)
- \(d_Y = f\bigl((2,M), Y\bigr)\)
\(X\) から \(Y\) への重み最小のパスでは，ちょうど \(1\) 回 \([L, M)\) から \([M, R)\) へ移動します．この移動が \(1\) 行目，\(2\) 行目のどちらであるかで場合分けすることを考えれば，\(f(X, Y) = \min (a_X + c_Y, b_X + d_Y)\) であることが分かります．
すべての \(X, Y\) に対する \(a_X, b_X, c_Y, d_Y\) は \(M\) 列目に近い列から順に計算することで \(O(R-L)\) 時間で計算できます．\(f(X,Y)\) の総和は，
\[f(X, Y) = a_X + c_Y + \min (0, b_X-a_X + d_Y-c_Y)\]
などと変形すると計算しやすいです．\(p_X = b_X - a_X\), \(q_X = d_Y - c_Y\) とおけば，
\[\sum_{X,Y}f(X, Y) = \sum_{X,Y}a_X + \sum_{X,Y}c_Y + \sum_{X,Y}\min (0,p_X+q_Y)\]
と書けて，この中で最も計算が難しいのは \(\sum_{X,Y}\min (0,p_X+q_Y)\) ですが，これもソートと二分探索や尺取り法により計算できます．
posted:
last update: