概要

各タスクを順番に処理し、省エネモードで足りないタスクだけフルパワーモードを使います。
すべて完了できるかを判定し、可能ならフルパワーモードの使用回数の最小値を求めます。

考察

タスク \(i\) の必要処理能力を \(H_i\) とします。

省エネモードでは常に処理能力 \(A\) を出せます。したがって、

• \(H_i \leq A\) のタスク
  → 省エネモードで完了できます。
• \(H_i > A\) のタスク
  → 省エネモードでは完了できないため、必ずフルパワーモードを使う必要があります。

ここで重要なのは、フルパワーモードを使うとバッテリー残量が \(\lfloor p/2 \rfloor\) に減ってしまうことです。
バッテリー残量は増えることがなく、フルパワーモードを使うほど減っていきます。

そのため、\(H_i \leq A\) のタスクでわざわざフルパワーモードを使うメリットはありません。

• フルパワーモードの使用回数が増える
• バッテリー残量が減る
• 将来のタスクが達成しにくくなる

だけなので、最適解では必ず省エネモードを選びます。

一方で、\(H_i > A\) のタスクではフルパワーモードを使う以外に選択肢がありません。
このとき現在のバッテリー残量を \(p\) とすると、\(p \geq H_i\) でなければそのタスクは完了できず、不可能です。

したがって、タスクを前から順に見て、

• \(H_i \leq A\) なら何もしない
• \(H_i > A\) ならフルパワーモードが必須
  • 現在のバッテリー残量 \(p\) が \(H_i\) 未満なら不可能
  • そうでなければ使用回数を \(1\) 増やし、\(p\) を \(\lfloor p/2 \rfloor\) にする

というシミュレーションで十分です。

例えば、\(M=20, A=7, H=[5,10,6,8,3]\) の場合を考えます。

• \(H_1=5 \leq 7\) なので省エネモード
• \(H_2=10 > 7\) なのでフルパワーモード
  現在のバッテリーは \(20\) なので成功、使用後は \(10\)
• \(H_3=6 \leq 7\) なので省エネモード
• \(H_4=8 > 7\) なのでフルパワーモード
  現在のバッテリーは \(10\) なので成功、使用後は \(5\)
• \(H_5=3 \leq 7\) なので省エネモード

この場合、フルパワーモードの最小使用回数は \(2\) 回です。

素朴に各タスクで「省エネモードを使うか、フルパワーモードを使うか」を全探索すると、選択肢は最大で \(2^N\) 通りあります。
\(N \leq 3 \times 10^5\) なので、この方法では到底間に合いません。

しかし上の考察により、各タスクでの選択は実質的に一意に決まるため、前から一度見るだけで解けます。

アルゴリズム

現在のバッテリー残量を \(p\)、フルパワーモードの使用回数を ans とします。

初期状態は、

• \(p = M\)
• ans = 0

です。

各タスク \(H_i\) について、順番に以下を行います。

1. \(H_i \leq A\) の場合
   省エネモードで完了できるので何もしません。

2. \(H_i > A\) の場合
   フルパワーモードが必須です。

   • もし \(p < H_i\) なら、そのタスクを完了できないので -1 を出力して終了します。
   • そうでなければ、フルパワーモードを使います。
     • ans を \(1\) 増やす
     • \(p\) を \(\lfloor p/2 \rfloor\) に更新する

最後まで処理できたら、ans を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

バッテリー残量や処理能力は最大で \(10^{18}\) なので、32 bit 整数では足りません。
Python の int は大きな整数も扱えるため問題ありません。

また、フルパワーモード使用後のバッテリー残量は \(\lfloor p/2 \rfloor\) なので、Python では p //= 2 と書けばよいです。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, A = map(int, input().split())
    H = list(map(int, input().split()))

    p = M
    ans = 0

    for h in H:
        if h > A:
            if p < h:
                print(-1)
                return
            ans += 1
            p //= 2

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。