概要

\(N\) 種類のトレーニングマシンから、連続しないように \(K\) 回選んで得られる運動効果の合計の最大値を求めます。

考察

この問題では、同じマシンを連続して使うことができません。したがって、最適な選び方を考える上で、できるだけ高い運動効果を持つマシンを多く使うことが重要です。

まず、最も簡単なケースとして \(K = 1\) のときは、単純に最大の運動効果を選ぶのが最適です。

次に、\(K \geq 2\) の場合を考えます。

重要な観察

• 最大の運動効果を持つマシンが 2つ以上ある 場合：

  • これらを交互に使うことで、毎回最大値を得ることができます。
  • つまり、合計は \(K \times \text{最大値}\) となります。

• 最大値が 1つだけ の場合：

  • 連続して使えないため、最大値のマシンを使った後は、次に最も高い運動効果のマシンを使う必要があります。
  • このとき最適なパターンは：
    [最大値, 第二の最大値, 最大値, 第二の最大値, ...]
    のように交互に使うことです。
  • この場合の合計は、 $\( \left\lfloor \frac{K}{2} \right\rfloor \times (\text{最大値} + \text{第二の最大値}) + (K \bmod 2) \times \text{最大値} \)$ となります。

このように、全探索やDPなどを行うことなく、最大値と第二の最大値を調べるだけで解けてしまいます。

アルゴリズム

1. 入力を読み込み、最大値と第二の最大値を求める。
2. 最大値が複数あるかどうかを判定する。
   • あれば、答えは \(K \times \text{最大値}\)。
3. 最大値が1つだけであれば、交互に最大値と第二の最大値を使うパターンで合計を計算する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力分を除く）

実装のポイント

• 最大値と第二の最大値を正しく求めること。
• \(K = 1\) のケースを忘れずに処理すること。
• 最大値が複数あるかどうかを count() などで判定できる。

## ソースコード

```python
import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 最大値とそのインデックスを取得
    max_val = max(A)
    max_idx = A.index(max_val)

    # 最大値以外の最大値（異なるインデックス）
    second_max = 0
    for i in range(N):
        if i != max_idx:
            second_max = max(second_max, A[i])

    # もしK=1なら、単純に最大値を返す
    if K == 1:
        print(max_val)
        return

    # 最大値が複数あるかどうかを確認
    max_count = A.count(max_val)

    if max_count >= 2:
        # 同じ最大値を交互に使えるので、K * max_val
        print(K * max_val)
    else:
        # 最大値が1つだけの場合
        # 最初に最大値を使って、その後はsecond_maxと交互に使うのが最適
        # パターン: [max_val, second_max, max_val, second_max, ...]
        # 合計 = (K // 2) * (max_val + second_max) + (K % 2) * max_val
        res = (K // 2) * (max_val + second_max)
        if K % 2 == 1:
            res += max_val
        print(res)

if __name__ == "__main__":
    main()

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