概要

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

考察

\(i\) 番目のタスクに必要な処理能力は \(H_i\) です。

省エネモードでは常に \(A\) の処理能力を発揮できます。
そのため、もし \(H_i \leq A\) なら、省エネモードで必ず完了できます。

一方で、\(H_i > A\) の場合、省エネモードでは処理能力が足りません。
したがって、このタスクを完了するにはフルパワーモードを使うしかありません。

つまり、各タスクでの選択は実はほぼ決まっています。

• \(H_i \leq A\)：省エネモードを使うのが最適
• \(H_i > A\)：フルパワーモードを使うしかない

ここで、\(H_i \leq A\) のタスクに対してあえてフルパワーモードを使うメリットはありません。

理由は以下の通りです。

• フルパワーモードを使うとバッテリーが減る
• フルパワーモードの使用回数も増える
• 将来のタスクが楽になることもない

したがって、\(H_i \leq A\) のタスクでは必ず省エネモードを選ぶのが最善です。

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

しかし上の観察により、選択は次のように一意に決まります。

• 省エネモードで足りるなら省エネモード
• 足りないならフルパワーモード

あとは、フルパワーモードを使う必要があるタスクで、現在のバッテリー残量が \(H_i\) 以上あるかを確認すればよいです。

例えば、

\(M = 20, A = 5\)、タスクが \([3, 8, 4, 9]\) の場合を考えます。

• \(3 \leq 5\) なので省エネモード
• \(8 > 5\) なのでフルパワーモード
  現在のバッテリーは \(20\) なので実行可能
  使用後のバッテリーは \(\lfloor 20 / 2 \rfloor = 10\)
• \(4 \leq 5\) なので省エネモード
• \(9 > 5\) なのでフルパワーモード
  現在のバッテリーは \(10\) なので実行可能
  使用後のバッテリーは \(\lfloor 10 / 2 \rfloor = 5\)

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

アルゴリズム

現在のバッテリー残量を battery として管理します。初期値は \(M\) です。
また、フルパワーモードの使用回数を ans とします。

タスクを先頭から順に見ていきます。

1. タスクの必要処理能力を \(H\) とする
2. もし \(H \leq A\) なら、省エネモードで処理できるので何もしない
3. もし \(H > A\) なら、フルパワーモードが必要
   • そのとき battery < H なら、このタスクを処理できないので -1 を出力して終了
   • そうでなければ、フルパワーモードを使う
     • ans を \(1\) 増やす
     • battery を \(\lfloor battery / 2 \rfloor\) に更新する

最後まで処理できれば、ans が答えです。

計算量

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

実装のポイント

\(M, A, H_i\) は最大で \(10^{18}\) なので、int ではなく long long を使う必要があります。

また、フルパワーモードでタスクを処理できるかどうかは、バッテリーを減らす前の値で判定します。

つまり、

if (battery < H) {
    cout << -1 << '\n';
    return 0;
}

ans++;
battery /= 2;

の順番にする必要があります。

入力された \(H_i\) は順番に処理すればよいため、配列としてすべて保存する必要はありません。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M, A;
    cin >> N >> M >> A;

    long long battery = M;
    int ans = 0;

    for (int i = 0; i < N; i++) {
        long long H;
        cin >> H;

        if (H <= A) {
            continue;
        }

        if (battery < H) {
            cout << -1 << '\n';
            return 0;
        }

        ans++;
        battery /= 2;
    }

    cout << ans << '\n';
    return 0;
}

---

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