2 再帰から動的計画法（下）

コース内容#

三つの最適化方法#

① 状態遷移プロセスの最適化

状態定義を変更せず、特別なデータ構造やアルゴリズムを使用して遷移プロセスを最適化
例：卵を投げる V2

② プログラム実装の最適化

状態定義は変わらず、遷移プロセスも変わらない
例：0/1 ナップサック問題、コイン問題 [ローリング配列]

③ 状態定義の最適化

大量のトレーニングによって培われる能力、源から最適化
例：卵を投げる V3

【⭐】状態定義 -> 源、遷移プロセス -> プロセス、プログラム実装 -> 結果

授業中の練習#

——— 動的計画法 ——#

HZOJ-46：回文の切断#

サンプル入力

sehuhzzexe

サンプル出力

考え方
- 文字列の長さは 50 万、タイムアウトに注意
- 通常版
  - 状態定義 [最長上昇部分列に似ている]
    - $dp [i]$：文字列の前 $i$ 文字を取ると、最小で何段の回文文字列に分けられるか
    - 段数の方が理解しやすい、最小の切断数 + 1 に等しい
  - 状態遷移
    - $dp[i]=min{dp[j]} + 1\ |\ j<i,\ s[j+1,\ i]\ is\ palindrome$
      - 状態集合：$dp [j]$、$j + 1 \to i$ 位置の文字列は回文文字列
      - 決定：$min$
  - 時間計算量：$O (n^2)$、遷移段階を最適化できる
- 最適化版 —— 遷移プロセス
  - 現象：実際には回文文字列は非常に少ない
  - 最適化：各回文の位置を事前に保存
    - すなわち、事前に処理して得られる $mark$二次元配列
      - $mark [i]$ は $i$ 位置で終わる回文の開始座標を保存している [複数ある可能性あり]
    - したがって、遷移プロセスでは、処理済みの $mark$ 配列を利用することで、大量の重複ループを回避できる
  - 状態遷移方程式 👉$dp [i]=min {dp [mark [i][j]-1]} + 1\ |\ j<i$
    - 状態集合のサイズ：$sizeof (mark [i])$、すなわちその部分文字列の回文の数
  - 時間計算量：$O (n \times m)$、$m$ は文字列中の回文の数
コード
- 通常版
  - 文字列と dp 配列は 1 つずれている
    - for ループの $i$、$j$ は dp 配列のインデックスに対応し、回文の $i$、$j$ は文字列に対応するため、各 - 1
  - $dp [i]$ を初期化、現在の文字は必ず回文である [段数に関係なく、遷移できるかどうか]
    - 実際には $j = i -1$ のケース
  - 時間計算量：$O (n^2)$
    - 2 つのループと回文判定だけを単純に見ると $O (n^3)$ のように見えるが、平均時間計算量の観点から考える必要がある
- 最適化版
  - 【注意】
    - $mark$ 配列は二次元で、第一次元は vector 構造を使用することで第二次元の長さを決定する必要がなく [部分文字列の回文の数に応じて変化]、開始座標の追加も便利
    - 各配列のインデックスの開始点は、文字列が 0 から始まるのみ
    - 回文の拡張の考え方は、中心から両側に広がる必要があり、奇数と偶数の文字数を考慮する

ナップサック類問題：限られたリソースで最大のリターンを得る / 最小のコストで最大のリターンを得る問題

HZOJ-47：0/1 ナップサック#

サンプル入力

サンプル出力

考え方
- アイテム数は有限で、選択 / 非選択の 2 つの状態のみ
- 状態定義
  - $dp [i][j]$：前 $i$ 件のアイテムで、ナップサックの最大重量が $j$ のときに得られる最大価値
- 状態遷移
  - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]&i 件目を選ばなかった場合 \&dp [i - 1][j - v [i]] + w [i]&i 件目を選んだ場合 \end {aligned}\right.$
  - 状態集合：i 件目を選ばなかった場合、選んだ場合の 2 つの状態
  - 決定：$max$
  - 注意：問題中で：v は重量、w は価値を表す
- 時間計算量：$O (n\times V)$
コード
- V1：状態の定義に従ってプログラムを実装
  - 遍歴の起点に注意し、状態を漏らさないようにする
  - この方法は美しくない
- V2：ローリング配列 👉 空間の最適化
  - i 次元は毎回現在の行と前の行の値のみを使用するため、2 次元で十分
  - i 次元でmod 2を統一する
- ⭐V3：プログラム内の dp 配列を 1 次元に、v、w 配列を 0 次元に、更新順序を変更
  - 上記のコードを理解するには、3 つの質問に答える必要がある：
    - ① なぜ dp 配列は 1 次元で十分か
    - ② なぜ v、w 配列は必要ないか
    - ③ なぜ $j$ は逆順か
  - 解答：
    - ① 思考はまだあり、状態定義は依然として二次元であるが、コード実装の最適化に過ぎない
    - ② $i$ はアイテムの件数を表し、以前のコードからわかるように、v、w は $i$ 件目のアイテムにのみ関心があるため、1 件のアイテムを読み込み、処理することができる
    - ③ まずは①の問題を理解し、状態遷移コードは等式の右側の $dp [j]、dp [j-v]$ が【アイテム件数】次元のインデックスで $i - 1$ であることを保証する必要がある；正順の場合、$dp [j-v]$ に対応するインデックスはすでに i になり、$dp [i-1][j-v]$ は失われてしまう
  - ❗ ここで j の遍歴範囲は以前の $1\to V$ から $V\to v$ に変わった
    - これは未遍歴の $v\to 1$ 部分の値は変更する必要がなく、そのまま保持すればよい [dp は 1 次元]
    - 以前のコードは $i-1$ 次元の値をコピーしただけである [dp は 2 次元で、そうでなければ初期の 0]

HZOJ-48：完全ナップサック#

サンプル入力

サンプル出力

考え方
- 状態定義 [0/1 ナップサックと同様]
  - $dp [i][j]$：前 $i$ 種類のアイテムで、ナップサックの最大重量が $j$ のときに得られる最大価値
- 状態遷移
  - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]&i 種類目を選ばなかった場合 \&dp [i][j - v [i]] + w [i]&i 種類目を若干選んだ場合 \end {aligned}\right.$
  - ❗ 注意：2 つ目の遷移状態では、i 種類目のアイテムをいくつ選んでも、アイテムの種類は前 $i$ 種類である。なぜなら、各種類のアイテムは無限に使用できるため、上の問題との最大の違いであり、コイン問題に似ている
    - ここで i 種類目のアイテムの空間を確保するだけでよい
- 時間計算量：$O (N \times V)$
コード
- 上の 0/1 ナップサックの第 3 の実装方法の表の順序とは逆で、j を正順に遍歴する必要がある。上文 [❗] を理解すればこの部分も理解できる

HZOJ-49：多重ナップサック#

サンプル入力

サンプル出力

考え方
- 通常版
  - 🆒問題モデルの変換：各アイテムを複数の独立したアイテムとして扱い、0/1 ナップサック問題に変換
  - 状態定義と状態遷移は 0/1 ナップサックと一致
  - 状態定義
    - $dp [i][j]$：前 $i$ 件のアイテムで、ナップサックの最大重量が $j$ のときに得られる最大価値
  - 状態遷移
    - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]&i 件目を選ばなかった場合 \&dp [i - 1][j - v [i]] + w [i]&i 件目を選んだ場合 \end {aligned}\right.$
  - 時間計算量：$O (n\times V\times s)$、最適化可能
- 最適化版 —— 遷移プロセス⭐
  - 二進法分解法を使用して、同じアイテムの遍歴回数を減らす
  - 本質的には、特定のアイテムのクラスについて、具体的に何件選ぶかを決定することが最適解である
  - 例：1 種類のアイテムが 14 件ある場合
    - 通常の単一分解法 ——14 回のループが必要で、特定の種類のアイテムを $1 \sim s$ 件選ぶすべての状況を列挙
    - 二進法分解法 ——4 回だけで、14 件のアイテムを 1、2、4、7 件のアイテムからなる4 つの山に分けることができる
      - 同じ効果を達成でき、分解された数も少なくなる
      - 各分解の数は前の山の 2 倍で、不足している場合は残りをすべて放置する
    - 分解 $s$ 件のアイテムの数の比較：通常の分解法：$s$ 件；二進法分解法：$log\ s$ 件
  - 時間計算量：$O (V\times \sum_{i=1}^{n}{logs_i})\approx O (n \times V\times log\ s)$
  - [PS] 二進法分解法のみ使用可能
    - 各山のアイテムについて、選択と非選択の 2 つの状態しかないため、遷移プロセスでも選択と非選択の 2 つの結果しかない
    - したがって、他の進数を使用することはできない
- 最適時間計算量：$O (n \times V)$—— 単調キューを借りて、後で説明
コード
- V1：0/1 ナップサック問題として扱う
  - 時間効率は高くない
- V2：遷移プロセスを最適化
  - 二進法分解法を使用
  - 2 倍ずつ、小さいものから大きいものへ分解し、すべての状況を遍歴する
  - 遷移方程式において件数 $k$ を考慮

HZOJ-50：卵を投げる#

サンプル入力

2 100

サンプル出力

考え方
- 【探索の考え方】
  - 求めるものを解読：最悪の場合に最小で何回測定するか
    - 測定回数は、測定方法に関係がある
    - 最悪の場合、測定プロセス中に運が最悪であることを示す
    - 👉 最良の戦略、最悪の運
  - 例：2 個の卵、ビルの高さは 100
    - 二分法：確実にタイムアウト、卵の数は有限
      - [最悪の場合]
      - 最初の卵でビルの高さ 50 を測定し、割れた
      - 2 番目の卵は最初の階から上に測定するしかない
      - 最終的に 50 回測定する必要がある [最悪の場合→硬度は 49]
    - カスタム戦略：10 階ごとに上に測定
      - [最悪の場合]
      - 10、20、30、...、100、100 で卵が割れた
      - 91、92、...、99 を再度測定
      - 最終的に 19 回測定する必要がある [硬度は 99]
    - 測定回数を x 回と仮定
      - [最悪の場合、測定できる階数は以下の通り、測定回数は x を保証]
      - 最初：$x$
      - 2 回目：$x + (x - 1)$
      - 3 回目：$x + (x - 1) + (x - 2)$
      - 最後：$x + (x - 1) + (x - 2) + ... ＋ 1$、1 まで加えるのは測定できる階数を最大にするため、すなわち最適戦略
      - 等差数列の和を計算：$(x + 1) \times x \div 2>=100$ のときの x の値は 14
      - したがって：2 個の卵で 100 階のビルを測定するには、最小で 14 回測定する必要がある
  - インスピレーション：固定された測定回数の状況で、測定戦略を発見
- V1：通常版
  - 状態定義
    - $dp [i][j]$：i 個の卵で j 階を測定する場合、最悪の場合に最小で何回測定するか
  - 状態遷移
    - $dp [i][j] = min_k (max\left {\begin {aligned}&dp [i - 1][k - 1]+1 & 卵が割れた場合 \&dp [i][j - k]+1 & 卵が割れなかった場合 \end {aligned})\right.$
    - k：k 階から卵を投げる
    - max：運が最悪
    - min：最小の測定回数 [すべての k を列挙し、最小値を取る]
    - 決定：2 つの状態の中から最大値を取り、すべての階に対応する結果の中から最小値を取る
  - この方法は思考は正しいが、明らかな空間と時間の制限がある。コードを参照 ——V1
- V2：遷移プロセスを最適化
  - V1 バージョンには 3 層のループがあるが、$k$ を求める min のプロセスを最適化することで 2 層のループに変えることができる
  - ① 卵の数 $i$、階数 $j$ を固定し、$k$ と $dp [i - 1][k - 1]$、$dp [i][j - k]$ の関係を観察
    - 前者 $dp [i - 1][k - 1]$ は $k$ と正の相関があり、後者 $dp [i][j - k]$ は $k$ と負の相関がある
    - そして min (max ()) を求めるため、図に示すように、両者の取る max の値を求める必要があるため、両者が交差する場所が最適な k 値である
    - 👉 最適な遷移 k 値は、必ず 2 つの関数の交点近くで発生する [PS：k の取値は離散的]
  - ② 卵の数 $i$ を固定し、階数 $j$ と最適な $k$ の関係を観察
    - 階数 $j$ が増加すると、緑の線は影響を受けず、赤の線は全体的に上に移動し、最適な $k$ 値も上昇する
    - 正確には、$k$ は少なくとも小さくならない。なぜなら k 値は離散的であり、階数 $j$ が一定の範囲で増加する場合にのみ、$k$ も増加し、総測定回数が増加する [対応する曲線は階段状]
  - 総合的に2 つの結論をまとめる
    - 仮に $dp [i][j-1]$ に対応する最適解を $k_1$ とすると、$dp [i][j]$ に対応する最適解 $k_2\geq k_1$[必ず]
      - さらに $k_2$ は $dp [i-1][k_2-1]\leq dp [i][j-k_2]$ 条件を満たす必要がある [①]
    - もし満たすなら、$k_2$ はその条件を満たす最大値である。なぜなら $k$ は最大で 1 つ増えるから
    - したがって、階数が 1 つ増えると、$k_2$ は 1 つ増えるか、変わらない【⭐】
      - $k_2= \left {\begin {aligned}&k_1+1&dp [i-1][k_1]\le dp [i][j-k_1 - 1]\&k_1 & その他 \end {aligned}\right.$
      - もし $k_2=k_1+1$ を条件 [①] に代入すると成立するなら、$k_2=k_1+1$
  - 本質的には min を求めるプロセスを最適化しており、時間計算量は質的に飛躍している。コードを参照 ——V2
- V3：状態定義を最適化
  - 状態を再定義
    - 元の状態定義 $dp [i][j] = x$ とし、$x$ は最小の測定回数を表す
    - 分析：元の状態定義に必要なストレージは階数 $j$ に関連し、$j$ の値域は非常に大きいため、配列に収まらない；対照的に、$x$ の値域は小さく、例えば $i = 2$ の場合、$x \le \sqrt {2j}$[平方根関係]
    - テクニック：ある自変数と因変数の間に関連性があることがわかった場合、両者を入れ替えることができる
    - ⭐再定義：$dp [i][x] = j$、$i$ 個の卵で $x$ 回投げた場合、最大で何階測定できるか
  - 状態遷移
    - $dp[i][x] = dp[i][x - 1] + dp[i - 1][x - 1] + 1$
    - 測定できる最大階数 = 上 [割れなかった] + 下 [割れた] + 1
    - 注意：dp 配列の要素が表す意味はすでに階数に変わっている
    - この時点で動的計画法の問題ではなく、再帰の問題になり、決定はない
  - 最後に $dp [n][x]≥m$[与えられた階数] を満たす最初の方法数 $x$ を見つける。これが答えである
  - 🆒最終的に V1 バージョンの空間と時間の制限を解決した
  - [PS] 値域の差があまりない場合、変換する意味はなく、関連する変数が見つからなければ変換できない
- 注意：すべての遷移公式は少なくとも 2 個の卵の状況に対しているため、1 個の卵の状況を初期化することを忘れないでください
コード
- V1
  - 範囲内で最小値を求める場合、一般的に極端な値を初期化する必要がある
  - 空間制限
    - このプログラムが使用するストレージは階数に強く関連している
    - 階数は $2^{31}$ に達しているため、この状態定義は要求を満たすことができない
    - 👉 状態定義を最適化する必要がある
  - 時間制限
    - 時間計算量：$O (n \times m^2)$
    - m が大きすぎると、時間消費が大きくなる
  - [PS] dp 配列の第一次元は圧縮でき、ローリング配列を利用できるが、第二次元の圧縮の突破口はここにはない
- V2：遷移プロセスの最適化
  - 【重要】転換点の結論に基づき、現在の卵数 $i$、階数 $j$ に対応する最適な $k$ が + 1 できるかどうかを判断
  - 時間計算量 ->$O (n \times m)$
  - [個人的な考え] ここでの転換点の結論は、$dp [i-1][k-1]\ge dp [i][j-k]$ の最小値を満たす場合でも可能である（その値を $k_2$ とし、$dp [i-1][k-1]\le dp [i][j-k]$ の最大値 $k_1$ と比較すると、$k_2=k_1+1\ or\ k_2=k_1$）、なぜなら両者の曲線（階段状）は対称的である（34 行目が $dp [i - 1][k] <= dp [i][j - k]$ に変更されると、OJ 上で同じ効果が得られるため）、したがって $k_2=k_1+1$ の場合、$dp [i-1][k_2-1]=dp [i-1][k_1-1]+1$ の同時に、$dp [i][j-k_2]=dp [i][j-k_1]-1$ となるため、求める答え $max {dp [i-1][k_2-1],\ dp [i][j-k_2]} + 1$ は変わらない
    - 実際には確かに対称的であり、数学的帰納法で証明できる
- V3：状態定義の最適化
  - 再帰問題に変わり、dp [][]->f [][]
  - f 配列は long long 型を使用し、階数は最大で $2^{31}$ で int 範囲内であるが、卵数は最大 32 で、階数が int を超える場合、未定義の動作が発生する可能性がある
  - f 配列の第二次元のサイズは 70000 に設定されている。なぜなら、卵数が 2、階数が $2^{31}$ の場合、対応する x 値は $65536=2^{16}=\sqrt {2^{31}\times 2}$ である
  - プログラムの最適化：ローリング配列ストレージに変更；階数に基づいて f 配列の第二次元のサイズを推定し、動的に配列を開発できる。なぜなら、毎回 70000 の大きさを開発する必要はないから
  - [PS] 再帰 + メモ化を使用して実装することも可能

HZOJ-44：最長上昇部分列#

サンプル入力

10
3 2 5 7 4 5 7 9 6 8

サンプル出力

考え方
- 通常版
  - 選択できる最長厳密上昇部分列[連続して選ぶ必要はない]
  - 状態定義
    - $dp (i)$：インデックスがiの要素で終わる最長厳密上昇列の長さ
    - 必ずi で終わる必要がある！
  - 状態遷移
    - $dp(i) = max{dp(j)} + 1\ |\ j<i,\ val(j) < val(i)$
    - $dp (i)$ に遷移できるすべての状態：$j<i,\ val (j)<val (i)$ の条件を満たす $f (j)$、合計 i 個
    - 決定：$max$
  - 最終的な答え：$max (f (i))$、すべての $dp (i)$ の中から最大値を取る
  - 状態遷移の時間計算量：$O (n^2)$
- 最適化版—— 遷移プロセス
  - ⭐$len$ 配列を追加し、$len [i]$ は長さ $i$ の [厳密上昇] 列の末尾の最小値を表す
  - 状態遷移
    - 導入：
      - 上の図の $len$ 配列を参照すると、実際には $i$ が長さを表し、$min$ が末尾の最小値を表す
      - 考える：新しい $val [i]=5$ があるとき、$len$ 配列の中でどの値の後に接続するのが最適か？
        
        ① まず、列の末尾の値がそれより小さい必要がある 👉$len [k] \lt val [i]$
        
        ② その後、列の長さが大きいほど良い 👉接続位置 $i$ が大きいほど良い
      - 変換：$len$ 配列の中で $val [i]$ より小さい最後の値のインデックス $k_{last}$ を見つけ、+1 すれば接続位置が得られる；$len [k_{last} + 1]$ の値を $val [i]$ に更新する。なぜなら、更新前 $val [i]\le len [k+1]$ は必ず成立するからである。そうでなければ、$k_{last}$ は最後の値ではない
      - すなわち：$dp [i]=k_{last}+1\ |\ len [k] \lt val [i]$、特殊な二分探索を含む
    - 実際には最初の大きさを持つ$val [i]$ を見つけることに等しい
      - $dp [i]=k_{first}\ |\ len [k] \ge val [i]$、特殊な二分探索を含む。$len [k_{first}]=val [i]$ を更新すればよい
      - より簡潔であり、後のコードもこのように実装される
  - 二分探索が可能であるための前提条件は $len$ 配列の単調性
    - 証明：$len$ 配列は必ず単調である。すなわち証明
    - ① 初期は単調である
      - 初期時には 0、∞、∞に設定すればよい
    - ② 更新前は単調であり、更新後も単調であると仮定する
      - 更新操作：$len [k]=val [i]$
      - 更新前：$len [k-1] <= len_原 [k]$
      - 更新後：$len [k-1] < val [i] =len_新 [k]<=len_原 [k]$
    - したがって、単調である
  - 時間計算量：$O (n\times log\ l)$
    - $l$ は最長上昇部分列の長さ、すなわち答えでもあり、$len$ 配列の最終的な有効長さでもある
    - 二分探索を使用して遷移プロセスを最適化した
  - 【重要】単調配列を維持し、その配列は求めるものと強く関連しており、実際には二分探索を使用している
コード
- 通常版
  - データが大きいため、scanf を使用し、cin ではなく
  - 2 つの max の意味に注意
  - 状態遷移の時間効率が低い
- 最適化版 —— 状態遷移
  - 単調配列の維持と特殊な二分探索0000011111 に注意
    - 二分探索時、ans + 1 は各要素を追加するたびに最大長さが最大 + 1であることを示す
  - ans は len 配列の最後の非極大値のインデックスを表し、現在の列の最長上昇部分列の最大長さでもある
  - [PS]
    - dp、val 配列を開く必要はなく、常に現在の状態の値のみを使用する
    - memset を使用して無限大の操作を設定する：なぜプログラマーは INF を 0x3f3f3f3f に設定するのが好きか—— 知乎

—— 単調キュー / スタックの結合 ——#

3 単調スタックと単調キューの知識に基づいて

HZOJ-51：矩形#

サンプル入力

6 6
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
1 0 1 1 1 1

サンプル出力

考え方
- 再帰+ 単調スタック
- 注意：結果が大きくなる可能性があるため、出力時に 100007 で割る
- 【常識】左上の座標 + 右下の座標 👉 唯一の 1 つの小さな矩形
- 問題の変換：まず 1 行に対して、右下の座標がその行のある点に落ちるとき、構成できる合法的な部分矩形の数を求める [その点に対応する合法的な左上の座標がいくつあるか]；その後、すべての点の数を累積すればよい
- 観察を通じて、上記の部分問題をさらに 2 つの部分問題に変える
  - まず、左側で $x$ 点に最も近い、小さい $x$ の高さ [上に数える連続した白いマスの数] の位置 $i$ を見つける
  - したがって【状態定義】$x$ を右下の座標として構成できる合法的な部分矩形の数 $f (x)$ は次のように満たす👇
  - 【再帰公式】$f (x) = f (i) + h_x\times (x - i)$
    - $i$ 点を右下の座標として持つ部分矩形の数 $f (i)$ は、対応する合法的な左上の座標の数であり、これらの座標は $x$ 点の合法的な左上の座標としても使用できる
    - すなわち：左側の合法的な矩形の数 $f (i)$➕右側の合法的な矩形の数 $h_x\times (x - i)$
  - $x$ の最近小さい値 $i$ を求める必要があるため、単調スタックを使用する
- [インスピレーション] 最近の大きさや小ささを探す必要がある場合、単調スタックを思い出すべきである [一般的には他のアルゴリズムと組み合わせて使用される]
コード
- 配列が必要な場所：単調スタック、矩形の高さ、再帰状態
- 注意：仮想の木板を残し、再帰状態の初期値を初期化し、スタックの底を初期化する
- 一般的な単調スタックのルーチン：単調性を維持→値を取る→スタックに入れる
- [PS] 2 回割ることで、未割りの $f [j]$ と $ans$ の合計が範囲を超えるのを防ぐことができる。実際にはこの問題では超えない；さらに、$f [j]$ が超えるのを防ぐことはできない [もし発生した場合]。なぜなら $f [j]$ はすでに計算されているからである

HZOJ-52：古いタイプライター#

サンプル入力

6 40
3 3 6 5 1 2

サンプル出力

考え方
- 動的計画法+ 単調キュー
- 状態定義：$dp [i]$ は前 $i$ 文字を印刷するための最小消費値を表す
- 状態遷移
  - 問題の意図に基づき：$dp [i]=min {dp [j]+(s_i-s_j)^2+M}\ |\ j<i$、ここで $s_i$ は前の和 $s_i=\sum_{k=1}^ic_k$
    - 前の印刷の可能な終了位置 $j$ を列挙し、最適なものを探す
  - 時間計算量：$O (n^2)$
- 傾きの最適化 [⭐特に優れた一種の最適化アルゴリズム]
  - ① 状態遷移公式 [消費値公式] の構成を分析
    - 主に混合項を排除する
  - ② 実際には、どの状態から遷移するのがより優れているかを見つける必要がある。仮に $j$ からの遷移が $k$ からの遷移より優れている、すなわち消費値が小さい場合、次のようになる
    - ↓
    - $dp[j] + (s_i - s_j)^2 + M < dp[k] + (s_i - s_k)^2 + M$
    - ↓
    - $dp[j] + s_j^2 - 2s_is_j<dp[k] + s_k^2 - 2s_is_k$
    - ↓
    - $(dp[j]+s_j^2)-(dp[k]+s_k^2)<2s_i(s_j-s_k)$
  - ③ さらに変換し、傾きの形に変える
    - $f (i)=dp [i]+s_i^2$ とする
    - ↓ 【傾き関係 (Ⅰ) 】
      - $g(j,k)=\frac{f(j)-f(k)}{s_j-s_k}<2s_i$
    - 👉 傾き [$s$ を横座標、$f$ を縦座標とする]
    - この時点で、もし傾き関係 (Ⅰ) が成立すれば、$j$ からの遷移は $k$ より優れている
  - ④ どのように傾き関係 (Ⅰ) をさらに利用するか？次の図を分析すると、$l$、$k$、$j$ の 3 点がある
    - 【このシーン】直線 $lk$ の傾き > 直線 $kj$ の傾き [弓背型]
    - 2 つの傾きと $2s_i$ の関係を分析すると、3 つの状況がある。図中の①、②、③を参照
    - さらに傾き関係 (Ⅰ) を分析すると、どの点から遷移するのが最も優れているかがわかる。九宮格✔の部分を参照
    - 見ると、最適な状態になるためには、$k$ がないことが必ず必要である
    - 👉 候補の答えの中には、必ず弓背型がない
  - ⑤ 最終的にこのプロセスは、候補状態の間で前者の傾きが後者の傾きより小さくなければならないことを保証することに変換される
    - 傾き関係 (Ⅰ) と傾きの増加の特性に基づき、求める最適遷移状態は頭部に近い
      - まず、傾き関係 (Ⅰ) に基づいて、頭部に関連する要素 $x_1$、$x_2$ を削除する【出隊】
      - この時点で残った最も左の要素が最適な遷移状態 $x_3$【隊首】
      - 新しい状態 $x_6$ を追加する場合：弓背型の原則に基づいて、まず隊尾の非候補状態 $x_4$、$x_5$ を削除し、次に $x_6$ を追加する【単調性を維持 + 入隊】
    - 👉 すなわち、【単調キュー】を維持し、区間の最小値を維持する
  - 時間計算量：$O (n)$
コード
- 傾きの最適化の考え方が重要であり、傾き関係 (Ⅰ) の公式と傾きの比較（弓背型の判断）を注意深く使用する
- 単調キューの問題に変換する：出隊→値を取る→単調性を維持→入隊
  - 順序は問題の意図に応じて調整
- [PS]
  - 傾きの最適化の考え方があれば、公式をそのまま適用すればよい
  - 単純に文字の消費値の配列を保存する必要はなく、前の和の情報のみが必要である

ヒント#

知識には限界がない。大学があれば、限界がある。