概要

隣り合う花壇に同時に花を植えられないという制約のもとで、美しさの合計を最大化する問題です。動的計画法（DP）を使って効率的に解くことができます。

考察

問題の本質

この問題は「隣り合う要素を同時に選べない」という制約付きの最大和問題です。これは典型的なDPで解ける問題パターンです。

素朴なアプローチの問題点

全ての花壇について「植える／植えない」の2通りを考えると、\(2^N\) 通りの組み合わせを調べる必要があります。\(N\) が最大 \(2 \times 10^5\) のため、これでは時間が足りません（TLE）。

重要な気づき

各花壇について決定を下すとき、重要なのは直前の花壇に花を植えたかどうかだけです。それより前の花壇の状態は、直前の状態に集約されています。

この「直前の状態だけで次の状態が決まる」という性質がDPを適用できる鍵です。

アルゴリズム

DP の定義

\(i\) 番目の花壇まで見たときの状態を以下のように定義します： - \(dp[i][0]\)：\(i\) 番目の花壇に花を植えない場合の、最大美しさ - \(dp[i][1]\)：\(i\) 番目の花壇に花を植える場合の、最大美しさ

遷移式

• 植えない場合：前の花壇は植えても植えなくてもよい $\(dp[i][0] = \max(dp[i-1][0], dp[i-1][1])\)$

• 植える場合：前の花壇には植えられない（隣り合うため） $\(dp[i][1] = dp[i-1][0] + A_i\)$

具体例

\(N = 4\), \(A = [3, 2, 5, 1]\) の場合：

\(i\)	\(A_i\)	\(dp[i][0]\)（植えない）	\(dp[i][1]\)（植える）
0	3	0	3
1	2	max(0, 3) = 3	0 + 2 = 2
2	5	max(3, 2) = 3	3 + 5 = 8
3	1	max(3, 8) = 8	3 + 1 = 4

答え：\(\max(8, 4) = 8\)（1番目と3番目の花壇に植える）

空間最適化

遷移には直前の状態（\(i-1\)）だけが必要なので、配列全体を保持せず、2つの変数だけで計算できます。

計算量

• 時間計算量: \(O(N)\)
  • 各花壇について定数時間の計算を1回ずつ行うため
• 空間計算量: \(O(1)\)
  • 空間最適化により、直前の状態を保持する変数のみ使用
  • （入力配列を除く追加のメモリ）

実装のポイント

• 初期化: 最初の花壇（\(i=0\)）について、植えない場合は \(0\)、植える場合は \(A_0\) で初期化

• \(N=1\) の特殊ケース: 花壇が1つだけの場合は、その花を植えるのが最適（ループに入らないため別処理）

• 最終的な答え: 最後の花壇について「植える場合」と「植えない場合」の大きい方を出力

  ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(A[0])
        return
    
    # dp[i][0] = i番目の花壇に花を植えない場合の最大美しさ
    # dp[i][1] = i番目の花壇に花を植える場合の最大美しさ
    
    # 空間最適化: 前の状態だけ保持
    prev_not_plant = 0  # 前の花壇に植えない場合の最大値
    prev_plant = A[0]   # 前の花壇に植える場合の最大値
    
    for i in range(1, N):
        # 現在の花壇に植えない場合: 前の花壇は植えても植えなくてもよい
        curr_not_plant = max(prev_not_plant, prev_plant)
        # 現在の花壇に植える場合: 前の花壇には植えられない
        curr_plant = prev_not_plant + A[i]
        
        prev_not_plant = curr_not_plant
        prev_plant = curr_plant
    
    print(max(prev_not_plant, prev_plant))

solve()

---

この解説は claude4.5opus によって生成されました。