TopCoder SRM 841 : Div1 Medium InTheLead

こちらも何気に最多得点なのよね。
https://community.topcoder.com/stat?c=problem_statement&pm=17881

問題

3人で問題を解きあった。
時間経過とともにそれぞれ解いた問題が増えて行き、最終的にi番の人はS[i]問の問題を解いた。
また、同時に2名以上が問題を解いた瞬間はないものとする。

解いた問題数が同着1位の状態で、自分がさらに1問問題を解いて単独1位になったとき、リードを取ったと呼ぶ。
i番の人がリードを取った回数がL[i]とする。

数列S,Lを満たすような、3人の問題の解いた順は何通りか。

解法

X=max(S)とする。
3人の解いた問題数と、これまでのリード取得回数を状態に持てば、O(X^6)のDPないしメモ化再帰は容易に思いつく。
しかしX^6個の配列はMLEするので、何らかの工夫が必要。

以下の2つの方法がある。

• sum(L)≦Xでなければならない。そのため、3名をリード回数降順で並べると、2人目はX/2以下、3人目はX/3以下のリード回数までしか許容されない。
  • こうすると作る配列のサイズを1/6にすることができ、MLEを回避できる。
• 状態遷移において、各値は高々1しか増加しない。
  • そのため、状態数6個に関するループのうち、一番外側のループは常にインクリメント前後の値を持てばよいと考え、X^5のサイズの配列を2面もって交互に使いまわせばよい。

以下のコードは前者。

const ll mo=1000000007;

int dp[25][25][25][25][13][9];
vector<int> S,L;
class InTheLead {
	public:
	
	int hoge(int s0,int s1,int s2,int l0,int l1,int l2) {
		if(s0>S[0]||s1>S[1]||s2>S[2]) return 0;
		if(l0>L[0]||l1>L[1]||l2>L[2]) return 0;
		if(s0==S[0]&&s1==S[1]&&s2==S[2]) return (l0==L[0])&&(l1==L[1])&&(l2==L[2]);
		if(dp[s0][s1][s2][l0][l1][l2]>=0) return dp[s0][s1][s2][l0][l1][l2];
		
		ll ret=0;
		ret+=hoge(s0+1,s1,s2,l0+(s0==max(s1,s2)),l1,l2);
		ret+=hoge(s0,s1+1,s2,l0,l1+(s1==max(s0,s2)),l2);
		ret+=hoge(s0,s1,s2+1,l0,l1,l2+(s2==max(s0,s1)));
		
		return dp[s0][s1][s2][l0][l1][l2]=ret%mo;
		
	}
	
	int count(vector <int> solved, vector <int> lead) {
		
		if(lead[0]+lead[1]+lead[2]>24) return 0;
		MINUS(dp);
		S=solved;
		L=lead;
		int x,y;
		FOR(y,3) FOR(x,y) if(L[x]<L[y]) swap(L[x],L[y]),swap(S[x],S[y]);
		
		return hoge(0,0,0,0,0,0);
	}
}

まとめ

難しいのはMLEに収めるところだけのような気もするが、何をしたい問題だったのだろう…。