[C#][DP] A – コンテスト(Typical DP Contest) を解く [動的計画法]

C# で動的計画法(DP)を解きたい

最近競技プログラミングをやりだして、動的計画法(DP)というアルゴリズムを知りました。練習でいろいろな問題を解いていこうと思います。そして勉強がてら解けた問題の内容を書いていきます。

Typical DP Contest – Typical DP Contest | AtCoder

DPの問題に特化した過去のコンテストがあるのでこれを順に C# で解いてみようと思います。コンテストページは上のリンクから確認できます。

A: コンテスト – Typical DP Contest

A: コンテスト – Typical DP Contest | AtCoder

今回はA問題です。まずは問題文を確認してみます。

問題文

N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。コンテスタントは、この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。

制約

• 1 ≤ N ≤ 100
• 1 ≤ pi ≤ 100

サンプル

入力例

3
2 3 5

2点、3点、5点の問題があり、これらの問題を解いたときの得点パターンは以下の出力例のパターン数になります。

出力例

7

0, 2, 3, 5, 7, 8 10 の7通りです。

• 0 = 0 + 0 + 0
• 2 = 2 + 0 + 0
• 3 = 0 + 3 + 0
• 5 = 2 + 3 + 0
• 7 = 2 + 0 + 5
• 0 = 0 + 3 + 5
• 10 = 2 + 3 + 5

7通りの組み合わせを全部列挙すると上の通りです。問題数が少ないので組み合わせを列挙できますが、数が増えると大変です。

もちろん重複する得点パターンもあります。この例だと5点を得るパターンは複数あり得ます。

考察

単純にすべての組み合わせを全列挙すると、ある問題に正解するか不正解するかの２通り * N問 = 2^N になります。

N=100 の時にはとても計算できない数になります。ということで動的計画法を使います。

まずこの問題で最大の得点ケースはいくつでしょうか。

制約

• 1 ≤ N ≤ 100
• 1 ≤ pi ≤ 100

制約が上記のようになっているので問題が100問あって、全て100点の問題の場合に10000点というパターンが考えられます。入力によらずどんな問題でも最大10000点しかありえません。

次に1問目だけに絞って考えてみます。

入力は以下の通りとします。

3
2 3 5

1問目は2点なのでとりうるパターンは 0点, 2点 のいずれかです。この状態から2問目を解くことを考えてみましょう。

2問目は3点の問題なので3点とるか0点かです。1問目を解いた後の状態で 0点, 2点のパターンしかありえないので、0+0=0点、0+3=3点、2+0=2点、2+3=5点の4パターンになります。

これを得点パターン数をカウントする配列に入れてみます。

配列のインデックス(ヘッダー行)は総得点数を表しています。最大10000点ということが制約からわかっているので要素数は10001個です。ゼロインデックスなので+1が必要です。

1行目のデータは1問目終了時点の得点パターン数をカウントした配列です。0点のパターンと2点のパターンが1通りあり、それ以外の点数はあり得ません。

2行目は2問目終了時点の得点パターン数です。

1行目のデータから2行目のデータを作るには、0点のパターン数を0+0点と0+3点のパターン数があり得て、2点のパターン数を2+0点と2+3点のパターンがあり得るので以下のような遷移で計算します。

こんな感じで求まります。○ の入っている点数があり得るパターンです。問題0問目は初期値で0点に1を入れておきます。

こうすることでN問解いたときの得点のパターン数が求まります。計算量は1問あたり10000件のループを実行するので O(10000*100=10^6) となりTLEの問題もありません。

DPはこんな感じで、「ある状態の答えが前の状態の答えに依存する」ような場合に状態を表す変数をインデックスとして配列にばしばし記録しておくことで効率よく問題を解けるアルゴリズムみたいです。(まだ詳しく理解できてないですが。)

Wikipedia には以下のように書かれてます。

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

動的計画法 – Wikipedia

解答

では C# での実装です。

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var N = int.Parse(Console.ReadLine());
        var P = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        // 初期値として0点のパターンのみ true とする
        var dp = new bool[100 * 100 + 1];
        dp[0] = true;

        // N問分ループ
        for (int i = 0; i < N; i++)
        {
            // i問目終了時の状態
            var nextDP = new bool[dp.Length];

            // 全得点パターンループ
            for (int j = 0; j < dp.Length; j++)
            {
                // j点のパターンがあり得る場合
                if (dp[j])
                {
                    // i問目が不正解の場合
                    nextDP[j] = true;
                    if (j + P[i] < dp.Length)
                    {
                        // i問目が正解の場合
                        nextDP[j + P[i]] = true;
                    }
                }
            }
            // i問目終了の状態に更新
            dp = nextDP;
        }

        // あり得るパターンを数えて出力
        var ans = dp.Count(p => p);
        Console.WriteLine(ans);
    }
}

DPで使う配列をdpという名前で保持します。表のように2次元て配列で保持してもいいですがここでは別変数でループごとに配列の参照を更新する実装にしました。

今回はあり得る得点のパターンを求めたいのでDPの中身はbool値にしています。

dp[0]=true; と初期値を設定するのを忘れないように。

これでACしました。

以上。