ブログで書いてほしい内容受付中!!

AtCoder Educational DP Contest / DP まとめコンテストを Pythonで解き進めていく記録

タイトルの通り、Python3 で Educational DP Contest / DP まとめコンテストを今日から解き進めていきます。

サトゥー

いつ終わるかは分かりませんが、解くごとに更新していきます。

初期状態

この記事を書き始めた 2019/06/10 時点での自分の状態を初期状態として記録しておきます。

  • AtCoder 初めて 2 ヶ月くらい(プログラミングほぼ未経験)
  • Python3
  • 茶色(もうすぐ緑)
  • ぶっちゃけ DP って何?って状態

DPの理解の助けになった資料

参考 動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集Qiita 参考 競技プログラミングにおけるDPの考え方サンリオピューロランド

A – Frog 1

\(N\) 個の足場があります。 足場には \(1, 2, …, N\) と番号が振られています。 各 \(i\)  \(( 1 \leq i \leq N )\) について、足場 \(i\) の高さは \(h_i\) です。
最初、足場 \(1\) にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 \(N\) まで辿り着こうとしています。
・足場 \(i\) にいるとき、足場 \(i + 1\) または \(i + 2\) へジャンプする。 このとき、ジャンプ先の足場を \(j\) とすると、コスト \(| h_i − h_j |\) を支払う。
カエルが足場 \(N\) に辿り着くまでに支払うコストの総和の最小値を求めてください。

https://atcoder.jp/contests/dp/tasks/dp_a

dp という配列を用意し、初期値を float("inf") にし、最小値を更新する形にします。 dp[i] が足場 \(i + 1\) までのコストの最小値を表すとし、 dp[0] = 0 から順番に dp の値を更新していきます。

dp[i] と求めるもの

dp[i] : カエルが足場 \(i + 1\) にたどり着くまでに支払うコストの総和の最小値

求めるもの : dp[N - 1] (カエルが足場 \(N\) にたどり着くまでに支払うコストの総和の最小値)

dp[0] がわかっていれば、 dp[1]dp[2] の値を更新することができますね。このようにして、次2つの値を更新しながら進めていき処理します。

提出コード
N = int(input())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]))
	if i < N - 2:
		dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]))
print(dp[N - 1])

B – Frog 2

\(N\) 個の足場があります。 足場には \(1, 2, …, N\) と番号が振られています。 各 \(i\)  \(( 1 \leq i \leq N )\) について、足場 \(i\) の高さは \(h_i\) です。
最初、足場 \(1\) にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 \(N\) まで辿り着こうとしています。
・足場 \(i\) にいるとき、足場 \(i + 1, i + 2, …, i + K\) のどれかへジャンプする。 このとき、ジャンプ先の足場を \(j\) とすると、コスト \(| h_i − h_j |\) を支払う。
カエルが足場 \(N\) に辿り着くまでに支払うコストの総和の最小値を求めてください。

https://atcoder.jp/contests/dp/tasks/dp_b

先程の問題をより一般化した問題です。今度は dp[i] によって更新されうるのは最大で \(K\) 個の dp になりますね。てことは計算量はだいたい \(O(N * K)\) 程度でしょうか。

dp[i] と求めるもの

dp[i] : カエルが足場 \(i + 1\) にたどり着くまでに支払うコストの総和の最小値

求めるもの : dp[N - 1] (カエルが足場 \(N\) にたどり着くまでに支払うコストの総和の最小値)

提出コード

下のコードでは問題文と j の意味合いが少し異なるので注意。 Python3 では TLE でしたが、 PyPy3 では AC (実行時間 435 ms) でした。(Python3 では後日リベンジします)

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

C – Vacation

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。
夏休みは \(N\) 日からなります。 各 \(i\)  \(( 1 \leq i \leq N )\) について、\(i\) 日目には太郎君は次の活動のうちひとつを選んで行います。

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

太郎君は飽き性なので、\(2\) 日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

https://atcoder.jp/contests/dp/tasks/dp_c

意識すべきはその日にどの活動をしたかですから、次のように dp[i][j] を定義してあげると画像のイメージで更新すれば良いことが分かります。

dp[i][j] と求めるもの

dp[i][j] : \(i + 1\) 日目に活動 \(j\) をしたときの、太郎くんが \(i + 1\) 日目までに得る幸福度の総和の最大値

求めるもの : max(dp[N - 1]) (太郎くんが \(N\) 日目までに得る幸福度の総和の最大値)

提出コード

Python3 (595 ms) でも PyPy3 (630 ms) でも AC を確認しました。

N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]
print(dp)
dp[0] = [a[0], b[0], c[0]]
for i in range(N - 1):
	dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1], dp[i][2] + a[i + 1])
	dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1], dp[i][2] + b[i + 1])
	dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1], dp[i][1] + c[i + 1])
print(max(dp[N - 1]))

D – Knapsack 1

\(N\) 個の品物があります。 品物には \(1, 2, …, 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\)

https://atcoder.jp/contests/dp/tasks/dp_d

一人で考えてもよく分からなかったので、色々先人の知恵をお借りしながらコードを書いてみました。

次のように dp[i][j] を定義し、 i → i + 1 での遷移を考えて更新していくことを考えるとうまくいきます。

dp[i][j] と求めるもの

dp[i][j] : \(i\) 番目までの品物から重さが \(j\) を超えないように選んだときの持ち帰る品物の価値の総和の最大値

求めるもの : dp[N][W] ( \(N\) 番目までの品物から重さが \(W\) を超えないように選んだときの持ち帰る品物の価値の総和の最大値)

これを \(i\) を \(0\) から \(N\) まで動かしながら、 dp[i + 1][j] の値を更新していきます。

更新する場合に、 \(i + 1\) 番目の品物( \(w_i\) , \(v_i\) に対応していることに注意)をナップサックに入れるか入れないかで場合を分けて考えます。

\(i + 1\) 番目の品物 ( \(w_i\) , \(v_i\)) を入れる場合

価値 \(v_{i}\) を dp[i][j] に足し合わせます。このとき、重さの合計が \(W\) を超えるとまずいので、品物を入れる条件を j - w[i] >= 0 とし、dp[i][j - w[i]] に足し合わせるようにするという工夫を施します。(これでも題意を満たすように dp を更新することができます)

\(i + 1\) 番目の品物 ( \(w_i\) , \(v_i\)) を入れない場合

このときは dp[i][j] の値をそのまま更新します。

提出コード

次のコードで Python3 では TLE、 PyPy3 では AC (509 ms) でした。

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])

E – Knapsack 2

\(N\) 個の品物があります。 品物には \(1, 2, …, 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^9\)
\(1 \leq w_i \leq W\)
\(1 \leq v_i \leq 10^3\)

https://atcoder.jp/contests/dp/tasks/dp_e

D – Knapsack 1 から制約が少し変わりました。先程と同じコードを PyPy3 で提出してみても MemoryError になってしまいます。

そこで、計算量を削減するために、見方を次のように変えてみます。

dp[i][j] と求めるもの

dp[i][j] : \(i\) 番目までの品物から価値が \(j\) 以上になるように選んだときの持ち帰る品物の重さの総和の最小値

求めるもの : dp[N][j] <= W をみたす j の最大値

ようするに、一度最大の価値を、条件を満たす最小の重みと言い換えることで、実際の計算の量をうまく削減しています。(あるものの最大を考えるとき、同時に別のあるものの最小を考えることになるのでそっちを使おうという発想です)

このように考えることで、 dp[N][j] ( \(N\) 番目までの品物から価値が \(j\) 以上になるように選んだときの持ち帰る品物の重さの総和の最小値)がもとめられるので、これが \(W\) 以下となるようなときの最大の価値 \(j\) を求めれば OK。

dp[i][j] の更新は次のように行います。

\(i + 1\) 番目の品物 ( \(w_i\) , \(v_i\)) を入れる場合

重さ \(w_{i}\) を dp[i][j] に足し合わせます。このとき、最小値を更新するために dp[i][j - v[i]] (価値の合計が \(j – v_i\) での重みの最小に \(w_i\) を足し合わせるようにして求めている)に足し合わせ、品物を入れる条件を j - v[i] >= 0 とするという工夫を施します。(これでも題意を満たすように dp を更新することができます)

\(i + 1\) 番目の品物 ( \(w_i\) , \(v_i\)) を入れない場合

このときは dp[i][j] の値をそのまま更新します。

提出コード

次のコードで Python3 で TLE 、 PyPy3 で AC (1154 ms) でした。

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

V = sum(v)
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)

F – LCS

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

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

https://atcoder.jp/contests/dp/tasks/dp_f

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)