C++で全モンスターを倒すために必要な爆弾の最小投下回数を求めるアルゴリズム

問題概要

2つの配列 X と H(どちらも N 個の要素を持つ)、および2つの整数 D と A が与えられます。この問題では、銀狐が N 匹のモンスターと戦うという設定です。モンスターたちは一列に並んでおり、i 番目のモンスターの座標は X[i]、体力は H[i] です。

銀狐は爆弾を使って攻撃することができます。座標 x の位置に爆弾を落とすと、x − D から x + D の範囲内にいるすべてのモンスターにダメージを与え、それぞれの体力が A 減少します。すべてのモンスターの体力が 0 以下になった時点で銀狐の勝利となります。目標は、勝利するために必要な爆弾の最小使用回数を求めることです。

入力例

例えば、D = 3、A = 2、X = [1, 5, 9]、H = [2, 4, 2] という入力の場合、出力は 2 になります。その理由は以下の通りです。

• まず座標 4 に爆弾を落とすと、体力は [0, 2, 2] になります。
• 次に座標 6 に爆弾を落とすと、すべての体力が [0, 0, 0] になり、全滅させることができます。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

1. モンスターの座標と体力をペアとして管理し、座標順にソートします。
2. 差分配列 q を使って、これまでに投下した爆弾による累積ダメージを効率的に記録します。
3. 各モンスターについて、累積ダメージを差し引いた残り体力を計算します。すでに体力が 0 以下ならスキップします。
4. 残り体力を倒すのに必要な爆弾の回数 p を計算し(切り上げ除算)、答えに加算します。
5. 二分探索を用いて、現在の爆弾の射程(x + 2D)に含まれる最後のモンスターの位置を見つけ、差分配列を更新して範囲へのダメージを反映します。

大きなサイズの配列 q を定義
座標 x と体力 h のペア配列を定義
n := X のサイズ
d := D
a := A
i := 1 から n まで繰り返す:
    num[i].x := X[i - 1]
    num[i].h := H[i - 1]
配列 num をソート
sum := 0
i := 1 から n まで繰り返す:
    q[i] := q[i] + q[i - 1]
    num[i].h := num[i].h - q[i] * a
    もし num[i].h <= 0 なら:
        次の反復へスキップ
    p := (num[i].h が a で割り切れるなら num[i].h / a、そうでなければ num[i].h / a + 1)
    tmp := num[i].x + 2 * d
    sum := sum + p
    q[i] := q[i] + p
    l := i、r := n
    l < r の間繰り返す:
        mid := (l + r + 1) / 2
        もし num[mid].x <= tmp なら:
            l := mid
        そうでなければ:
            r := mid - 1
    q[l + 1] -= p
sum を返す

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

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

const int maxn = 2e5 + 20;
int n;
int d, a, q[maxn];
struct node{
    int x, h;
    bool operator<(const node& a) const{
        return x < a.x;
    }
} num[maxn];
int solve(int D, int A, vector<int> X, vector<int> H){
    n = X.size();
    d = D;
    a = A;
    for (int i = 1; i <= n; i++){
        num[i].x = X[i - 1];
        num[i].h = H[i - 1];
    }
    sort(num + 1, num + n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++){
        q[i] += q[i - 1];
        num[i].h -= q[i] * a;
        if (num[i].h <= 0)
            continue;
        int p = (num[i].h % a == 0 ? num[i].h / a : num[i].h / a + 1);
        int tmp = num[i].x + 2 * d;
        sum += p;
        q[i] += p;
        int l = i, r = n;
        while (l < r){
            int mid = (l + r + 1) >> 1;
            if (num[mid].x <= tmp)
                l = mid;
            else
                r = mid - 1;
        }
        q[l + 1] -= p;
    }
    return sum;
}
int main(){
    int D = 3;
    int A = 2;
    vector<int> X = { 1, 5, 9 };
    vector<int> H = { 2, 4, 2 };
    cout << solve(D, A, X, H) << endl;
}

入力

3, 2, { 1, 5, 9 }, { 2, 4, 2 }

出力

2

まとめ

このアルゴリズムは、差分配列と二分探索を組み合わせることで、各爆弾の影響範囲へのダメージ適用を O(log N) で処理します。全体の計算量は O(N log N) となり、N が大きい場合でも高速に動作します。貪欲法の考え方に基づき、各モンスターを左から順に処理しながら、その位置で必要なだけ爆弾を投下し、射程内の右側のモンスターにも同時にダメージを与えることで、爆弾の使用回数を最小化しています。