0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

トキはモンスターと戦っています。

モンスターの体力は H です。

トキは N 種類の魔法が使え、 i 番目の魔法を使うと、モンスターの体力を A_i 減らすことができますが、トキの魔力を B_i 消耗します。

同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を 0 以下にすればトキの勝ちです。

トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。

2.制約

1 ≤ H ≤ 10⁴
1 ≤ N ≤ 10³
1 ≤ A_i ≤ 10⁴
1 ≤ B_i ≤ 10⁴
入力中のすべての値は整数である。

3.入力例

入力

出力

4.初見の感想

とりあえずMP効率のよい魔法をたくさん使って、HPが小さくなってきたらどの魔法使うか考え始める方針を最初に思いつきました(貪欲法的な感じ)
効率良いけどMPを大幅に使う魔法を２回使ってMP大幅に使うより、多少効率悪い魔法でも同じくHPを綺麗に削りきることができればMP効率が良いパターンが存在する
上の損得の分岐点を単純に見つけるのは非常に難しい
そもそもNが10³制約なので、いつもと違う感じがする

5.学びポイント

「体力Nを削り切るのに、最小何MPいるか」という値を繰り返し計算で求める
繰り返し計算なのでDP(動的計画法)が使える
計算量が許せば、全探索的な手法が最強ということを体現しています
実は個数制限なしナップサック問題だった

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long H = long.Parse(input[0]);
        long N = long.Parse(input[1]);
        //DPの初期化
        long[] DP = new long[H + 1];
        DP[0] = 0;
        for(int i = 1; i <= H; i++) { DP[i] = long.MaxValue; }
        //各魔法ごとにDPで体力Nを削り切るのに、最小何MPいるかの表を埋める
        for(int i = 0; i < N; i++)
        {
            input = Console.ReadLine().Split();
            long a = int.Parse(input[0]);
            long b = int.Parse(input[1]);
            for(int j = 0; j < H; j++)
            {
                //魔法を使った時のMPを計算し比較
                if (DP[j] == long.MaxValue) continue;
                int k = (int)Math.Min(j + a, H);
                DP[k] = Math.Min(DP[k], DP[j] + b);
            }
        }
        Console.WriteLine(DP[H]);
    }
}

7.最後に

この問題解けないの、悔しい…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 153 E - Crested Ibis vs Monster