SRM520 Div2 Hard(1000) SRMSystemTestPhase

SRMSystemTestPhase

解いた問題の数をp、チャレンジされた問題の数をcとして、score=3p-c+3とすると、scoreの降順に並ぶのは何通りかという問題になる。i番目のコーダーのscoreがjになるようなi番目までのコーダーの結果は何通りかを覚えておいて動的計画法。

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

class SRMSystemTestPhase{public:
int countWays( vector <string> description )
{
    enum { X, passed, failed, challenged };
    const int M = 1000000007;
    int N = (int)description.size();

    long long T[50][13] = {{0}};

    for ( int i=0; i<N; i++ )
    {
        int p[3];
        for ( p[0]=0; p[0]<4; p[0]++ )
        for ( p[1]=0; p[1]<4; p[1]++ )
        for ( p[2]=0; p[2]<4; p[2]++ )
        {
            bool f = true;
            int s = 3;      //  3*passed - challenged + 3
            for ( int j=0; j<3; j++ )
            {
                if ( description[i][j]=='Y' && p[j]==X  ||
                     description[i][j]=='N' && p[j]!=X )
                    f = false;
                if ( p[j]==passed ) s += 3;
                if ( p[j]==challenged ) s--;
            }
            
            if ( f )
            {
                if ( i == 0 )
                    T[i][s]++;
                else
                    for ( int j=s; j<=12; j++ )
                        T[i][s] += T[i-1][j];
                T[i][s] %= M;
            }
        }
    }
    
    long long ans = 0;
    for ( int i=0; i<=12; i++ )
        ans += T[N-1][i];

    return (int)(ans%M);
}};