yukicoder : No.472 平均順位

すごい遠回りしちゃった…。
http://yukicoder.me/problems/no/472

問題

N個のコンテストがある。
各コンテストは３問からなり、それぞれ正答数に対し何位になるかが与えられる。
全部でP問解いた場合、平均順位の最小値を答えよ。

解法

以下の状態を考え、単純にDPしていけばよい。
ただしFを愚直にメモリ上に２次元テーブルとして持つとMLEするので、直前のコンテスト分だけ覚えて置くなどして高速化する。
F(c, p) := c個目までのコンテストでp問解いたときの順位の合計の最小値

本番は無駄にpriority_queueを使ったりしてしまった(しかも正解しなかった)。

int N,P;
int A[5];
ll from[15050];
ll to[15050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,3*N+1) from[i]=1<<30;
	from[P]=0;
	
	FOR(i,N) {
		FOR(j,3*N+1) to[j]=1<<30;
		cin>>A[0]>>A[1]>>A[2];
		A[3]=1;
		FOR(j,P+1) FOR(x,4) if(j>=x) to[j-x]=min(to[j-x],from[j]+A[x]);
		swap(from,to);
	}
	_P("%.12lf\n",from[0]*1.0/N);
	
}

まとめ

今年のAdvent Calendar Contest、昨年より少し難易度が高い気がする。