python~動的計画法~

こんにちは、Keymaleです。今回は動的計画法です。ArcoderのDPコンテストをやっていきます。

A問題

問題文

NN 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 ii (1≤i≤N) について、足場 i の高さは hi です。

最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

  • 足場 ii にいるとき、足場 i+1 または i+2 へジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。

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

制約

  • 入力はすべて整数である。
  • 2≤N≤105
  • 1≤hi≤104

入力

入力は以下の形式で標準入力から与えられる。

N
h1 h2 …… hN

出力

カエルが支払うコストの総和の最小値を出力せよ。

解答コード

この問題に対するコードは以下のようになります。

import sys
input = sys.stdin.readline

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

dp = [[10e10] for _ in range(N)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,N):
  dp[i] = min(abs(h[i] - h[i - 1]) + dp[i - 1], abs(h[i] - h[i - 2]) + dp[i - 2])
print(dp[N-1])

次の問題はこちらです。

B問題

問題文

N 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hi です。

最初、足場 1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

  • 足場 i にいるとき、足場 i+1,i+2,…,i+K のどれかへジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。

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

制約

  • 入力はすべて整数である。
  • 2≤N≤105
  • 1≤K≤100
  • 1≤hi≤104

入力

入力は以下の形式で標準入力から与えられる。

N K
h1 h2 …… hN

出力

カエルが支払うコストの総和の最小値を出力せよ。

解答コード

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0 for _ in range(N)])
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,N):
  dp[i] = abs(h[i] - h[i-1]) + dp[i-1]
  k = min(i,K)
  dp[i] = np.min(np.abs(h[i] - h[i-k:i+1]) + dp[i-k:i+1])
print(dp[N-1])

こちらは二重for文だとpythonでは間に合わなかったので、numpyで処理して間に合わせてます。

C問題

問題文

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

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

  • A: 海で泳ぐ。 幸福度 ai を得る。
  • B: 山で虫取りをする。 幸福度 biを得る。
  • C: 家で宿題をする。 幸福度 ci を得る。

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

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

制約

  • 入力はすべて整数である。
  • 1≤N≤105
  • 1≤ai,bi,ci≤104

入力

入力は以下の形式で標準入力から与えられる。

N
a1 b1 c1
a2 b2 c2
::
aN bN cN

出力

太郎君が得る幸福度の総和の最大値を出力せよ。

解答コード

import numpy as np
import sys
input = sys.stdin.readline

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

D問題

これはかの有名なナップザック問題です。

問題文

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 ii (1≤i≤N) について、品物 i の重さは wi で、価値は viです。

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

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

制約

  • 入力はすべて整数である。
  • 1≤N≤100
  • 1≤W≤105
  • 1≤wi≤W
  • 1≤vi≤109

入力

入力は以下の形式で標準入力から与えられる。

N W
w1 v1
w2 v2
::
wN vN

出力

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。

解答コード

import numpy as np
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = np.array([[0] * (W + 1) for _ in range(N + 1)])
for i in range(N):
  w, v = map(int, input().split())
  dp[i + 1][0:w] = dp[i][0:w]
  dp[i + 1][w:] = np.maximum(dp[i][w:], dp[i][0:W+1-w] + v)
#  for j in range(W+1):
#    if w > j:
#      dp[i + 1][j] = dp[i][j]
#    else:
#      dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)
print(dp[N][W])

これもpythonだと間に合わないので、numpy配列で高速化してます。時間制限がない場合のfor文での記述もコメントアウトで記載してます。