SRM 520 Div2 1000pt: SRMSystemTestPhase

TopCoder

問題概要

システムテスト終了時の順位とそれぞれ何を解いたかの表が与えられる。各問題の正当な結果の組み合わせが何通りあるか求める問題。ただし、順位は(通った問題の数、-撃墜された問題の数)で辞書順に定める。参加者はN(<50)名。

考えたこと

  • とりあえずスコアを 4*通った問題 + (3 - 撃墜された数) とすればDiv1 500pt とほとんど同じ問題になる。
  • 数字もスコアも小さいので累積和なんてケチケチしたものを使う必要がないので、ただただひたすら愚直にDPする。
  • あるスコアの取り方が何通りあるか求めるときは、解いた問題の量とキーにしてやればよい(この問題はeasyとかhardの間に違いがないから情報量落とせる)。

修正したコード

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

typedef long long int64;

const int MAX_N = 50;
const int64 MOD = 1000000007;

int64 dp[MAX_N + 1][4 * 4];
int64 pat[4][4 * 4];

struct SRMSystemTestPhase {

	int countWays(vector <string> description) {
		const int N = description.size();

		//階乗の計算
		int64 fact[10];
		fact[0] = 1;
		for(int i=1; i<10; i++){
			fact[i] = ( i * fact[i-1] ) % MOD;
		}

		//前処理
		for(int submit=0; submit<=3; submit++){
			for(int fail=0; fail<=3; fail++){
				for(int challenged=0; challenged<=3; challenged++){
					for(int passed=0; passed<=3; passed++){
						if(fail + challenged + passed == submit){

							int score = passed * 4 + ( 3 - challenged );

							pat[submit][score] = ( pat[submit][score] + (fact[submit] / (fact[fail] * fact[challenged] * fact[passed])) ) % MOD;
						}
					}
				}
			}
		}


		//メインソルバ。DP
		dp[0][15] = 1;
		for(int i=0; i<N; i++){
			int solved = 0;
			for(int k=0; k<3; k++)if(description[i][k] == 'Y'){
				solved++;
			}

			for(int j=0; j<16; j++){
				int64 add = 0;
				for(int k=j; k<16; k++){
					add = ( add + dp[i][k] ) % MOD;
				}
				add = (add * pat[solved][j]) % MOD;
				dp[i+1][j] = (dp[i+1][j] + add) % MOD;
			}
		}

		int64 ret = 0;
		for(int i=0; i<16; i++){
			ret = ( ret + dp[N][i] ) % MOD;
		}
		return ret;
	}

};