C++で敵を倒すための武器の最小使用回数を求める方法

問題の概要

n個の要素を持つ配列Aと、整数Hが与えられます。ここで、Hは敵の体力（HP）を表します。こちらはn個の武器を持っており、i番目の武器のダメージ力はA[i]です。これらの武器を組み合わせて敵を倒しますが、同じ武器を連続して2回使用することはできません。この制約のもとで、敵を倒すために必要な武器の使用回数の最小値を求めます。

例えば、入力がA = [2, 1, 7]、H = 11の場合を考えてみましょう。このときの出力は3となります。ダメージ7の武器を使用し、続いてダメージ2の武器、そして再びダメージ7の武器を使うことで敵を倒せるからです。

解法のアプローチ

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

sort the array A
n := size of A
x := (A[n - 1] + A[n - 2])
return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]

まず配列Aを昇順にソートします。すると、最も強い武器はA[n-1]、2番目に強い武器はA[n-2]になります。同じ武器を連続で使えないため、最適な戦略は「最強の武器」と「2番目に強い武器」を交互に使い続けることです。このとき、2回の攻撃で与えられる最大ダメージは x = A[n-1] + A[n-2] となります。

H / x * 2 の部分は、完全なペア攻撃（最強＋2番目）を何セット行えるかを表しています。残りの (H mod x + A[n - 1] - 1) / A[n - 1] は、余ったダメージを埋めるために追加で必要な攻撃回数を切り上げ除算で計算する部分です。

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int H){
    sort(A.begin(), A.end());
    int n = A.size();
    int x = (A[n - 1] + A[n - 2]);
    return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1];
}
int main(){
    vector<int> A = { 2, 1, 7 };
    int H = 11;
    cout << solve(A, H) << endl;
}

この実装では、ソートに O(n log n)、その後の計算は定数時間で完了するため、全体として非常に効率的です。

入力例

{ 2, 1, 7 }, 11

出力例

3