概要

\(N\) 個のタスクを順番に処理する際、省エネモード（処理能力 \(A\)、バッテリー消費なし）とフルパワーモード（処理能力＝現在のバッテリー残量、使用後バッテリー半減）を適切に選び、全タスクを完了できるか判定し、可能ならフルパワーモードの使用回数を最小化する問題です。

考察

重要な気づき

各タスク \(i\) に対して、処理能力の観点で考えると：

• \(H_i \leq A\) の場合：省エネモードで十分対応できる。バッテリーを消費しないため、わざわざフルパワーモードを使う理由がない。
• \(H_i > A\) の場合：省エネモードでは処理能力が足りないため、必ずフルパワーモードを使わなければならない。

つまり、フルパワーモードを使う必要があるタスクは一意に決まります。「使わなければならない場面でだけ使う」のが最適です。

なぜ余計にフルパワーモードを使うことが損か

フルパワーモードを使うとバッテリーが半減します。将来のフルパワーモードの処理能力が下がるため、不必要に使うと損になります。省エネモードで済む場面ではそちらを使うべきです。

アルゴリズム

貪欲法（Greedy）で解きます。

1. バッテリー残量を \(M\) で初期化し、タスクを先頭から順に見る。
2. \(H_i \leq A\) なら省エネモードを使い、バッテリーは変化しない。
3. \(H_i > A\) なら、フルパワーモードを使う必要がある：
   • 現在のバッテリー残量 \(p\) が \(H_i\) 未満なら、タスクを完了できないので -1 を出力して終了。
   • \(p \geq H_i\) なら、フルパワーモードを使い、カウントを \(1\) 増やし、バッテリーを \(\lfloor p/2 \rfloor\) に更新する。
4. すべてのタスクを処理できたら、カウントを出力する。

具体例

\(N=3,\ M=10,\ A=3,\ H=[2,\ 8,\ 4]\) の場合：

タスク	\(H_i\)	モード	バッテリー（使用前→使用後）
1	2	省エネ (\(2 \leq 3\))	\(10 \to 10\)
2	8	フルパワー (\(8 > 3\), \(10 \geq 8\) ✓)	\(10 \to 5\)
3	4	フルパワー (\(4 > 3\), \(5 \geq 4\) ✓)	\(5 \to 2\)

答え：2

計算量

• 時間計算量: \(O(N)\) — 各タスクを一度ずつ走査するのみ
• 空間計算量: \(O(N)\) — 配列 \(H\) の格納

実装のポイント

• \(M\) や \(H_i\) が最大 \(10^{18}\) になるため、long long 型を使う必要がある。

• バッテリーの半減は整数除算 battery / 2 で自動的に切り捨てになる（C++ の仕様）。

• タスクの順序は固定なので、単純な前から順のシミュレーションで十分。判断が局所的（今の \(H_i\) と \(A\) の比較、今のバッテリーとの比較のみ）なので、探索や二分探索は不要。

  ソースコード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, M, A;
    cin >> N >> M >> A;
    
    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];
    
    long long battery = M;
    long long count = 0;
    
    for (int i = 0; i < N; i++) {
        if (H[i] <= A) {
            // Use energy-saving mode, no battery cost
            continue;
        } else {
            // Must use full-power mode
            if (battery < H[i]) {
                cout << -1 << endl;
                return 0;
            }
            count++;
            battery = battery / 2;
        }
    }
    
    cout << count << endl;
    return 0;
}

---

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