敵を倒すために必要な最小操作回数を求めるC++プログラム

ナイフを武器に敵と戦うアクションゲームを想像してみてください。主人公はナイフで敵を斬ることも、投げつけることもできます。ただし、一度投げたナイフは二度と手元に戻ってきません。i 番目のナイフのダメージ情報は配列 knives に {斬撃ダメージ, 投擲ダメージ} というペアの形式で与えられます。「斬撃(slash)」はそのナイフで敵を切りつけた際に与えるダメージ、「投擲(throw)」はそのナイフを敵に投げた際に与えるダメージです。斬撃は何度でも繰り返し実行できますが、投擲は各ナイフにつき1回しか行えません。

ここで、体力 h を持つ敵が現れます。敵の体力を 0 にして倒すまでに必要な操作回数(斬撃または投擲)の最小値を求めてください。

たとえば、入力が n = 2、h = 11、knives = {{4, 5}, {3, 6}} だったとしましょう。この場合の出力は 2 になります。2本のナイフを両方投げれば、与えられる合計ダメージは 5 + 6 = 11 となり、敵の体力はちょうど 0 になって倒れるためです。

解き方の手順

この問題は貪欲法(greedy)の考え方で効率よく解くことができます。ポイントは次のとおりです。

• まず、すべてのナイフの中で最大の斬撃ダメージ val を求めます。
• 投擲ダメージが val を上回るナイフだけを投げます。それ以外のナイフは、投げても同じ1操作で得られるダメージが最強の斬撃以下になるため、投げる意味がありません。
• 投擲で体力が 0 以下になれば、その時点の操作回数が答えです。
• 体力が残っている場合は、最強のナイフで斬撃を繰り返して削ります。必要な回数は ceil(h / val)(h を val で割った値の切り上げ)です。

これらの手順を疑似コードで表すと、次のようになります。

val := 0
for i := 0 to n-1 do:
   val := max(val, knives[i].first)
sort the array knives
res := 0
for i := 0 to n-1 do:
   if knives[i].second > val then:
      h := h - knives[i].second
      res := res + 1
      if h <= 0 then:
         print(res)
         return
   else:
      break
print(res + ceil(h / val))

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

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

void solve(int n, int h, vector<pair<int, int>> knives){
   int val = 0;
   for(int i = 0; i < n; i++){
      val = max(val, knives[i].first);
   }
   sort(knives.begin(), knives.end());
   int res = 0;
   for(int i = 0; i < n; i++){
      if(knives[i].second > val){
         h -= knives[i].second;
         res++;
         if(h <= 0){
            cout << res << endl;
            return;
         }
      }
      else break;
   }
   cout << (res + ceil(h / (double)val)) << endl;
}
int main() {
   int n = 2, h = 11;
   vector<pair<int, int>> knives = {{4, 5}, {3, 6}};
   solve(n, h, knives);
   return 0;
}

入力

2, 11, {{4, 5}, {3, 6}}

出力

2

計算量について

このアルゴリズムでは、ナイフのソートに O(n log n)、その後の走査に O(n) かかるため、全体の時間計算量は O(n log n) となります。ナイフの本数が多くても高速に動作する、非常に効率的な解法です。