mayoko’s diary

プロコンとかいろいろ。

SRM 520 div1 med:SRMIntermissionPhase

良いdpの練習問題ですね…(全然サンプルが合わなくて死んだ)

解法

dpの組み合わせです。

全体で参加者が N 人であるとします。
次のような2つのdpっぽいものを考えます。

dp[n][p] = ([n, N]の人の得点のみを気にする場合, n 番目の人が p 以下の得点を取るような場合の数)
ways[n][p] = (n 番目の人が得点 p を取る場合の数)

ways が計算出来たものとして, dp をどうやって計算するのかを考えます。

dp[i][j] は, i 番目の人が j-1 点獲得するか, i 番目の人が j 点獲得して,かつ i+1 番目の人以降が j-1 点以下であるかのいずれかになるので,

dp[i][j] = dp[i][j-1] + ways[i][j] * dp[i+1][j-1]

です。なお,初期条件は仮想的に N+1 人目がいると考えて,この人は -1 点取ったと考えればよいです。よって,

dp[N+1][-1] から dp[N+1][MAXP] を 1 にすればよいです(MAXP は得点の最高値)。

ということで dp の方は ways さえ構成できれば 上手く構成できそうなので今度は ways の構成を考えます。

ノリはさきほどと似ています。各 i について ways を求めていきます。

memo[k][p] = (k番目の問題までで p 点以下をとるような場合の数)

とします。すると,さきほどと同じように

memo[k][p] = memo[k][p-1] + memo[k-1][p-minScore] - memo[k-1][p-maxScore-1]

で漸化式が作れます。これも初期条件がややこしいですが, 3 問の問題番号を(0-index ではなく) 1, 2, 3 で表すと, 0 問目の問題は 0 点である場合の数は 1 であると解釈できるので,

memo[0][a] = 1 (a = 0 〜 MAXP)

とすれば OK のはずです。

ソースコードと微妙に違うじゃん,と思うかもしれませんが, 上で dp[N+1][-1] とか出てきてることからわかるように少し添字を平行移動させないとプログラムできちんと動くようにならないのでそうしています。例えば「0 点を取る場合の数」は memo[k][1] に記録しています。

const int MAXP = 200010;
const int MOD = 1e9+7;
int dp[22][MAXP]; // dp[n][p] : n人目の人が得点p以下を取る場合の数
int ways[22][MAXP];
int memo[4][MAXP];

class SRMIntermissionPhase {
public:
    int countWays(vector <int> points, vector <string> description) {
        int n = description.size();
        memset(dp, 0, sizeof(dp));
        memset(ways, 0, sizeof(ways));
        for (int i = 0; i < n; i++) {
            memset(memo, 0, sizeof(memo));
            for (int j = 1; j < MAXP; j++) memo[0][j] = 1;
            for (int j = 1; j <= 3; j++) {
                int minScore = 0, maxScore = 0;
                if (description[i][j-1] == 'Y') {
                    minScore = 1;
                    maxScore = points[j-1];
                }
                for (int p = 1; p < MAXP; p++) {
                    memo[j][p] = memo[j][p-1];
                    memo[j][p] += memo[j-1][p-minScore];
                    memo[j][p] -= memo[j-1][max(0, p-maxScore-1)];
                    memo[j][p] %= MOD;
                    if (memo[j][p] < 0) memo[j][p] += MOD;
                }
                for (int j = 1; j < MAXP; j++) {
                    ways[i][j] = memo[3][j] - memo[3][j-1];
                    if (ways[i][j] < 0) ways[i][j] += MOD;
                }
            }
        }
        for (int i = 0; i < MAXP; i++) dp[n][i] = 1;
        for (int i = n-1; i >= 0; i--) {
            for (int j = 1; j < MAXP; j++) {
                dp[i][j] = (dp[i][j-1] + (ll)(ways[i][j]) * dp[i+1][j-1]) % MOD;
                dp[i][j] %= MOD;
                if (dp[i][j] < 0) dp[i][j] += MOD;
            }
        }
        return (int)dp[0][MAXP-1];
    }
};