概要

\(N\) 個の銘柄からちょうど \(K\) 回「選んだ銘柄の価値を2倍にする」操作を行い、合計資産価値を最大化する問題です。最大値の銘柄に全ての操作を集中させるのが最適であり、繰り返し二乗法を用いて高速に計算します。

考察

重要な気づき：常に最大の銘柄を2倍にするのが最適

操作1回で得られる増加量に注目しましょう。資産価値が \(X\) の銘柄を2倍にすると、増加量は \(2X - X = X\) です。

つまり、現時点で最も資産価値が大きい銘柄を2倍にするのが、1回あたりの増加量を最大化することになります。

具体例で考えます。\(S = [3, 5]\), \(K = 2\) の場合：

• 5を2回選ぶ: \(3 + 5 \times 2^2 = 3 + 20 = 23\)
• 5を1回、3を1回: \((3 \times 2) + (5 \times 2) = 6 + 10 = 16\)
• 3を2回選ぶ: \(3 \times 4 + 5 = 12 + 5 = 17\)

5を2回選ぶのが最大です。

一般に、最初の操作で最大値の銘柄を選ぶと、その銘柄は \(2 \times \max(S)\) となり、他のどの銘柄よりも大きいままです（元々最大だったので）。よって2回目以降もずっと同じ銘柄を選び続けるのが最適です。

結論

\(K\) 回すべての操作を、初期値が最大の銘柄 \(S_{\max}\) に適用するのが最適です。

最終的な合計は：

\[\text{答え} = \left(\sum_{i=1}^{N} S_i - S_{\max}\right) + S_{\max} \times 2^K\]

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

\(K\) が最大 \(10^{18}\) と非常に大きいため、\(K\) 回ループして2倍する方法では到底間に合いません。\(2^K\) を高速に計算する必要があります。

アルゴリズム

1. \(S\) の最大値 \(S_{\max}\) と合計 \(\text{total}\) を求める。
2. \(2^K \mod (10^9 + 7)\) を繰り返し二乗法（バイナリ法）で計算する。
   • Python では pow(2, K, MOD) で \(O(\log K)\) で計算できます。
3. 答えを以下の式で計算する：

\[\text{ans} = \left((\text{total} - S_{\max}) + S_{\max} \times 2^K\right) \mod (10^9 + 7)\]

計算量

• 時間計算量: \(O(N + \log K)\)
  • \(O(N)\): 最大値と合計の計算
  • \(O(\log K)\): 繰り返し二乗法による \(2^K \mod (10^9+7)\) の計算
• 空間計算量: \(O(N)\)
  • 入力の配列を保持する分

実装のポイント

• 繰り返し二乗法: Python の組み込み関数 pow(base, exp, mod) を使えば、\(O(\log K)\) でのモジュラー累乗が簡単に書けます。

• MOD の取り方: \(\text{total} - S_{\max}\) と \(S_{\max} \times 2^K\) をそれぞれ \(\mod (10^9 + 7)\) で計算してから足し合わせます。\(\text{total} - S_{\max}\) は非負なので、MOD を取る際に負数になる心配はありません。

• 最大値が複数ある場合: どれか1つに全操作を集中すればよく、結果は同じです。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    S = [int(input_data[i + 2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # To maximize the total sum, we should always double the largest current value.
    # So we find the maximum value and apply all K doublings to it.
    max_val = max(S)
    total = sum(S)
    
    # The answer is (total - max_val) + max_val * 2^K
    # = (total - max_val) + max_val * 2^K
    
    rest = (total - max_val) % MOD
    contribution = (max_val % MOD) * pow(2, K, MOD) % MOD
    
    ans = (rest + contribution) % MOD
    print(ans)

solve()

---

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