概要

\(N\) 個のタスクを順番に処理する際、省エネモードでは処理能力が足りないタスクに対してのみフルパワーモードを使わざるを得ないため、その回数を数えつつ、バッテリーが足りるかを判定する問題です。

考察

重要な気づき

1. 省エネモードで処理できるタスク（\(H_i \leq A\)）：わざわざフルパワーモードを使う必要がありません。フルパワーモードを使うとバッテリーが半減するため、将来のためにバッテリーを温存すべきです。

2. 省エネモードで処理できないタスク（\(H_i > A\)）：フルパワーモードを使うしかありません。このとき、現在のバッテリー残量 \(p\) が \(H_i\) 以上でなければ、そのタスクは完了不可能です。

貪欲法の正当性

フルパワーモードの使用回数を最小化するには、「フルパワーモードを使わざるを得ないタスクでのみ使う」のが最適です。理由は以下の通りです：

• \(H_i \leq A\) のタスクでフルパワーモードを使っても、タスクは完了できますがバッテリーが無駄に減ります。
• \(H_i > A\) のタスクでは省エネモードでは処理能力が足りないため、必ずフルパワーモードを使わなければなりません。

したがって、「フルパワーモードを使う回数」は \(H_i > A\) であるタスクの個数に等しく、それが実現可能かどうかだけを確認すればよいです。

アルゴリズム

1. タスクを \(1\) 番目から順番に見ていく。
2. \(H_i \leq A\) ならば省エネモードを使う。バッテリーは変化しない。
3. \(H_i > A\) ならばフルパワーモードを使う必要がある：
   • 現在のバッテリー残量が \(H_i\) 未満なら、タスク完了不可能なので -1 を出力して終了。
   • そうでなければ、フルパワーモードを使用し、バッテリーを \(\lfloor \text{battery} / 2 \rfloor\) に更新。カウントを \(1\) 増やす。
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\) の格納分

実装のポイント

• バッテリーの半減は battery >> 1（右ビットシフト）で実装できます。これは \(\lfloor \text{battery} / 2 \rfloor\) と等価です。

• \(M\) や \(H_i\) が最大 \(10^{18}\) と非常に大きいですが、Python は多倍長整数を扱えるためオーバーフローの心配はありません。

• フルパワーモードを使うたびにバッテリーが半減するため、最大でも約 \(60\) 回（\(\log_2(10^{18}) \approx 60\)）しかフルパワーモードを使えません。\(H_i > A\) のタスクがそれ以上あると、バッテリーが \(0\) になり完了不可能になります。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, M, A = map(int, input().split())
    H = list(map(int, input().split()))
    
    battery = M
    count = 0
    
    for i in range(N):
        if H[i] > A:
            if battery < H[i]:
                print(-1)
                return
            count += 1
            battery = battery >> 1
    
    print(count)

main()

---

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