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

hamayanhamayan's blog

競技プログラミングにおける動的計画法更新最適化まとめ(CHT, MongeDP, AlianDP, インラインDP, きたまさ法)

動的計画法更新最適化?

  • セグメント木や累積和
    • 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性を持つ
  • インラインDP
    • skyさんによる素晴らしい記事
    • DPで2次元配列となるが、遷移が単純なので、普通なら空間O(NM),計算量O(NM)かかる所を、セグメントツリー全体をDPの配列として更新していくことで、空間O(N),計算量O(MlogN)で済むテク
    • 名前が無いのでここに追加するのに困っていたが、インラインDPという名前はとても良いと思う(なんとなくかっこいいので)

問題

CFにあったまとめ

セグメントツリーや累積和

行列累乗

分割統治

CHT

http://codeforces.com/blog/entry/8219
http://arc070.contest.atcoder.jp/tasks/arc070_c
http://pekempey.hatenablog.com/archive/category/Convex%20Hull%20Trick

MongeDP

インラインDP

(あんまり関係ないけど)遷移が限られる関係で最適化できる動的計画法問題