Top Coder SRM 609 Level3 おさらい

今週末もTop Coderに参戦したが、例のごとく最終問題のみ解けなかったので復習した。

今回はGumiとIaとMayuというボーカロイドが音楽アルバムを作りますという若干Geekyなお題でした。以下のような入力値が与えられた時に、すべての曲が必ず一名以上に歌われるようなアルバムのパターンは何種類あるかという問題です（一つの曲を複数人で歌うのはOK）。

入力値(すべて1から50までの整数)

• S: 全曲数
• gumi: Gumiが歌う曲数
• ia: Iaが歌う曲数
• mayu: Mayuが歌う曲数

出力値

• Int: アルバムのパターン数

例えば(3,1,1,1)だと3C1 * 2C1 * 1C1で6パターンとなります。

各曲に対して、各一名ずつ歌う場合（3パターン）、各二名ずつ歌う場合（3パターン）、三人全員が歌う場合（1パターン）の合計7パターンあります。なので7のS乗回試行して条件を満たすものをカウントすればよいのですが、Sが50の場合には1.798465e+42回ほど試行する事になるので残念ながら僕が死ぬまでには計算が終わらなそうです。

この手の問題はどうやら以下の二種類の方法で解けるようです。

• 場合分けをして数学的に解く
• 動的計画法で解く

前者は場合分けを行ってCombinationを駆使して解く方法、後者は分割統治法とメモ化と呼ばれる手法を使って問題を細分化して同じパターンの部分をキャッシュしながら解く方法です。勿論、数学的に解けた方がエレガントではあるのですが、Top Coderでは動的計画法は必須知識らしく、他の多くの問題に応用可能なようなので今回はこちらで解いてみました。

まずは各項が以下の漸化式で求められるという事に気づく必要があります。こちらは前述の通り各曲に対して7パターン存在するということからも分かると思います。

• f(s, g, i, m) = f(s-1, g-1, i, m) + f(s-1, g, i-1, m)  + f(s-1, g, i, m-1)  + f(s-1, g,-1 i-1, m)  + f(s-1, g-1, i, m-1) +  + f(s-1, g, i-1, m-1)  + f(s-1, g-1, i-1, m-1)
• f(0,0,0,0) = 1

後は、各入力値は正の値であるとか、g+i+m > sであるとかの確認をして、この漸化式を満たして、s/g/i/mのパターンをキャッシュしてあげるようなプログラムを実装すればよいです。

できあがりは以下のようなコードになりました。でも、やっぱこのレベルの問題を30分で完璧に解くのはまだまだ無理だなぁ。あ、ちなみに1000000007で割ってるのは問題文に数値がでかすぎるのでこの値の剰余をとるようにって書いてあったから。

import java.util.*;

public class VocaloidsAndSongs {

    long cache[][][][];
    final long MOD = 1000000007L;

    public int count(int S, int gumi, int ia, int mayu) {

        cache = new long[S + 1][gumi + 1][ia + 1][mayu + 1];

        for (int s = 0; s <= S; s++) {
            for (int g = 0; g <= gumi; g++) {
                for (int i = 0; i <= ia; i++) {
                    for (int m = 0; m <= mayu; m++) {
                        cache[s][g][i][m] = -1L;
                    }
                }
            }
        }
        return (int) dp(S, gumi, ia, mayu);
    }

    private long dp(int s, int g, int i, int m) {

        if (s > (g + i + m)) {
            return 0;
        }

        if (s == 0) {
            if (g == 0 && i == 0 && m == 0) {
                return 1L;
            } else {
                return 0L;
            }
        }

        if (g < 0 || i < 0 || m < 0) {
            return 0L;
        }

        if (cache[s][g][i][m] == -1L) {
            cache[s][g][i][m] = dp(s - 1, g - 1, i, m) +
                    dp(s - 1, g, i - 1, m) +
                    dp(s - 1, g, i, m - 1) +
                    dp(s - 1, g - 1, i - 1, m) +
                    dp(s - 1, g - 1, i, m - 1) +
                    dp(s - 1, g, i - 1, m - 1) +
                    dp(s - 1, g - 1, i - 1, m - 1);

        }

        return cache[s][g][i][m] % MOD;
    }

}