はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける動的計画法更新最適化まとめ

動的計画法更新最適化?

  • セグメント木や累積和
    • dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
    • dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
    • dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
    • みたいに区間和や区間最大最小をもたせることで更新を行う。
  • 行列累乗
    • DPの更新式を見てみると、一回の更新操作が行列の形になるときがある
    • この場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。
  • Convex Hull Trick
    • 関数の形式になっている区間最小値を素早く見つける手法 参考1 参考2
    • dp[i] = min{j=0...i-1}(dp[j] + A[i] * B[j])
    • dp[i] = (iの関数) + min{j=0...i-1}((jの関数)*i+(jの関数))
  • MongeDP
    • 別名,Knuth Optimization, Knuth-Yao speedup, 最適二分探索木問題, MongeDP
    • 一番短いMongeDPがいいんじゃないかなと思ってる
    • 「f(i,l) + f(j,k) >= f(i,k) + f(j,l), i <= j, k <= l」を満たす二変数関数はMonge性を持つ