概要

同じマシンを連続して使えない制約のもと、\(K\) 回のトレーニングで得られる運動効果の合計を最大化する問題です。

考察

重要な気づき

運動効果を最大化するには、なるべく効果の高いマシンを多く使いたいです。しかし「同じマシンを連続して使えない」という制約があります。

ここで重要な観察があります： - 最大値のマシンをできるだけ多く使いたい - 連続使用を避けるため、間に別のマシンを挟む必要がある - 間に挟むなら、2番目に効果の高いマシンが最適

つまり、上位2つのマシン（\(\text{max1}\), \(\text{max2}\)）だけを考えれば十分です。

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

「\(K\) 回のループを回して毎回最適な選択をする」というシミュレーションは、\(K\) が最大 \(10^9\) なので明らかに TLE になります。

解決策

パターンを分析して、数式で直接計算します。

場合1: \(\text{max1} = \text{max2}\) の場合 - 最大効果のマシンが複数台あるので、それらを交互に使える - 毎回 \(\text{max1}\) の効果を得られる - 合計 = \(\text{max1} \times K\)

場合2: \(\text{max1} > \text{max2}\) の場合 - \(\text{max1}\), \(\text{max2}\), \(\text{max1}\), \(\text{max2}\), … と交互に使う - \(K\) 回中、\(\text{max1}\) を \(\lceil K/2 \rceil\) 回、\(\text{max2}\) を \(\lfloor K/2 \rfloor\) 回使える

具体例

\(N=3\), \(K=5\), \(A = [10, 7, 3]\) の場合： - \(\text{max1} = 10\), \(\text{max2} = 7\) - パターン: \(10 \to 7 \to 10 \to 7 \to 10\) - \(\text{max1}\) を \(\lceil 5/2 \rceil = 3\) 回、\(\text{max2}\) を \(\lfloor 5/2 \rfloor = 2\) 回 - 合計 = \(10 \times 3 + 7 \times 2 = 44\)

アルゴリズム

1. 配列 \(A\) を降順にソートする
2. 最大値 \(\text{max1} = A[0]\)、2番目 \(\text{max2} = A[1]\) を取得
3. \(\text{max1} = \text{max2}\) なら、答えは \(\text{max1} \times K\)
4. そうでなければ、答えは \(\text{max1} \times \lceil K/2 \rceil + \text{max2} \times \lfloor K/2 \rfloor\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（配列の格納）

実装のポイント

• \(\lceil K/2 \rceil\) は (K + 1) // 2 で計算できる

• \(\lfloor K/2 \rfloor\) は K // 2 で計算できる

• \(K\) や \(A_i\) が最大 \(10^9\) なので、答えが最大 \(10^{18}\) 程度になる可能性がある。Python では整数オーバーフローの心配はないが、他の言語では注意が必要

• 制約 \(N \geq 2\) より、\(\text{max2}\) は必ず存在することが保証されている

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sort in descending order
    A.sort(reverse=True)
    
    # Get the two largest values
    max1 = A[0]  # Largest
    max2 = A[1]  # Second largest
    
    # Strategy:
    # - If max1 == max2, we can use them alternately for all K rounds
    #   Total = K * max1
    # - If max1 > max2, we want to use max1 as much as possible
    #   We alternate between max1 and max2
    #   In K rounds, we can use max1 ceil(K/2) times and max2 floor(K/2) times
    #   But we need to be careful: we use max1, max2, max1, max2, ...
    #   If K is odd: (K+1)/2 times max1, K/2 times max2
    #   If K is even: K/2 times max1, K/2 times max2
    
    if max1 == max2:
        # All top values are the same, can use any of them every round
        result = max1 * K
    else:
        # Alternate between max1 and max2
        # Pattern: max1, max2, max1, max2, ...
        # Number of max1 uses: ceil(K/2) = (K+1)//2
        # Number of max2 uses: floor(K/2) = K//2
        times_max1 = (K + 1) // 2
        times_max2 = K // 2
        result = max1 * times_max1 + max2 * times_max2
    
    print(result)

solve()

---

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