概要

\(N\) 個の銘柄のうち好きなものを選んで評価額を \(2\) 倍にする操作を \(K\) 回行い、評価額の合計を最大化する問題です。最大の銘柄に全ての操作を集中させるのが最適であることに気づくのがポイントです。

考察

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

操作1回で得られる「増加分」を考えてみましょう。評価額が \(x\) の銘柄を \(2\) 倍にすると、増加分は \(2x - x = x\) です。つまり、評価額が大きい銘柄ほど、2倍にしたときの増加分が大きいのです。

したがって、合計を最大化するには毎回「現在最大の銘柄」を選ぶのが最適です。

具体例

\(N = 3\), \(K = 2\), \(L = [3, 5, 1]\) の場合を考えます。

• 1回目：最大値 \(5\) を2倍 → \([3, 10, 1]\)（合計 \(14\)）
• 2回目：最大値 \(10\) を2倍 → \([3, 20, 1]\)（合計 \(24\)）

一度最大値を2倍にすると、その銘柄は引き続き最大なので、結局すべての操作は初期状態で最大の銘柄に集中します。

まとめると

初期値の最大値を \(M\)、それ以外の合計を \(S\) とすると、答えは：

\[\text{答え} = S + M \times 2^K\]

素朴なシミュレーションではなぜダメか

\(K\) は最大 \(10^{18}\) と非常に大きいため、1回ずつシミュレーションすると \(O(K)\) となり全く間に合いません。上記の式を直接計算すれば \(O(1)\)（べき乗の計算を除く）で求まります。

アルゴリズム

1. 配列 \(L\) から最大値 \(M = \max(L)\) を求める。
2. それ以外の要素の合計 \(S = \sum L_i - M\) を求める。
3. \(2^K \mod (10^9 + 7)\) を繰り返し二乗法（モジュラ累乗）で高速に計算する。
4. 答えを \((S + M \times 2^K) \mod (10^9 + 7)\) として出力する。

繰り返し二乗法とは

\(2^K\) を普通に \(K\) 回掛け算すると \(O(K)\) かかりますが、繰り返し二乗法を使うと \(O(\log K)\) で計算できます。例えば \(2^{10}\) を求めるとき：

• \(2^1 \to 2^2 \to 2^4 \to 2^8 \to 2^{10} = 2^8 \times 2^2\)

のように、指数を2進数で分解して計算します。Python では pow(2, K, MOD) で自動的にこの方法が使われます。

計算量

• 時間計算量: \(O(N + \log K)\)
  • \(O(N)\)：最大値と合計の計算
  • \(O(\log K)\)：\(2^K \mod (10^9+7)\) の計算（繰り返し二乗法）
• 空間計算量: \(O(N)\)（入力の格納）

実装のポイント

• modの取り忘れに注意：\(S\) や \(M\) もそれぞれ mod を取ってから掛け算・足し算を行う必要があります。Python では多倍長整数を扱えるため溢れませんが、最終的に mod を取ることを忘れないようにしましょう。

• Python の pow(base, exp, mod) は繰り返し二乗法を内部で行ってくれるので、自分で実装する必要はありません。

• 最大値が複数ある場合でも、そのうちどれか1つに全操作を集中すればよいため、結果は変わりません。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    L = [int(input_data[i + 2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # To maximize the sum, we should always double the largest current value.
    # So we should apply all K doublings to the maximum element.
    # The maximum element gets multiplied by 2^K, and the rest stay the same.
    
    max_val = max(L)
    total_rest = sum(L) - max_val
    
    # Answer = total_rest + max_val * 2^K
    # All mod 10^9+7
    
    ans = (total_rest % MOD + (max_val % MOD) * pow(2, K, MOD)) % MOD
    print(ans)

solve()

---

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