【競技プログラミング】AtCoder Beginner Contest 369_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

dp[i][j] を以下のように定義する

• i: i番目のモンスターまで考慮した場合
• j: 0なら偶数回、1なら奇数回モンスターを倒した場合
• 値: その状態での最大経験値

初期化

1. dpテーブルを十分大きな負の値（ここでは $-10^{18}$）で初期化する。
2. dp = 0 とする。これは、まだモンスターを倒していない初期状態を表す。

DPの遷移

各モンスター i （1からNまで）に対して、以下の2つの選択肢を考慮する

1. モンスターを逃がす場合：

   • dp[i+1][0] = max(dp[i+1][0], dp[i])
   • dp[i+1][1] = max(dp[i+1][1], dp[i][1])

2. モンスターを倒す場合：

   • 偶数回目の場合（追加経験値あり）：
     dp[i+1][0] = max(dp[i+1][0], dp[i][1] + a[i] * 2)
   • 奇数回目の場合：
     dp[i+1][1] = max(dp[i+1][1], dp[i] + a[i])

これらの遷移を全てのモンスターに対して行う。

最終結果の出力

全てのモンスターを考慮した後、dp[N] と dp[N][1] の大きい方が答えとなる。

ACコード1

ac.py

import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    logger.debug("ロガーのセットアップが完了しました。デバッグモード: %s", debug_mode)
    return logger

def io_func():
    n = int(input())
    monster_strengths = list(map(int, input().split()))
    return n, monster_strengths

def solve(n, monster_strengths):
    logger = setup_logger(True)
    
    inf = 10**18
    dp = [[-inf, -inf] for _ in range(n + 1)]
    dp[0][0] = 0
    
    logger.debug(f"初期化: n = {n}, monster_strengths = {monster_strengths}")
    logger.debug(f"DPテーブルの初期状態: dp = {dp}")

    for i in range(n):
        dp[i+1][0] = max(dp[i][0], dp[i][1] + monster_strengths[i] * 2)
        dp[i+1][1] = max(dp[i][1], dp[i][0] + monster_strengths[i])
        logger.debug(f"ステップ {i+1}: dp[{i+1}] = {dp[i+1]}")

    max_experience = max(dp[-1])
    logger.debug(f"最終結果: max_experience = {max_experience}")
    return max_experience

def main():
    n, monster_strengths = io_func()
    result = solve(n, monster_strengths)
    print(result)

if __name__ == "__main__":
    main()