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

（この記事の続き↓）
politeness.hatenadiary.com

前回の記事に引き続き、以下のコンテストで出題された問題を使ってDPに慣れていこう。

atcoder.jp

D . Knapsack 1

問題 $N$ 個の品物があります。品物には $1,2,\ldots ,N$ と番号が振られています。各 $i\, (1\leq i \leq N)$ について、品物 $i$ の重さは $w_i$ で、価値は $v_i$ です。

太郎君は、 $N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量は $W$ であり、持ち帰る品物の重さの総和は $W$ 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

入力はすべて整数である。
$1\leq N \leq 100$
$1\leq W \leq 10^5$
$1 \leq w_i \leq W$
$1 \leq v_i \leq 10^9$

この問題も各品物に対し選ぶ、選ばないの2択が存在し、全探索する場合計算量は（ざっくり） $\mathcal{O}(2^N)$ になる。いかにもDPを使えそうな設定だ。

例えば、以下のようなDP配列を考えるとする。

dp[ i ] = $i$ 番目までの品物から重さが $W$ を超えないように選んだときの、価値の総和の最大値 $\qquad (i=0,1,\ldots , N)$

少し考えてみればわかるが、このDP配列はどの品物を選択したかの情報を持たないため、うまくdp[ i+1 ]の更新ができない。こういった場合は、DP配列の添字を増やすのが定石であった。

DP配列を以下のように改良するとうまく動作する。

dp[ i ][w] = $i$ 番目までの品物から重さが $w$ を超えないように選んだときの、価値の総和の最大値 $\qquad (i=0,1,\ldots , N\, , \, w=0,1,\ldots , W)$

なお、dp[0][ i ]=0 , dp[ i ][0]=0 であるとする。

このDP配列はどのように更新するべきか例を見ながら考えよう。

例えば、 $N=4,W=5$ であり4つの品物が $(w,v)=(4,2),(5,2),(2,1),(8,3)$ で与えられる時、上の定義にのっとったDP配列は以下のようになる。

i \ w	1	2	3	4	5
0	0	0	0	0	0
1	0	4	4	4	4
2	0	5	5	9	9
3	2	5	7	9	11
4	2	5	8	10	13

例えばこのdp[3][5]はどのように更新したかであるが、これは3つ目の品物を選択したかどうかで場合わけして考えれば良い。

品物3を使わないならば、詰め方は品物2まで使った最適の詰め方dp[2][5] = 9を採用すれば良い。一方品物3を使うとすると、「重さ制限として品物2までで最適に詰めたナップザックに品物3を追加して容量5に合わせる」のが価値を最大にする方法で、すなわちdp[2][4]+v[3] = 9+2 = 11となる。

2通りのうち価値が多くなるのは品物3を使う時で、dp[3][5]の値は11に更新されるということだ。同様にしてdp[ i ][ j ]は以下の式に基づいて更新することができるだろう。

$\begin{align*} \mathrm{dp}[i][w]=\max \left\{\mathrm{dp}[i-1][w]\, , \, \mathrm{dp}[i-1][w-w_i]+v_i\right\} \end{align*}$

更新の仕方がわかったらこっちのもので、コードは以下のようにかける。

N,W=map(int,input().split())

#vもwもdpも全て1-indexedみたいにした。わかりやすいので。
v=[0]*(N+1)
w=[0]*(N+1)
for i in range(1,N+1):
    w_i,v_i=map(int,input().split())
    w[i]=w_i
    v[i]=v_i


dp=[[0]*(W+1) for i in range(N+1)] #初期化もこの段階で済んでいる

for i in range(1,N+1):
    for j in range(1,W+1):
        if dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]
        if j >= w[i]:
            if dp[i][j] < dp[i-1][j-w[i]]+v[i]:
                dp[i][j] = dp[i-1][j-w[i]]+v[i]

print(dp[N][W])

DPを実装する上でindexが難しさの6割を担っているように感じる。

E . Knapsack 2

問題文はD.Knapsack 1と同じで、 $W$ に関する制約のみ「 $1\leq W \leq 10^9$ 」に変更されたのがこの問題である（なので問題文は割愛）。

先ほどの $N\times W$ のサイズのDP配列を作る解き方だと、計算量は $\mathcal{O}(NW)$ となり、 $W$ が大きな値をとるときによくない感じになってしまう。

この時は発想の転換が必要となる。以下のようにDP配列を構成する。

dp[ i ][w] = $i$ 番目までの品物から価値がちょうど $v$ となるように選んだときの、重さの総和の最小値 $\qquad (i=0,1,\ldots , N\, , \, v=0,1,\ldots , V\quad(V:=\sum_{i=1}^N v_i))$

このようにDP配列を構成すると計算量は $\mathcal{O}(NV)$ となり、（ $N,V$ がそんなに大きくならない今問題では）計算量を抑えることに成功している。

このDPからどのように答えを求められるかであるが、dp[N][v]の値が $W$ 以下となるような $v$ の最大値が求める値となっている。「できるだけ価値が大きいやつ選びたいけど、 $W$ 超えるやつは選べないし〜」とギャルのように思考すると理解できるかと思う。

更新の仕方はD.Knapsack 1と同様に以下のようになる。

$\begin{align*} \mathrm{dp}[i][v]=\min \left\{\mathrm{dp}[i-1][v]\, , \, \mathrm{dp}[i-1][v-v_i]+w_i\right\} \end{align*}$

また、最小値を更新していくDPなので初期条件はdp[0][0]=0、その他のマスはdp[ i ][ j ]= $\infty$ と初期化しておくと良さそうだ。コードは以下の通り。

#入力受け取り
N,W=map(int,input().split())

v=[0]*(N+1)
w=[0] *(N+1)
for i in range(1,N+1):
    w_i,v_i=map(int,input().split())
    w[i]=w_i
    v[i]=v_i
sum_v=sum(v)+1

#DP配列の初期化
dp=[[float('inf')]*(sum_v) for i in range(N+1)] 
dp[0][0]=0
#これでDP配列の1行目は完了。2行目以降を更新していく。
#DP配列の値float('inf')は実現不可能を表すと解釈する。

for i in range(1,N+1):
    for j in range(sum_v):
        if dp[i][j] > dp[i-1][j]:
            dp[i][j] = dp[i-1][j]
        if j >= v[i]:
            if dp[i][j] > dp[i-1][j-v[i]]+w[i]:
                dp[i][j] = dp[i-1][j-v[i]]+w[i]

ans=0
for i in range(1,sum_v):
    if dp[N][i] <= W:
        ans = i
print(ans)

(※課題)
初め、dp[ i ][ v ]に「価値が $v$ 以上となるような選び方の中での重さの総和の最小値」を格納しようとしてコードを書いていたが失敗した。

どうすりゃいいか考えときます。

F . LCS

問題文字列 $s$ および $t$ が与えられます。 $s$ の部分列かつ $t$ の部分列であるような文字列のうち、最長のものをひとつ求めてください。

なお文字列 $x$ の部分列とは、 $x$ から $0$ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。

制約

$s$ および $t$ は英小文字からなる文字列である。
$1\leq |s|,|t| \leq 3000$

この問題は「DPを使ってみよう」というテーマで出題された問題であるからDPを利用するという発想になるが、初見ではDPを使おうと思いたつことが難所のように感じる。

$s,t$ の各文字を部分列に含むか含まないかの"全探索感"、そして $s,t$ の最初の何文字かを取ってくるとそれが元の問題の部分問題となることを嗅ぎつけて、なんとかDPを使うという発想に持っていきたいものだ(ちなみに部分列の長さの最大値を求める問題がLCSというDPの典型問題らしい)。

この問題は部分列のうち最長のものを求めよという問題であるが、DPを利用する時は「最長部分列の長さを求めつつDP配列を更新し」、「DP配列から部分列を復元する」という2つのフェーズに分けると良い。

DP配列は順当に以下のようなものを考えれば良い。

dp[ i ][ j ] = $s$ の $i$ 文字目までと $t$ の $j$ 文字目まででの最長部分列の長さ $\qquad (i=0,1,\ldots , |s|\, , \, j=0,1,\ldots , |t|)$

更新の仕方もシンプルで s[ i-1 ] == t[ j-1 ] が成り立つ時は、dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ i-1 ][ j-1 ] + 1 )と更新すれば良いし、それ以外の時はsのi文字目、tのj文字目を考慮しても部分列の長さは変わらず、dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ i ][ j-1 ] , dp[ i-1 ][ j ] )と更新すれば良い。

問題は復元であるが、考え方としてはDP配列のdp[n][m]から出発して順に「どのノードから更新されて来たのか、その元となる部分を辿って行く」ことになる。ここではDP配列を見て、今いるノード $(i,j)$ がどのノードから更新されて来たのかを特定する方法を用いる。

DP配列の要素の値が減らない様に遷移できる時はそう遷移して、できない時はs[ i ] == t[ j ]が成り立っていることを表しているので、s[ i ]を記録し、ノード $(i-1,j-1)$ に遷移すれば良い。

コードは以下の通りになる。

s=input()
t=input()

S=len(s)+1
T=len(t)+1

dp=[[0]*T for i in range(S)]

for i in range(1,S):
    for j in range(1,T):
        if s[i-1]==t[j-1]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
        dp[i][j] = max(dp[i][j],dp[i-1][j]) 
        dp[i][j] = max(dp[i][j],dp[i][j-1])
    
res=""
i=len(s)
j=len(t)
while i>0 and j>0:
    #(i-1,j)->(i,j)に更新した場合(1)
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    #(i,j-1)->(i,j)に更新した場合(2)
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    #s[i]=t[j]であり、(i-1,j-1)->(i,j)に更新した場合(3)
    else:
        res = s[i-1] + res
        i -= 1
        j -= 1
print(res)

実は初めこのコードを書くのに失敗した。間違えた点は復元のフェーズで、(3)→(1)→(2)の順番でif文を書いてしまったところだ。

dp[ i ][ j ] == dp[ i-1 ][ j-1 ] + 1が成り立っているからと言って、s[ i ] == t[ j ]が成り立っているとは限らないことが原因である。

ムズイなあ！

G . Longest Path

問題 $N$ 頂点 $M$ 辺の有向グラフ $G$ があります。頂点には $1,2,\ldots ,N$ と番号が振られています。各 $i\,(1\leq i \leq M)$ について、 $i$ 番目の有向辺は頂点 $x_i$ から $y_i$ へ張られています。 $G$ は有向閉路を含みません。

$G$ の有向パスのうち、最長のものの長さを求めてください。ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。

制約

入力は全て整数である。
$2\leq N \leq 10^5$
$1\leq M \leq 10^5$
$1\leq x_i,y_i \leq N$
ペア $(x_i,y_i)$ は全て相異なる。
$G$ は有効閉路を含まない。

「おいおいこんなもんBFSで1発やがな！人生は冒険や！」と自分の中のゆたぼんが暴れ出したところで、求められているのが最長路であることに気づいた。

BFSはキューのデータ構造を用いて始点から近いものから最短路をひとつずつ確定させていく方法であったが、最長路を調べる際は、どのようにキューを更新していけば良いのかわからない（どうやら、トポロジカルソートを行った後にBFSを行うことで解けるようだが僕にはまだ難しい...）。

BFSを使わないとすると、コンテストの名前通りDPを使って解くしかない。しかし、この問題では今までの問題とは違い、DP配列の更新順序が不明である。

このような場合は、メモ化再帰を利用すれば良い。復習になるが、メモ化再帰とは関数を再帰的に定義するが、何度も同じ計算を繰り返すと計算量が膨大になってしまうので、1度計算した結果をDP配列にメモしときましょう、というやり方である。

さて、ここでDP配列を以下のように定義する。

dp[ v ] = ノード $v$ を始点としたときの、 $G$ の有効パスの長さの最大値 $\qquad (v=0,1,\ldots , N-1)$

この関数内では、ノード $v$ から直接行くことのできる各ノード $u$ に対して

$\begin{align*} \mathrm{dp}[v]=\max \left\{\mathrm{dp}[v]\, , \, \mathrm{dp}[u]+1\right\} \end{align*}$

として、DP配列を更新してあげればよい。それを踏まえたコードが以下の通りとなる。

import sys
sys.setrecursionlimit(10**5+10) 
#許容する再起処理の回数を変更。これをつけなければACにならなかった...。


N,M=map(int,input().split())

G=[[] for i in range(N)] #グラフを隣接リストで表現
for j in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)

dp=[-1]*N

def longest_path(v): #vを始点とした時の最長パスの長さ
    if dp[v] != -1: #更新済みの場合
        return dp[v]
    
    #更新されていなかった場合
    tmp_max = 0
    for u in G[v]:
        tmp_max = max(tmp_max,longest_path(u)+1)
    dp[v] = tmp_max #きちんとメモする
    
    return dp[v]

ans=0
for i in range(N):
    ans = max(ans,longest_path(i))

print(ans)

おそらく再起処理の回数が規定の条件を上回っているため、sys.setrecursionlimit(10**5+10)という行を付け足す必要があった。Pythonの遅さが出ましたねぇ。

このような更新の仕方をするDPも存在することは頭に入れておく必要がある。

この記事も長くなったので、ここで一旦終わりとする。

続き？知らねえなあ、、、

（続き↓）

coming soon...

naruの日記

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

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

D . Knapsack 1

E . Knapsack 2

F . LCS

G . Longest Path