TopCoder SRM 520 Div2 Hard SRMSystemTestPhase

うーん、あまり面白くない問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11511

問題

各人３問の問題を解き、それぞれSubmit状況と順位が与えられる。
Submitした場合、結果は正答・誤答・撃墜のいずれかである。

各人の順位は以下のように決まる。

• 正答数が多い方が上。
• 正答数が同じなら、撃墜数が少ない方が上。

指定されたSubmit状況を順位を満たすような、各人の正答・誤答・撃墜の組み合わせ数を答えよ。

解法

順位が上の方から正答数と撃墜数を状態としてDPすればよい。

ただし、Submit状況に対して同じ正答数・誤答数・撃墜数は複数通りあるので、その点は事前に考慮しておく。
例えば３問Submitして正答数・誤答数・撃墜数がいずれも１つになるのは６通りある。

ll mo=1000000007;
ll dp[51][4][4];
ll numnum[4][4][4];

class SRMSystemTestPhase {
	public:
	int countWays(vector <string> description) {
		int N,i,x,p,c,p2,c2,y[3];
		int num[51];
		ZERO(numnum);
		numnum[0][0][0]=numnum[1][0][0]=numnum[0][1][0]=numnum[0][0][1]=1;
		numnum[2][0][0]=numnum[0][2][0]=numnum[0][0][2]=1;
		numnum[3][0][0]=numnum[0][3][0]=numnum[0][0][3]=1;
		numnum[1][1][0]=numnum[0][1][1]=numnum[1][0][1]=2;
		numnum[1][2][0]=numnum[2][1][0]=numnum[0][1][2]=numnum[0][2][1]=3;
		numnum[1][0][2]=numnum[2][0][1]=3;
		numnum[1][1][1]=6;
		
		
		N=description.size();
		FOR(i,N) num[i]=(description[i][0]&1)+(description[i][1]&1)+(description[i][2]&1);
		ZERO(dp);
		dp[0][3][0]=1;
		FOR(x,N) {
			FOR(p,4) FOR(c,4) FOR(p2,4) FOR(c2,4) {
				if(p2+c2>num[x]) continue;
				if(dp[x][p][c]==0) continue;
				if(p2>p || (p==p2 && c>c2)) continue;
				dp[x+1][p2][c2] = (dp[x+1][p2][c2]+dp[x][p][c]*numnum[p2][c2][num[x]-p2-c2]) % mo;
			}
		}
		ll ret=0;
		FOR(p,4) FOR(c,4) ret+=dp[N][p][c];
		
		return (int)(ret%mo);
	}
};

まとめ

うーん、何がテーマの問題だったのだろう。