概要

ノートパソコンのバッテリー消費を管理しながら、\(N\) 個のタスクを順番に処理する問題です。 フルパワーモードを使用するたびにバッテリー残量が半分になるという性質を利用し、動的計画法（DP）を用いてフルパワーモードの最小使用回数を求めます。

考察

重要な気づき：フルパワーモードを使用できる回数の上限

初期バッテリー残量 \(M\) は最大で \(10^{18}\) と非常に大きな値ですが、フルパワーモードを使用するたびにバッテリー残量は \(\lfloor p/2 \rfloor\) と半分になっていきます。

\(10^{18}\) を 2 で割り続けると、約 60 回でバッテリー残量は 0 になります。 したがって、フルパワーモードを使用できる回数は高々 60 回程度（正確には \(\log_2 M + 1\) 回以下）しかありません。この「状態数が非常に少ない」という性質が、この問題を解くための最大の鍵となります。

なぜ貪欲法では解けないか？

「必要処理能力 \(H_i\) が \(A\) を超えたときだけフルパワーを使う」というような単純な貪欲法では解けません。 なぜなら、現在のタスクを省エネモードでクリアできる場合（\(H_i \le A\)）であっても、将来のより厳しいタスクに備えて、あえて今のうちにフルパワーモードを使っておく（あるいはバッテリーを温存しておく）といった判断が必要になる場合があるからです。

どのタイミングでフルパワーを使うべきかは、先のタスクの必要処理能力に依存するため、すべての可能性を探索する必要があります。

DP（動的計画法）によるアプローチ

フルパワーモードの最大使用回数を \(L\)（\(\approx 60\)）とします。 タスクを 1 番目から順に見ていきながら、以下の情報を管理するDPを考えます。

• dp[k] : 現在までにフルパワーモードをちょうど \(k\) 回使用した状態に到達可能か（true / false）

タスクを進めるごとに、この dp 配列を更新していきます。状態数が \(L \le 60\) と非常に小さいため、タスク数 \(N\) に対しても高速に動作します。

アルゴリズム

1. 前処理

フルパワーモードを \(k\) 回使った後のバッテリー残量を表す配列 \(P\) を作成します。 - P[0] = M から開始し、curr /= 2 を curr > 0 である限り繰り返して配列に追加します。 - 配列のサイズを \(L + 1\) とします（\(P[L] = 0\) となります）。

2. DPの遷移

各タスク \(i = 0, 1, \ldots, N-1\) について、現在の dp から次のタスク終了時の状態 next_dp を遷移させます。 dp[k] が true（到達可能）であるとき、以下の 2 つの選択肢があります。

1. 省エネモードを使用する

   • タスクの必要処理能力が \(A\) 以下（\(H_i \le A\)）であれば、バッテリーを消費せずにクリアできます。
   • このとき、フルパワー使用回数は \(k\) 回のままなので、next_dp[k] = true とします。

2. フルパワーモードを使用する

   • まだバッテリーが残っており（\(k < L\)）、かつ現在のバッテリー残量 \(P[k]\) が \(H_i\) 以上（\(P[k] \ge H_i\)）であれば、フルパワーモードでクリアできます。
   • このとき、フルパワー使用回数は \(k+1\) 回になるので、next_dp[k+1] = true とします。

各タスクの処理が終わるたびに、dp を next_dp で更新します。

3. 答えの出力

すべてのタスクを処理し終えた後、dp[k] が true となっている最小の \(k\)（\(0 \le k \le L\)）が答えとなります。 どの \(k\) に対しても dp[k] が false である場合は、すべてのタスクを完了することは不可能なので -1 を出力します。

計算量

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

  • バッテリーが 0 になるまでの回数 \(L\) は \(\log_2 M\) に比例します（\(M \le 10^{18}\) のとき \(L \le 60\)）。
  • 各タスクに対して、サイズ \(L\) のループを回して遷移を行うため、全体の計算量は \(O(N \log M)\) となります。
  • \(N = 3 \times 10^5\) のとき、全体のループ回数は最大でも約 \(1.8 \times 10^7\) 回であり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N + \log M)\)

  • 入力されたタスクの配列 \(H\) を保持するのに \(O(N)\) のメモリを使用します。
  • DPテーブルは現在の状態と次の状態の 2 世代分（サイズ \(L \approx 60\)）だけ保持すればよいため、DPに必要な空間は \(O(\log M)\) です。

実装のポイント

• データ型: バッテリー残量 \(M\) や必要処理能力 \(H_i\) は最大 \(10^{18}\) に達するため、C++では 64 ビット整数型（long long）を使用する必要があります。

• メモリの節約: DPテーブルを遷移させる際、std::move を使用して next_dp を dp に代入することで、不要なメモリコピーを避けて高速化を図っています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M, A;
    if (!(cin >> N >> M >> A)) return 0;

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

    // P[k] はフルパワーモードを k 回使った後のバッテリー残量
    vector<long long> P;
    long long curr = M;
    P.push_back(curr);
    while (curr > 0) {
        curr /= 2;
        P.push_back(curr);
    }
    int L = P.size() - 1; // P[L] = 0 となる

    // dp[k] : 現在、フルパワーモードを k 回使った状態に到達可能か (0: 不可能, 1: 可能)
    vector<char> dp(L + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < N; ++i) {
        vector<char> next_dp(L + 1, 0);
        long long hi = H[i];
        for (int k = 0; k <= L; ++k) {
            if (!dp[k]) continue;
            // 省エネモードを使用する場合
            if (hi <= A) {
                next_dp[k] = 1;
            }
            // フルパワーモードを使用する場合
            if (k < L && P[k] >= hi) {
                next_dp[k + 1] = 1;
            }
        }
        dp = move(next_dp);
    }

    int ans = -1;
    for (int k = 0; k <= L; ++k) {
        if (dp[k]) {
            ans = k;
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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