概要

連続した社員をグループに分割し、各グループの「生産性」の合計を最大化する問題です。生産性は「グループの人数 × 能力値の合計」で計算されます。

考察

この問題では、社員を連続した区間に分割する必要があり、各区間の生産性を足し合わせた値を最大化するのが目的です。

素朴な方法として、全ての区間の組み合わせを試すことが考えられますが、これは指数時間になってしまうため現実的ではありません。例えば再帰的に分割位置を決めていくと、計算量が爆発してしまいます。

そこで、動的計画法（DP）を用いることを考えます。

DPの定義

dp[i] を「最初の \(i\) 人についての生産性の合計の最大値」とします。初期値は dp[0] = 0 です。

次に、dp[i] を更新するために、過去の状態 dp[j] （\(0 \leq j < i\)）を見て、「区間 \([j+1, i]\) のグループを作る」という選択を加えたときの生産性を計算します。

この区間の生産性は： $\( \text{生産性} = (i - j) \times \sum_{k=j+1}^{i} P_k \)$

この合計部分 \(\sum P_k\) を高速に求めたいので、累積和を使います。
S[i] を \(P_1 + P_2 + \cdots + P_i\) と定義すると、区間和は \(S[i] - S[j]\) で求められます。

このようにして、各 \(i\) に対して \(j\) を全部試しても、全体で \(O(N^2)\) となり、制約 \(N \leq 5000\) でも十分間に合います。

アルゴリズム

1. 入力を読み込み、累積和配列 \(S\) を構築する。
2. DPテーブル dp を初期化する。dp[0] = 0、他は \(-\infty\) で初期化。
3. 各 \(i = 1, 2, ..., N\) に対して以下を行う：
   • 各 \(j = 0, 1, ..., i-1\) に対して、区間 \([j+1, i]\) の生産性を計算： $\( \text{生産性} = (i - j) \times (S[i] - S[j]) \)$
   • dp[i] = max(dp[i], dp[j] + 生産性) で更新する。
4. dp[N] を出力する。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和を前処理で構築しておくことで、区間和を高速に求められるようにする。

• DPテーブルの初期値に注意：dp[0] = 0、それ以外は十分に小さい値（例：-float('inf')）で初期化。

• 区間 \([j+1, i]\) の長さは \(i - j\)、区間和は \(S[i] - S[j]\)。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:N+1]))
    
    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + P[i]
    
    # dp[i] := 最初のi人についての生産性の合計の最大値
    dp = [-float('inf')] * (N + 1)
    dp[0] = 0
    
    for i in range(1, N + 1):
        for j in range(i):
            # 区間[j+1, i]のグループを作る
            length = i - j
            sum_P = S[i] - S[j]
            productivity = length * sum_P
            if dp[j] + productivity > dp[i]:
                dp[i] = dp[j] + productivity
    
    print(dp[N])

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。