D - Inc, Dec - Decomposition Editorial
by 
maspy
\(2\) つの解法を解説します。
- DP の高速化として得られる \(\Theta(N\log N)\) 時間計算量での解法：https://atcoder.jp/contests/arc123/editorial/2254
- 最適解の構造を調べることで得られる \(\Theta(N)\) 時間計算量での解法：この解説
この解説において、問題の数列 \(C\) のすべての項を \(-1\) 倍した数列を改めて \(C\) と書くこととします。つまり、広義単調増加数列 \(B, C\) であって \(A_i = B_i - C_i\) を満たすものに関する問題と見なしておきます。
◆ 最適解の構造
次を示すことができます：
【補題】最適解 \((B, C)\) であって、任意の \(1\leqq i \leqq N - 1\) に対して \(B_i =B_{i+1}\) または \(C_i = C_{i+1}\) を満たすものが存在する。
このことを証明しましょう。最適解 \((B, C)\) のうちで、\(B_N - B_1\) が最小であるものをとります。\(1\leqq n \leqq N-1\) が \(B_n < B_{n+1}\) かつ \(C_n < C_{n+1}\) を満たすと仮定して、矛盾を導きます。
次の \(2\) 種の操作を考えます。
- 操作 \(\operatorname{prefix}_+\)：\(B_1, \ldots, B_n\) および \(C_1, \ldots, C_{n}\) に \(1\) を加える。
- 操作 \(\operatorname{suffix}_-\)：\(B_{n+1}, \ldots, B_N\) および \(C_{n+1}, \ldots, C_N\) に \(-1\) を加える。
これらの操作は、\(B\), \(C\) の広義単調増加性および \(A_i = B_i - C_i\) という条件を保ったまま \(B_N - B_1\) を \(1\) 減少させます。したがって、これらのどちらかの操作が最適性（\(\sum (|B_i| + |C_i|)\) の最小性）を保つことがいえればよいです。
次が確かめられます：
- \(B_n < 0\) のとき：\(\operatorname{prefix}_+\) が最適性を保つ。
- \(0< B_{n+1}\) のとき：\(\operatorname{suffix}_-\) が最適性を保つ。
実際 \(B_n < 0\) のとき、\(1\leqq i\leqq n\) に対して \(B_i < 0\) です。そのような \(i\) に対して操作 \(\operatorname{prefix}_+\) によって \(|B_i|\) は \(1\) 減少し、\(|C_i|\) は高々 \(1\) 増加であるのでよいです。\(0 < B_{n+1}\) のときも同様です。
\(B_n < B_{n+1}\) と仮定していたので、これらで場合分けは尽くされています。よって補題を証明することができました。
◆ 答えの計算
補題により、問題の考察を \(B_i =B_{i+1}\) または \(C_i = C_{i+1}\) が成り立つような \((B, C)\) に限定することができます。この場合、
- \(B_{i+1} = B_i + \max(0, A_{i+1} - A_i)\)
- \(C_{i+1} = C_i + \max(0, A_i - A_{i+1})\)
が成り立ちます。これと \(A_1 = B_1 - C_1\) より、全ての \(B_i, C_i\) は \(B_1\) を定めると一意に定まります。\(x = B_1\) とおくことで、結局次の形の問題に帰着されます：
\(2N\) 個の整数 \(p_1, \ldots, p_{2N}\) が与えられる。整数 \(x\) に対して \(\sum_{i=1}^{2N}|x - p_i|\) の最小値を求めよ。
この問題は、中央値の計算を利用して \(\Theta(N)\) 時間で解くことができます。
◆ 解答例
posted:
last update: