動的計画法に只管打座(1)

動的計画法というものがあるという噂を聞いた。

あまり詳しくはない*1が、簡単な漢字のみで構成されているのでまあ余裕であろう。

この記事を書く上で以下の記事を大いに参考にした。Viva インターネッツ。

qiita.com

動的計画法とは

ja.wikipedia.org

Wikipediaによると動的計画法とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法である。

具体的には以下の2条件を満たすようなアルゴリズムの総称らしい。

1.帰納的な関係の利用

　より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解
　くのに使用する。

2.計算結果の記録

　小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的
　な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見
　出しにして管理される

ほう...。だいぶ柔らかい定義である。

動的計画法を問題に適用するためには、問題が以下の2条件を満たしている必要がある。

1.部分構造最適性・最適性原理

　部分構造最適性、最適性原理とは、部分問題も同じ最適化問題が成立している、そ
　して部分問題間が独立しているという2条件のことを指す。
　例を挙げると、最短路問題における「最短路の部分経路もまた最短路になってい
　る」(日本語がむずかしい)という性質は部分構造最適性を満たしている。

2.部分問題重複性

　部分問題重複性とは、同一の部分問題が繰り返し出現することである。重複する部
　分問題の計算結果を記録し再利用する事により計算量を削減するというのが動的計
　画法の骨子であった。

上には適用できる条件を挙げたが、実際には動的計画法を利用できる問題パターンを具体的に知っておくことが大事だと思う。

以下では動的計画法を利用できる典型問題とその解法を扱いながら、動的計画法との付き合い方を探っていこう。

動的計画法を用いる諸問題

※もうアニメーションは使いません。我ながらうざいので。

徐々に問題の難易度をあげて動的計画法(以下DP)に慣れていこう。

ここではAtCoderの以下のコンテストで出題された中から問題をピックしていく。

atcoder.jp

A.Frog 1

問題 $N$ 個の足場があります。足場には $1,2,\ldots,N$ と番号が振られています。各 $i\,(1\leq i \leq N)$ について、足場 $i$ の高さは $h_i$ です。
最初、足場 $1$ にカエルがいます。カエルは次の行動を何回か繰り返し、足場 $N$ まで辿り着こうとしています。

足場 $i$ にいるとき、足場 $i$ または $i+2$ へジャンプする。このとき、ジャンプ先の足場を $j$ とすると、コスト $|h_i-h_j|$ を支払う。

カエルが足場 $N$ に辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

入力はすべて整数である。
$2\leq N \leq 10^5$
$1 \leq h_i \leq 10^4$

DPを使うときの基本的な順序は以下の通りである。

DP 配列全体を「DP の種類に応じた初期値」で初期化

初期条件を入力

ループを回す

テーブルから解を得て出力

僕はマニュアル大好き人間なので、問題をこのフォーマットに落とすことを考えながら問題を解いていこう。

まず、今回の問題は最小値を求める問題であるので、初期化する値はfloat('inf')とでもしておけば良いだろう。

次にループを回し、DP配列を更新していく方法であるが、ここで二通りの考え方を紹介する。

1.貰うDP

ノード $i$ (ここでは足場 $i+1$ に足場 $1$ からたどり着く最小コストを格納する)に遷移してくるのは、ノード $i-2$ から足場を飛ばして飛んできた時と、ノード $i-1$ から足場を飛ばさず飛んできた時の2パターンであるので、2パターンのうち、よりコストが小さい方を採用してノード $i$ にその値を格納する。なおこの考え方ではノード $i-2,i-1$ への最小コストが確定していることは前提とする。

この更新の仕方を採用したDPを「貰うDP」とここでは呼び、以下のコードで実装される。

N=int(input()) #足場の個数

h=list(map(int,input().split())) #足場の高さデータ

#ステップ1
dp=[float('inf') for i in range(N)]

#ステップ2
dp[0]=0

#ステップ3
for i in range(1,N):
    if dp[i] > dp[i-1]+abs(h[i]-h[i-1]):
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
    
    if i != 1:  #ノード1(足場2)のみ2個前のノードからの遷移がないので除外
        if dp[i] > dp[i-2]+abs(h[i]-h[i-2]):
            dp[i] = dp[i-2]+abs(h[i]-h[i-2])
      
#ステップ4
print(dp[N-1])

2.配るDP

ノード $i$ から他のノードへ遷移する状況を考えると、ノード $i+1$ に足場を飛ばさず遷移する時と、ノード $i+2$ に足場を飛ばして遷移する時の2パターンがある。ノード $i+1,i+2$ でその遷移によってコストが減少するならば、そのコストを採用しノードに格納する。なおこの考え方ではノード $i$ の最小コストが確定していることを前提としている。

この更新の仕方を採用したDPを「配るDP」とここでは呼び、以下のコードで実装される。

N=int(input())

h=list(map(int,input().split()))

#ステップ1
dp=[float('inf') for i in range(N)]

#ステップ2
dp[0]=0

#ステップ3
for i in range(N-1):
    if dp[i+1] > dp[i]+abs(h[i+1]-h[i]):
        dp[i+1] = dp[i]+abs(h[i+1]-h[i])

    if i!= N-2: #ノードN-2(足場N-1)のみ2個先のノードへの遷移がないので除外
        if dp[i+2] > dp[i]+abs(h[i+2]-h[i]):
            dp[i+2] = dp[i]+abs(h[i+2]-h[i])
      
#ステップ4
print(dp[N-1])

上に2つの考え方とそれに基づく解法を示したが、どちらの考え方においても

if dp[to] > dp[from] + (遷移のコスト):
    dp[to] = dp[from] + (遷移のコスト)

という更新を繰り返しているにすぎない。この更新のことを「緩和」というらしい。

この緩和において重要なのは、ノード from からノード to への緩和を行うときは、dp[from] の値の更新は完了していることである。

これを満たしている限り、緩和の順番は「貰うDP」でも「配るDP」でもなんでも構わない。この条件を満たすというのは、dp[ i ]にはi番目までの探索過程がまとめられていることを表していて、これがはじめに述べたDPの適応条件である部分構造最適性にあたる性質である。

とにかくDPは「再帰的に全探索を行っている」というイメージを持つことが重要らしい。

C.Vacation

問題明日から太郎君の夏休みが始まります。太郎君は夏休みの計画を立てることにしました。

夏休みは $N$ 日からなります。各 $i\,(1\leq i \leq N)$ について、 $i$ 日目には太郎君は次の活動のうちひとつを選んで行います。

　　A: 海で泳ぐ。幸福度 $a_i$ を得る。
　　B: 山で虫取りをする。幸福度 $b_i$ を得る。
　　C: 家で宿題をする。幸福度 $c_i$ を得る。

太郎君は飽き性なので、 $2$ 日以上連続で同じ活動を行うことはできません。

太郎君が得る幸福度の総和の最大値を求めてください。

制約

入力はすべて整数である。
$1\leq N \leq 10^5$
$1 \leq a_i,b_i,c_i \leq 10^4$

この問題は愚直に全探索すると計算量が（ざっくり) $\mathcal{O}(3^n)$ くらいになる。2日以上前の選択はその日の選択に影響しないというルールが存在するので、それを利用して解こうと考えるとDPの利用に思い至るだろう。

ポイントとしては、前日の選択がその日の選択に影響を与える点である。今まで通りにDP配列を作りdp[ i ]を $i+1$ 日目までの最大幸福度としていくやり方は、DP配列が前日の選択の情報を持たないのでうまく動作しない。

DP法の漸化式的側面に読者の皆々様は気付きつつあるだろうが、漸化式を解く場合を考えると、こういう状況では前日の選択により場合分けするのが鉄板である。

DPにおける場合分けの実現方法は、DP配列を2次元配列に拡張することである。以下のようにDP配列を作成する。

dp[ i ][ j ]=夏休み $i+1$ 日目にアクティビティ $j\,(A:j=0,B:j=1,C:j=2)$ をした場合の $i+1$ 日目までに得られる幸福度の最大値 $\qquad (i=0,1,\ldots N-1)$

このようにして、ループ毎に

dp[ i ][ 0 ] から dp[ i + 1 ][ 1 ] への遷移
dp[ i ][ 0 ] から dp[ i + 1 ][ 2 ] への遷移
dp[ i ][ 1 ] から dp[ i + 1 ][ 0 ] への遷移
dp[ i ][ 1 ] から dp[ i + 1 ][ 2 ] への遷移
dp[ i ][ 2 ] から dp[ i + 1 ][ 0 ] への遷移
dp[ i ][ 2 ] から dp[ i + 1 ][ 1 ] への遷移

の6通りの遷移を考慮しDP配列を更新していくことで、 $N$ 日目の幸福度の最大値が求まるっていう寸法さ。

コードは以下の通り。

N=int(input())

A=[[0]*3 for i in range(N+1)]
for i in range(N):
    a=list(map(int,input().split()))
    A[i]=a

#ステップ1
dp=[[-float('inf')] * 3 for i in range(N+1)]
#A,dp共にN+1行作っておくことでループを回すときにN日目だけ分けて考える必要がなくなる。
#今回は最大値問題なので-infで初期化（0でも構わない）。

#ステップ2
dp[0]=A[0] #初日にAを実行する日の幸福度は確定している。以下同様。

#ステップ3
for i in range(N):
    for j in range(3): #i+1日目に行うアクティビティ
        for k in range(3): #i+2日目に行うアクティビティ
            if j != k: #2日連続同じアクティビティは禁止
                if dp[i+1][k] < dp[i][j] + A[i+1][k]:
                    dp[i+1][k] = dp[i][j] + A[i+1][k]
        
#ステップ4
ans=max(dp[N-1])
print(ans)

この問題のように、DPを設計するときに「情報が足りないから添字を増やす」というのはよく行うステップのようだ。

ちょっとDP法に慣れてきた。記事が長くなるのでここらで一回休憩を挟みます。
各自水分補給等するように。

(続き↓)
politeness.hatenadiary.com

*1:詳しくはないと言いつつも、勉強したことがないわけではない。いや、あの程度が勉強にはいるかどうかは微妙なラインなのでとりあえず触ったことがあると言っておこう。そんな言い方をすると教わった先生に申し訳ない気もするが自分の認識としてはやはり身についていないわけで、だからこそ、ここにこうやってまとめているわけで、、、。先生の責任じゃない。気に負う必要ないよ先生！何が言いたいかというと、1から内容をまとめるつもりはないので、動的計画法の基本的なイメージ(適切な配列を作り、その要素を徐々に更新していく)を持っていることはこの記事を読む上で前提とする。

naruの日記

いい記事を書きます。あと、日記ではないです。

動的計画法に只管打座(1)

動的計画法とは

動的計画法を用いる諸問題

A.Frog 1

C.Vacation