SRM520 Div1 Medium(500) SRMIntermissionPhase

SRMIntermissionPhase

動的計画法。

まずは、問題の正解状況および合計点数ごとに、各問題の点数が何通りかを求める。例えば、W[6][i]をEasyとMediumを解いてi点になる場合の数、W[7][j]をEasyとMediumとHardを解いてj点になる場合の数とすると、

が成り立つ。ただし、添え字が負の場合には0とする。

T[i][j]をi番目の人がj点となるようなi番目までの人の点数の割り当ての場合の数とすると、

が成り立つ。ここで、P=points[0]+points[1]+points[2]、wはi番目の人の正解状況。

このままではどちらの計算もO(P²)だけど、どちらの和も差分計算が可能で、O(P)にできる。

#include <string>
#include <vector>
using namespace std;

int s2i( string s )
{
    int r = 0;
    for ( int i=0; i<3; i++ )
        r += s[i]=='Y' ? 1<<i : 0;
    return r;
}

class SRMIntermissionPhase{public:
int countWays( vector <int> points, vector <string> description )
{
    const long long M = 1000000007;
    int P = points[0]+points[1]+points[2];
    int n = (int)description.size();

    vector<long long> W[8];
    W[0].resize(P+1);
    W[0][0] = 1;
    for ( int i=1; i<8; i++ )
    {
        int l;  //  立っている最左ビット
        for ( l=2; (i>>l&1)==0; l-- )
            ;
        W[i].resize(P+1);   //  W[i][j] = Σ[1≦k≦points[l]] W[i^1<<l][j-k]
        W[i][0] = 0;
        for ( int j=1; j<=P; j++ )
            W[i][j] = W[i][j-1]
                    + W[i^1<<l][j-1]
                    - ( j-points[l]-1>=0 ? W[i^1<<l][j-points[l]-1] : 0 );
    }

    vector<long long> T = W[s2i(description[0])];

    for ( int i=1; i<n; i++ )
    {
        int w = s2i(description[i]);

        vector<long long> S = T;
        T = vector<long long>(P+1);     //  T[i] = W[w][i] Σ[i<j] S[j]
        
        long long s = 0;
        for ( int j=P; j>=0; j-- )
        {
            T[j] = s*W[w][j]%M;
            s += S[j];
            s %= M;
        }
    }

    long long ans = 0;
    for ( int i=0; i<=P; i++ )
        ans += T[i],
        ans %= M;

    return (int)ans;
}};