概要

一列に並んだ \(N\) 個の花壇から、「隣り合う花壇を同時に選ばない」という条件のもとで、選んだ花壇の美しさの合計を最大化する問題です。

考察

まず、素朴な方法として「すべての組み合わせを試す」という手法が考えられます。しかし、各花壇について「植える・植えない」の 2 択があるため、組み合わせの総数は \(2^N\) 通りとなります。制約の \(N \leq 2 \times 10^5\) では、この方法は計算時間がかかりすぎて間に合いません（TLE）。

この問題のポイントは、「\(i\) 番目の花壇に花を植えるかどうか決める際、それより前の最適な選び方の情報があれば十分である」という点です。

\(i\) 番目の花壇に注目したとき、選択肢は以下の 2 つに限られます： 1. \(i\) 番目に花を植える場合： 隣り合う花壇には植えられないため、\(i-1\) 番目には植えることができません。したがって、合計の美しさは「\(i-2\) 番目までの最大値 + \(A_i\)」となります。 2. \(i\) 番目に花を植えない場合： この場合、制約の影響を受けません。したがって、合計の美しさは「\(i-1\) 番目までの最大値」をそのまま引き継ぎます。

このように、大きな問題を小さな部分問題に分解して解く手法である動的計画法 (DP) が有効です。

アルゴリズム

動的計画法 (DP)

以下の定義で DP を行います。 - \(dp[i]\) ： \(i\) 番目の花壇まで考慮したときの美しさの合計の最大値

遷移式は以下のようになります： $\(dp[i] = \max(dp[i-1], dp[i-2] + A_i)\)$

空間の最適化

素直に配列 \(dp\) を作成すると長さ \(N\) のメモリが必要ですが、式を見ると \(dp[i]\) を計算するのに必要なのは \(dp[i-1]\) と \(dp[i-2]\) の 2 つの値だけです。 そのため、変数 2 つ（dp_prev1, dp_prev2）だけで状態を保持しながらループを回すことで、メモリ使用量を節約できます。

計算量

• 時間計算量: \(O(N)\) 花壇の数 \(N\) に対して、ループを 1 回回すだけで計算が完了するため、非常に高速です。
• 空間計算量: \(O(N)\) 入力された配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。DP の計算自体は \(O(1)\) の追加変数で行えます。

実装のポイント

• 高速な入力: Python では \(N\) が大きい場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

• 初期値: \(i=1\) のときは \(i-2\) が存在しないため、初期値を \(0\) として扱うことで、ループ内で統一的に処理できます。

• 大きな数値の扱い: Python は標準で多倍長整数をサポートしているため、合計値が \(10^{14}\) 程度（\(10^9 \times 2 \times 10^5\)）になっても、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は高速に大量の入力を読み込むのに適しています
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了
    if not input_data:
        return
    
    # 1番目の要素は花壇の数 N
    n = int(input_data[0])
    
    # 2番目以降の要素は各花壇の美しさ A_i
    # map(int, ...) を使って効率的に整数に変換する
    a_values = map(int, input_data[1:n+1])
    
    # 動的計画法（DP）を用いて最大値を求める
    # dp_prev2: i-2 番目の花壇までを考慮したときの最大美しさ
    # dp_prev1: i-1 番目の花壇までを考慮したときの最大美しさ
    dp_prev2 = 0
    dp_prev1 = 0
    
    # 各花壇の美しさについて順番に処理を行う
    for a_i in a_values:
        # i 番目の花壇に花を植えるかどうかの2択を考える
        # 1. 花を植えない場合: 合計の美しさは i-1 番目までの最大値 (dp_prev1) と同じ
        # 2. 花を植える場合: 隣り合う花壇には植えられないため、i-2 番目までの最大値 (dp_prev2) に 
        #    現在の美しさ a_i を加えたものになる
        
        option_not_plant = dp_prev1
        option_plant = dp_prev2 + a_i
        
        # 2つの選択肢のうち、大きい方を現在の最大値とする
        if option_not_plant > option_plant:
            current_max = option_not_plant
        else:
            current_max = option_plant
            
        # 次のループ（i+1番目の花壇）に向けて状態を更新する
        dp_prev2 = dp_prev1
        dp_prev1 = current_max
        
    # すべての花壇を考慮した後の最大値を出力する
    print(dp_prev1)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。