ABC369 D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが開催している、競技プログラミングコンテストのことです。

今回はABC369のD問題を解説していきます。

ABC369　D – Bonus EXP

問題

問題

N匹のモンスターに順に出会います。i匹目のモンスターの強さは \(A_i\) です。

各モンスターについて逃がすか倒すか選ぶことができ、それぞれの行動によって次のように経験値を得ます。

• モンスターを逃がした場合、得られる経験値は0である。
• 強さがXのモンスターを倒したとき、経験値をX得る。ただし、モンスターを倒すのが偶数回目であるとき、さらに追加で経験値をX得る。

N匹から得た経験値の合計としてあり得る最大の値を求める問題です。

制約

• \(1 \leqq N \leqq 2×10^5\)
• \(1 \leqq A_i \leqq 10^9\)

思考の筋道

DPを使って解きましょう。

これをもとに、漸化式を作成します。

• dp[i + 1][0] = max(dp[i][0], dp[i][1] + (A[i] * 2))
  i+1匹目までで偶数匹倒しているパターン。
  i+1匹目を倒す場合と倒さない場合の大きい方を取ります。
  i+1匹目を倒す場合、偶数匹目なので経験値2倍です。
• dp[i + 1][1] = max(dp[i][0] + A[i], dp[i][1])
  i+1匹目までで奇数匹倒しているパターン。
  i+1匹目を倒す場合と倒さない場合の大きい方を取ります。
  i+1匹目を倒す場合、奇数匹目なので経験値は2倍されません。

なお、dp[0][1]は存在しないことに注意しましょう。下のコードでは、dp[0][1]=-infとして、maxに選ばれないようにしています。

動的計画法の問題としては、易しめの問題でしょうか。

コード

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

INFTY = 2 ** 31 - 1
dp = [[-INFTY] * 2 for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    dp[i + 1][0] = max(dp[i][0], dp[i][1] + (A[i] * 2))
    dp[i + 1][1] = max(dp[i][0] + A[i], dp[i][1])

print(max(dp[N][0], dp[N][1]))

リンク