たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】AtCoder Beginner Contest 153 E - Crested Ibis vs Monster

f:id:c_taquna:20200115005201p:plain

ABC153 - E の個数制限なしナップサックDPが実装できなかったのでもし次回出たときは実装できるように、自分なりの考え方をまとめました。

読み直してみたら、自分用のメモレベルの書きなぐりになってましたが、何か少しでも参考になるところがあればと思い公開します。

はじめに

本記事のテーマ

AtCoder Beginner Contest 153 E - Crested Ibis vs Monster を使用した個数制限なしナップサックDPの実装方法の考え方の説明です。

下記記事を参考にC#で実装したので、どうすれば再現性をもたせられるか、実装の構造という観点で考えていきます。

drken1215.hatenablog.com

問題へのリンク

atcoder.jp

参考リンク

ナップサックDPについて qiita.com

個数制限なしナップサックDPについて qiita.com

本題

実装

static void Main(string[] args)
{
    long[] input = Console.ReadLine().Split().Select(long.Parse)
    long H = input[0];
    long N = input[1];
    long[,] DP = new long[N + 10, H + 10];
    long[] A = new long[N];
    long[] B = new long[N];
    for (int i = 0; i < N; i++)
    {
        input = Console.ReadLine().Split().Select(long.Parse).To
        A[i] = input[0];
        B[i] = input[1];
    }
    for (int i = 0; i <= N; i++)
    {
        for (int h = 0; h <= H; h++)
        {
            DP[i, h] = int.MaxValue;
        }
    }
    DP[0, 0] = 0;
    for (int i = 0; i < N; i++)
    {
        for (int h = 0; h <= H; h++)
        {
            DP[i + 1, h] = Math.Min(DP[i + 1, h], DP[i, h]);
            DP[i + 1, Math.Min(h + A[i], H)] = Math.Min(DP[i + 1
        }
    }
    Console.WriteLine(DP[N, H]);
}

実装リンク github.com

実装への考察

ここから、実装を分割してみていきます。

これは、インプットです。特別なことはしていません。

long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
long H = input[0];
long N = input[1];
long[] A = new long[N];
long[] B = new long[N];
for (int i = 0; i < N; i++)
{
    input = Console.ReadLine().Split().Select(long.Parse).ToArray();
    A[i] = input[0];
    B[i] = input[1];
}

DP配列を定義しています。今回、DPの配列が格納するのは、i 種類までの魔法を使用して、モンスターに h のダメージを与える場合の、消費魔力の最小値です。(解答を参考にしたリンク先の言葉を借りました。)

最小値とあるので、直感的に整数の最大値で埋めています。この整数の最大値ですが、今回はlong型の配列にint.MaxValueの値を格納することで、値の増減でオーバーフローすることが無いようにしています。

long[,] DP = new long[N + 10, H + 10];
for (int i = 0; i <= N; i++)
{
    for (int h = 0; h <= H; h++)
    {
        DP[i, h] = int.MaxValue;
    }
}

これは、DPのメイン処理になります。これを更に分割してみていきます。

DP[0, 0] = 0;
for (int i = 0; i < N; i++)
{
    for (int h = 0; h <= H; h++)
    {
        DP[i + 1, h] = Math.Min(DP[i + 1, h], DP[i, h]);
        DP[i + 1, Math.Min(h + A[i], H)] = Math.Min(DP[i + 1, Math.Min(h + A[i], H)], DP[i + 1, h] + B[i]);
    }
}
Console.WriteLine(DP[N, H]);

この初期処理ですが、最初はなぜDP[0, 0]だけを0にしているのかわからなかったので、そういう人は for文でDP[i, 0] = 0にするのが理解しやすくて良いと思います。というのも、意味を考えるとhが0なのであれば、攻撃する必要がないのでコストもかからず0が入る、と考えれるので、最初の列に問題なく0を入れることができるかと思います。

ちなみに、どちらの実装でも問題ありません。どのみち処理の中で最初の列には0が入るので。

// 変更前
DP[0, 0] = 0;

// 変更後
for (int i = 0; i <= N; i++)
{
    DP[i, 0] = 0;
}

ここは2つの処理で成り立っています。

  1. 今みているマスにおいて、i 番目の攻撃を選択しなかった場合とすでに入っている値を比較して小さい方を選択する

  2. 今みているマスからAi進んだマスに格納されている値と、今いるマスにBi足した値を比較して、小さい方を選択する

今回のポイントは配るDPで書いているところだと思います。最初は貰うDPで書こうと思ったのですが、うまくいかず、結果的に配るDPのほうがシンプルに書けました。

アルゴリズムの設計ですが、今いるマスの更新+A[i]すすんだマスの更新をするA[i]進んだ時に、Hを超えていないか調べて超えていたらHの列を更新するようにするというのをループの中でシリアルで処理する方針で実装してます。

今いるマスの他にA[i]進んだ後の処理も同時にしてしまうのも、配るDPであることを考えると直感的に理解できるかと思います。(言語化できてない、、、)

ちなみに、Hを超えないようにするのは、最終的に解答を出力する際に、解答が格納されているマスを固定できる効果があるからかな?と考えました。

// 1
DP[i + 1, h] = Math.Min(DP[i + 1, h], DP[i, h]);

// 2
DP[i + 1, Math.Min(h + A[i], H)] = Math.Min(DP[i + 1, Math.Min(h + A[i], H)], DP[i + 1, h] + B[i]);

感想

まだまだDPに慣れていないですが、今回のABCはEまでとけないと(DPが)緑にいけないことがよく分かる回だったので精進していかないとなと思いました。