Official

E - Good Partition Editorial by tsutaj

いくつかのステップに分けて解説します。

問題の言い換え

部分列のスコアに寄与するのは、列に含まれる要素の最大値と最小値のみです。よって、部分列の端にあって、部分列の最小値でも最大値でもない要素は無視できます。

このことから、問題を次のように言い換えても求める答えが同じであることがわかります。

長さ \(N\) の数列 \(A\) が与えられます。この数列から、いくつかの連続する空でない部分列を、部分列同士が交わりをもたないように選びます。

最適に部分列を選んだときの、選んだ部分列のスコアの和の最大値を求めてください。

また、言い換え後の問題で選ぶ部分列は、次のいずれかに限定してよいです。

  • 部分列の左端が部分列の最小値であり、右端が部分列の最大値である
  • 部分列の左端が部分列の最大値であり、右端が部分列の最小値である

動的計画法の適用

動的計画法で使う配列 \(\mathrm{dp}\) を次のように定めます。

  • \(\mathrm{dp}[i] :=\) \(i\) 番目の要素までを見たときのスコアの和の最大値

これは次のように更新できます。

  • \(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \mathrm{dp}[i - 1] \right\}\)
    • \(a_i\) を部分列に含めない場合に対応
  • \(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \max_{k < j < i} \left( \mathrm{dp}[j - 1] + a_i - a_j \right) \right\}\)
    • \(a_j\) を部分列の最小値として、\(a_i\) を部分列の最大値として使う場合に対応
    • \(k\) は、\(k < i\) かつ \(a_k \geq a_i\) を満たす最大の添字
  • \(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \max_{k < j < i} \left( \mathrm{dp}[j - 1] + a_j - a_i \right) \right\}\)
    • \(a_j\) を部分列の最大値として、\(a_i\) を部分列の最小値として使う場合に対応
    • \(k\) は、\(k < i\) かつ \(a_k \leq a_i\) を満たす最大の添字

しかし、 \(j\) の範囲をすべて探索すると実行制限時間に間に合いません。

動的計画法の高速化

実行制限時間内で実行するには、次を行う必要があります。

\(k\) を高速に求める

\(a_k \geq a_i\) を満たす最大の添字は、主に次の方法のいずれかで求められます。

  • stack を使う
  • 平衡二分探索木 (set) を使う
  • セグメント木を使う

ここでは stack を使う場合について説明します。\(i\) 番目の要素に対応する \(k\) を求めるときは次のように処理します。これを \(i\) の昇順に行います。

  1. stack の一番上の要素が \(a_i\) 未満である限り、stack から要素を取り除くことを繰り返す
  2. stack に残った一番上の要素の添字が \(k\) に対応するので、これを記録する
    1. 空である場合は \(k = 0\) とみなす
  3. stack に \(i\) 番目の要素を追加する

\(A\) の各要素は、stack に高々 \(1\) 回しか追加・削除の操作が行われないため、この処理全体の計算量は \(O(N)\) となります。

\(a_k \leq a_i\) を満たす最大の添字についても同様に求められます。

区間（\(k < j < i\) の範囲）に対する操作を高速に行う

\(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \max_{k < j < i} \left( \mathrm{dp}[j - 1] + a_i - a_j \right) \right\}\) の高速化を考えます。

\(\max_{k < j < i}\) の項は \(j\) に対するループ処理なので、\(j\) に依存しない部分は外に出すことができます。よって、 \(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \max_{k < j < i} \left( \mathrm{dp}[j - 1] - a_j \right) + a_i \right\}\) と変形できます。

ここで、\(\mathrm{dp}[j - 1] - a_j\) を管理するセグメント木を用意し、区間最大値を求めることで、この処理を \(O(\log N)\) に高速化できます。

\(\mathrm{dp}[i] \leftarrow \max \left\{ \mathrm{dp}[i], \max_{k < j < i} \left( \mathrm{dp}[j - 1] + a_j - a_i \right) \right\}\) についても、\(\mathrm{dp}[j - 1] + a_j\) を管理するセグメント木を用意することで同様に高速化できます。このため、セグメント木は 2 本必要になります。

まとめ

この問題は以下のようにして解くことができます。全体の計算量は \(O(N \log N)\) です。

  • 問題を言い換えて、部分列の端を最大値または最小値に限定する
  • 動的計画法で管理する状態とその遷移を考える
  • 動的計画法を高速化する

別解

上記の解説では貰う DP の方針ですが、配る DP を高速化することもできます。詳しくはソースコード 2 をご覧ください。

また、ここで書かれている解法とは異なるアプローチによって、言い換え後の問題を \(O(N)\) で解くこともできます。詳しくは他の解説ページをご覧ください。

ソースコード

posted:
last update: