動的計画法はアルゴリズムコンテストで頻出な手法であり、簡単な実装から短時間コンテストと相性がよくかなり出題される。しかし、難易度が高い問題は漸化式を立てるだけでは計算量がオーバーしてしまう。ここで、計算量を落として加速するのだが、その方法を纏める。
ここでは、データ構造を用いない加速法をまとめる。
ここでは、データ構造を用いない加速法をまとめる。
優先順序を持ったペアのDP
優先順序を持ったものは、DPテーブルの値自体にそれを持つことによって、往々一つのオーダーを落とせる。例を見たほうが分かりやすい。
500-yen Saving (AOJICPC-500) AOJ1603
この問題での考察を詰めると
dp[i][j][k]:= i個目の商品まで見て、500円玉をj個保持して、小銭がkのときのかかるコストの最大値
と漸化式が立つ。
しかし、O(n^3 * 500)となり、これではAOJの8.00sの制約に間に合わない(ICPC本番では時間実質ほぼ無制限？なのでこれでも通るけど)
ここで落とせそうなものを考察すると、商品を見る、500円玉の個数を見る、小銭を見るの3つによってなり、500円玉の数が落ちると嬉しいことがわかる。
この問題では、500円玉の数の最大化をして、その中でのコストの最小化をする。つまり、同じ小銭の額ならば500円玉がより多い方、その中で一番コストが低い方が答えとなる。（これを最善解と呼ぼう）
このことを利用すると、DPテーブルの更新の際には、同じ小銭の額でも、最善解をもとに次の更新を行い、最終的な答えを計算する。ということは、小銭の額ごとに最善解のみを持てば、遷移を計算できる
dp[i][j][k]:= i個目の商品まで見て、500円玉をj個保持して、小銭がkのときのかかるコストの最大値
と漸化式が立つ。
しかし、O(n^3 * 500)となり、これではAOJの8.00sの制約に間に合わない(ICPC本番では時間実質ほぼ無制限？なのでこれでも通るけど)
ここで落とせそうなものを考察すると、商品を見る、500円玉の個数を見る、小銭を見るの3つによってなり、500円玉の数が落ちると嬉しいことがわかる。
この問題では、500円玉の数の最大化をして、その中でのコストの最小化をする。つまり、同じ小銭の額ならば500円玉がより多い方、その中で一番コストが低い方が答えとなる。（これを最善解と呼ぼう）
このことを利用すると、DPテーブルの更新の際には、同じ小銭の額でも、最善解をもとに次の更新を行い、最終的な答えを計算する。ということは、小銭の額ごとに最善解のみを持てば、遷移を計算できる
具体的な実装では、{pair<int, int>をdpの型として持ち、それぞれ、<500円硬貨数, かかるお土産代>とする。
dp[i][j] := iこのアイテムまで見て、j円の小銭を持った時の最善解}
とすればよい。
dp[i][j] := iこのアイテムまで見て、j円の小銭を持った時の最善解}
とすればよい。
N項間漸化式など、漸化式に帰着できるもの
N元連立漸化式やN項間漸化式に帰着できるのならば、行列累乗のテクニックで爆速で計算できる。
EDPC R
まずは
dp[i][j] := iターン目にjの位置にいるときの場合の数
とすると、
dp[i + 1][to] += dp[i][j] ただし、toはjの位置から行ける頂点
と遷移できるようになる。ここで、漸化式への帰着ができる重要ポイントとして、
すべての遷移に何回目の移動かは関係なく、かつ遷移はすべては平等な操作である(今回の場合は、どの辺を移動してもすべて距離1)
これらからわかることとしては、
何回目の遷移は実は無関係で、ひたすらN項間の連立漸化式にしたがって更新される。
ということ。これは漸化式に対応する行列を繰り返し二乗法を用いることで高速に計算できる。
dp[i][j] := iターン目にjの位置にいるときの場合の数
とすると、
dp[i + 1][to] += dp[i][j] ただし、toはjの位置から行ける頂点
と遷移できるようになる。ここで、漸化式への帰着ができる重要ポイントとして、
すべての遷移に何回目の移動かは関係なく、かつ遷移はすべては平等な操作である(今回の場合は、どの辺を移動してもすべて距離1)
これらからわかることとしては、
何回目の遷移は実は無関係で、ひたすらN項間の連立漸化式にしたがって更新される。
ということ。これは漸化式に対応する行列を繰り返し二乗法を用いることで高速に計算できる。
