TopCoderOpen 2019 Japan Regional : Medium ChangesInTheLead

このイベント自体はどうだったんですかね。
https://community.topcoder.com/stat?c=problem_statement&pm=15636&rd=17637

問題

２つのチームがスポーツの試合を行った。
このスポーツでは、１回で１点点が入る。

あるチームがリーダーであるとは、相手チームより点が高いことを示す。同点ならどちらもリーダーではない。
また、リーダーが入れ替わるとは、どちらかのチームが点を取った結果、最後にリーダーになったのが相手チームだったが、自チームがリーダーになることを示す。

両チームの最終成績はH-Aだった。
リーダーの入れ替わり回数がCであるような得点の遷移は何通りか。

解法

以下の値をDPで愚直に埋めても間に合う。
dp(h,a,c,l) := 今の得点がh-aで、リーダーの入れ替わり回数がc回であり、最後にリーダーだったチームがlであるような組み合わせ

H*A*C*2は32M近く、long long型の配列を取ろうとするとMLEしかねないので注意。

ll mo=1000000007;
int dp[252][252][252][2];

class ChangesInTheLead {
	public:
	int add(int& a,int& b) {
		a+=b;
		if(a>=mo) a-=mo;
		return a;
	}
	int count(int H, int A, int C) {
		
		if(H==0||A==0) return C==0;
		ZERO(dp);
		dp[1][0][0][0]=dp[0][1][0][1]=1;
		int h,a,c;
		FOR(h,H+1) FOR(a,A+1) FOR(c,C+1) {
			if(h<H) {
				add(dp[h+1][a][c][0],dp[h][a][c][0]);
				if(a==h) add(dp[h+1][a][c+1][0],dp[h][a][c][1]);
				else add(dp[h+1][a][c][1],dp[h][a][c][1]);
			}
			if(a<A) {
				add(dp[h][a+1][c][1],dp[h][a][c][1]);
				if(a==h) add(dp[h][a+1][c+1][1],dp[h][a][c][0]);
				else add(dp[h][a+1][c][0],dp[h][a][c][0]);
			}
		}
		
		
		return (dp[H][A][C][0]+dp[H][A][C][1])%mo;
		
	}
}

まとめ

450ptとはいえ、Div1相当にしては簡単な感じ。