読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

動的計画法更新最適化?

動的計画法で更新式を立ててみると、データ構造などを上手く使うことで計算量が落とせる場合がある。
参考
http://codeforces.com/blog/entry/8219
http://codeforces.com/blog/entry/47932

SegmentTree

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])
みたいに区間和や区間最大最小をもたせることで更新を行う。

問題

http://codeforces.com/blog/entry/22616 のSegment Tree & Dp

Convex Hull Trick

関数の形式になっている区間最小値を素早く見つける手法
http://satanic0258.hatenablog.com/entry/2016/08/16/181331
http://d.hatena.ne.jp/sune2/20140310/1394440369

問題
  • Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry

http://codeforces.com/contest/319/problem/C
英語を読むのが苦じゃないなら、この問題が入門に最適。
問題概要

高さA[i]の木がN本並んでいる。
チェンソーでそれを切る。
高さは単調増加しており、各木には充電料金が決められている。
チェンソーで1cm切るのに充電を全て使い切る。
充電できるのは切り取られている木から。

「dp[i] = min{j=0...i-1}(dp[j] + A[i] * B[j])」となりCHTで解ける
http://codeforces.com/contest/319/submission/25726136
計算の過程でlonglongを超えてしまうので注意。

  • yukicoder No.409 ダイエット

http://yukicoder.me/problems/no/409
「dp[i] = (iの関数) + min{j=0...i-1}((jの関数)*i+(jの関数))」となりCHTで解ける
恐らく、日本語で最も基本的なCHTの入門問題
http://yukicoder.me/submissions/158961

  • HackerRank Week of Code 30 Poles

https://www.hackerrank.com/contests/w30/challenges/poles
これも比較的一般的なCHTの適用例。

  • 以下まとめ

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

分割統治

工事中

クヌース

工事中

きたまさ法

工事中