Educational DP Contest C - Vacation【Pythonの解答例】

DPの勉強としてEducational DP Contestに取り組んでいます。
今回は3回目　C - VacationをPythonで解いてみます。

EDPC C - Vacation

C - Vacation

問題文

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。
夏休みはN日からなります。 各i(1≤i≤N) について、i日目には太郎君は次の活動のうちひとつを選んで行います。
・A: 海で泳ぐ。 幸福度aiを得る。
・B: 山で虫取りをする。 幸福度biを得る。
・C: 家で宿題をする。 幸福度ciを得る。太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

制約

・入力はすべて整数である。
・1≤N≤10^5
・1≤ai,bi,ci≤10^4

解答例

n = int(input().strip())
a = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    a.append(array)

dp = [[0 for j in range(100010)]for i in range(3)] # ※1　夏休みの日数より多く、各要素が0の2次元配列を準備
# ※2　dp = [[0] * 100010] * 3は不可

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp1 = dp[j][i] + a[i][k]# ※3　i-1日目にjの行動、i日目にkの行動を行う場合の幸福度
            if dp1 > dp[k][i+1]: # ※4　dp[k][i+1]はi日目にkを行ったときの得られる幸福度
                dp[k][i+1] = dp1
                
dpmax = 0 # ※5　求める最大の幸福度
for i in range(3):
    if dp[i][n] > dpmax:
        dpmax = dp[i][n]

print(dpmax)

解説

この問題では太郎君が夏休みの間、毎日A,B,Cの3通りのなかから1つの行動をとることができ、その行動により幸福度を得ます。
夏休みが終わるときの最大の幸福度を求める問題です。
注意として2日続けて同じ行動はとれないという制約があります。

上記のプログラムは配るDPの考え方で進めております。
まず前提として行動A→0,B→1,C→2のようにプログラム上は行動を数字で表しています。
※1のように用意する配列dpは2次元配列としました。
dp[a][b]は、b-1日目に行動aを行った場合の幸福度になります。
※2に記載しましたが、dp = [[0] * 100010] * 3のように2次元配列を作成すると、例えばdp[1][1]にある値に代入するとdp[0][1]やdp[2][1]まで同じ値が代入されました。
これでは意図した結果が得られないため、※2の2次元配列の作成の仕方はやめたほうがいいようです。
※3ではi-1日目に行動j、i日目に行動kの行動を行う場合の幸福度dp1を計算しています。
このときjとkは行動を表す数字で、jとkが等しいときi-1日目とi日目に同じ行動を行ったことになります。
したがって※3に至るまえにif文でjとkが等しい場合は※3以降の計算を行わないようにしています。
※4でdp[k][i+1]とdp1を比較し、dp1が大きければ代入します。
n日目までこの計算を繰り返してきます。
n日目に行う行動はA,B,Cの3パターンありますので※5以降でn日目の最大幸福度をdpmaxに代入し、最後にdpmaxを出力することでACでした。

今回は2次元配列を用いたDPでした。
初心者ゆえに2次元配列を思い通りに使いこなせず苦労しましたが、DPの考え方自体はこれまでの問題と大きく変わっていないと感じました。
ACに至るまで大変ですが、1問1問新たな学びがありますので今後もEDPCを続けていきます。

これまでのEDPCの記事はこちら
https://ebisuke33.hatenablog.com/entry/2020/11/26/225503ebisuke33.hatenablog.com
https://ebisuke33.hatenablog.com/entry/2020/11/28/134117ebisuke33.hatenablog.com