概要

この問題は、各タスクを「省エネモード」と「フルパワーモード」のどちらで処理するかを、各ステップにおいて最適な選択をしていく貪欲法（Greedy）を用いて解くことができます。

考察

この問題の鍵は、「バッテリー残量をできるだけ多く残しておくことが、常に先のタスクで有利に働く」という点です。

バッテリー残量 \(p\) は初期値 \(M\) から始まり、フルパワーモードを使うたびに \(\lfloor p/2 \rfloor\) に減少します。一度減ったバッテリーが回復することはありません。したがって、バッテリーの消費を抑えられる場面では、温存しておくのが常に最善の戦略となります。

各タスク \(i\)（必要処理能力 \(H_i\)）について、現在のバッテリー残量を \(p\) としたとき、どのようにモードを選択すべきか順を追って考えてみましょう。

1. 省エネモードでクリアできる場合（\(H_i \le A\)）

省エネモードの処理能力 \(A\) だけでタスクを完了できるなら、必ず省エネモードを選択すべきです。 フルパワーモードを使ってもタスクは完了できますが、バッテリー残量が半分に減ってしまい、以降のタスクで不利になるだけです。メリットは一切ありません。

2. 省エネモードでクリアできない場合（\(H_i > A\)）

省エネモードでは処理能力が足りないため、フルパワーモードを選択するしかありません。 このとき、さらに 2 つの状況に分かれます。 - \(p \ge H_i\) のとき: フルパワーモードでタスクを完了できます。バッテリー残量 \(p\) は \(\lfloor p/2 \rfloor\) に減少し、フルパワーモードの使用回数を \(1\) 増やします。 - \(p < H_i\) のとき: 現在のバッテリー残量では、フルパワーモードを使っても処理能力が足りません。これより前にバッテリーを温存せずに多く消費していたとしても、バッテリーを増やす手段は存在しないため、どのようにしてもこのタスクをクリアすることは不可能です。したがって、この時点で -1 を出力して終了します。

このように、各タスクに対して「省エネモードが使えるなら使い、使えないならフルパワーモードを使う（使えなければ不可能）」という選択を前から順に行うだけで、自動的に最適な手順（フルパワーモードの使用回数が最小となる手順）が決まります。

具体例

\(N=3, M=10, A=5\)、各タスクの必要処理能力が \(H = [4, 8, 3]\) の場合：

1. 1つ目のタスク（\(H_1 = 4\)）: \(H_1 \le A\) (\(4 \le 5\)) なので、省エネモードを選択。バッテリー \(p = 10\) のまま。
2. 2つ目のタスク（\(H_2 = 8\)）: \(H_2 > A\) (\(8 > 5\)) なので、フルパワーモードを選択。 \(p \ge H_2\) (\(10 \ge 8\)) なのでクリア可能。バッテリーは \(p = \lfloor 10/2 \rfloor = 5\) になり、使用回数は \(1\) に。
3. 3つ目のタスク（\(H_3 = 3\)）: \(H_3 \le A\) (\(3 \le 5\)) なので、省エネモードを選択。バッテリー \(p = 5\) のまま。

すべてのタスクを完了でき、フルパワーモードの使用回数の最小値は 1 となります。

アルゴリズム

1. バッテリー残量を表す変数 \(p\) を \(M\) で、フルパワーモードの使用回数を表す変数 \(ans\) を \(0\) で初期化します。
2. \(i = 1, 2, \ldots, N\) について、以下の処理を順番に行います。
   • \(H_i > A\) の場合：
     • \(p < H_i\) ならば、クリア不可能なので -1 を出力して即座に終了します。
     • そうでなければ、フルパワーモードを使用します。\(p \leftarrow \lfloor p / 2 \rfloor\) と更新し、\(ans\) を \(1\) 増やします。
   • \(H_i \le A\) の場合：
     • 省エネモードを使用します。\(p\) や \(ans\) は変化しません。
3. すべてのタスクを無事に処理し終えたら、最終的な \(ans\) の値を出力します。

計算量

• 時間計算量: \(O(N)\) タスクの配列を前から順に \(1\) 回走査するだけです。各タスクに対する判定やバッテリーの更新は \(O(1)\) の定数時間で行えるため、全体の計算量は \(N\) に比例します。制約の \(N \le 3 \times 10^5\) に対しても十分高速に動作します。
• 空間計算量: \(O(N)\) 入力されたタスクの必要処理能力 \(H\) を配列（リスト）に格納するために必要なメモリ量です。

実装のポイント

• 整数の型（他言語での注意点）: 入力される \(M, A, H_i\) は最大で \(10^{18}\) と非常に大きな値になります。Pythonでは自動的に多倍長整数が扱われるためオーバーフローの心配はありませんが、C++などの言語を使用する場合は、64ビット整数型（long long など）を使用する必要があります。

• 高速な入出力: Pythonで \(N = 3 \times 10^5\) 規模の入力を扱う場合、input() を愚直に繰り返すと実行時間制限（TL）に間に合わない可能性があります。sys.stdin.read().split() を用いて入力を一度にすべて読み込むことで、入出力のボトルネックを解消できます。

  ソースコード

import sys


def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    A = int(input_data[2])

    p = M
    ans = 0

    # 各タスクの処理
    for i in range(N):
        h = int(input_data[3 + i])
        if h > A:
            if p < h:
                print(-1)
                return
            p //= 2
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

---

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