概要

\(N\) 個の銘柄から 1 つを選んで評価額を 2 倍にする操作を \(K\) 回行い、最終的な評価額の合計を最大化する問題です。合計値を \(10^9 + 7\) で割った余りを出力します。

考察

どの銘柄を倍にするべきか？

合計値を最大化するためには、各操作において「増える金額」を最大にすればよいことになります。 ある銘柄の評価額が \(X\) であるとき、それを 2 倍にすると評価額は \(2X\) になり、合計値は \(X\) だけ増加します。

したがって、その時点で最も評価額が高い銘柄を選んで 2 倍にするのが常に最善です。

操作を繰り返すとどうなるか？

評価額が正の数であるとき、最大の銘柄を 2 倍にしても、その銘柄は引き続き「最大の銘柄」であり続けます。 例えば、銘柄の評価額が \(\{3, 5, 8\}\) の場合、最大値は \(8\) です。 1. \(8\) を 2 倍にする \(\rightarrow \{3, 5, 16\}\) （最大値は \(16\)） 2. \(16\) を 2 倍にする \(\rightarrow \{3, 5, 32\}\) （最大値は \(32\)）

このように、一度最大である銘柄は、2 倍にした後も他の銘柄に追い越されることはありません。つまり、「最初から最後まで、初期状態で最大値である銘柄を \(K\) 回連続で 2 倍にし続ける」のが最適な戦略となります。

大きな \(K\) への対処

\(K\) は最大で \(10^{18}\) と非常に大きいため、実際に 2 倍にする操作を \(K\) 回繰り返すと、計算が終わらなくなってしまいます（TLE）。 しかし、ある値 \(M\) を \(K\) 回 2 倍にするということは、\(M \times 2^K\) を計算することと同じです。 プログラミング言語の機能（Pythonの pow 関数など）を用いることで、\(2^K \pmod{10^9+7}\) は \(O(\log K)\) という非常に高速な時間で計算可能です。

アルゴリズム

1. 入力された銘柄 \(L_1, L_2, \ldots, L_N\) の中から最大値 \(M\) を見つける。
2. 最大値以外の銘柄の合計 \(S_{others}\) を計算する。
3. 最大値 \(M\) を \(K\) 回 2 倍にした値 \(M_{final} = M \times 2^K \pmod{10^9+7}\) を計算する。
4. 最終的な答えを \((S_{others} + M_{final}) \pmod{10^9+7}\) として出力する。

計算量

• 時間計算量: \(O(N + \log K)\)
  • 最大値の探索と合計の計算に \(O(N)\)、繰り返し二乗法による \(2^K\) の計算に \(O(\log K)\) かかります。
• 空間計算量: \(O(N)\)
  • \(N\) 個の銘柄の値を保持するリストのメモリが必要です。

実装のポイント

• 大きな数の余り: 計算の途中で値が非常に大きくなるため、適切に mod（\(10^9 + 7\)）を取る必要があります。

• 累乗の計算: Pythonでは pow(base, exp, mod) を使うことで、巨大な指数の累乗を高速かつ余りを取った状態で計算できます。

• 最大値が複数ある場合: 最大値が複数存在しても、そのうちのどれか 1 つを \(K\) 回倍にし続ければよいため、結果は変わりません。

  ソースコード

import sys

def solve():
    # Read all input data at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of stocks, K is the number of investment chances
    n = int(input_data[0])
    k = int(input_data[1])
    
    # L is the list of current assessment values for the N stocks
    l = list(map(int, input_data[2:]))
    
    mod = 10**9 + 7
    
    # To maximize the total sum, the optimal strategy is to always double
    # the stock that currently has the highest assessment value.
    # Since all L_i >= 1, doubling the maximum value will always result 
    # in a value that remains the maximum. Thus, we pick the initial 
    # maximum value and double it exactly K times.
    
    max_val = max(l)
    total_sum = sum(l)
    
    # Calculate the sum of the other N-1 stocks modulo 10^9 + 7
    # These values remain unchanged throughout the operations.
    others_sum = (total_sum - max_val) % mod
    
    # Calculate the value of the chosen maximum stock after K doublings.
    # We use modular exponentiation (pow(base, exp, mod)) for efficiency.
    max_val_final = (max_val % mod * pow(2, k, mod)) % mod
    
    # The final total sum is the sum of the unchanged stocks and the doubled stock.
    ans = (others_sum + max_val_final) % mod
    
    # Output the result modulo 10^9 + 7
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。