TopCoder SRM 740 Div1 Medium DieDesign

これ想定解２通りありそう。
http://community.topcoder.com/stat?c=problem_statement&pm=15141

問題

　
２人が、N個の面があるサイコロを持っている。
互いにサイコロを振ったとき、目の大きな面を出した側が出すゲームを考える。
　
片方のプレイヤーの各面の目の数が与えられる。
もう片方は、目の総和が等しい範囲で各面の目の数を任意に選べるとき、勝率を最大化できる目の例を示せ。

解法

できるだけ効率よく相手に勝てるようにする方がいいので、最後の１面を除けば、面に振る目の数は0か相手の(いずれかの面+1)の計N+1通りである。
そこで、以下の通りdpを行いそれを復元しよう。
片方のプレイヤーの各面の目の最大値をAとすると、O(A*N^3)となりちょっと危ないが何とか通る。
dp(i,s) := i番目までの面が決まっているとき、残りの面に計sの目を触れるときの勝率の最大値。

まだ、今回はAがさほど大きくないのでこれでよいが、以下のようにするとO(N^4)でAの値に依存しない計算量にできる。
dp(i,x) := i番目までの面が決まっているとき、勝率がx/(N^2)となるような目の総和の最小値

int win[30*5100+1];
int ma[31][30*5100];
int from[31][30*5100];


class DieDesign {
	public:
	vector <int> design(vector <int> P) {
		int i,j,k;
		int N=P.size();
		int S=0;
		FORR(p,P) S+=p;
		
		vector<int> C;
		C.push_back(0);
		FOR(i,30*5002) {
			win[i]=0;
			FORR(p,P) if(p<i) win[i]++;
			if(i && win[i]>win[i-1]) C.push_back(i);
		}
		
		MINUS(from);
		MINUS(ma);
		ma[0][S]=0;
		FOR(i,N-1) FOR(j,S+1) FORR(c,C) if(j>=c) {
			if(ma[i][j]+win[c]>ma[i+1][j-c]) {
				ma[i+1][j-c]=ma[i][j]+win[c];
				from[i+1][j-c]=c;
			}
		}
		
		int be=-1;
		int ca=-1;
		FOR(i,S+1) if(ma[N-1][i]+win[i]>be) be=ma[N-1][i]+win[i], ca=i;
		vector<int> R;
		R.push_back(ca);
		for(i=N-1;i>=1;i--) {
			R.push_back(from[i][ca]);
			ca+=from[i][ca];
		}
		cout<<be<<endl;
		return R;
	}
}

まとめ

本番（計算時間は確認したが）何も考えず前者を取ってしまった。