kmjp's blog

競技プログラミング参加記です

Code Festival Team Relay 2018 : J - 健康診断

こっちは普通に自力で解けました。
https://beta.atcoder.jp/contests/cf18-relay-open/tasks/relay2018_j

問題

狼と狐がN日にわたり健康診断を行う。
i日目に健康診断を希望する狼・狐はそれぞれW[i]、F[i]である。
1日に健康診断を行える数は上限がないが、1日につき狼と狐のいずれかしか健康診断を行えない。
希望日に健康診断を行えない狼・狐は最寄の健康診断を行える日に健康診断を行う。
その際、d日希望日からずれた日に健康診断を行うと1匹あたりd不満度が増す。

各日の健康診断を行う種族を最適に設定した場合、不満度の総和の最小値を答えよ。

解法

dp(d, t) := d日目までの健康診断予定が確定しており、(d+1)目が種族tの健康診断を行う予定の場合の、d日目までに受診希望する狼・狐の不満度の総和の最小値
上記を考える。
dp(d,t)が確定している場合、種族tが(d+1)~e日目に受診するとすると
dp(e,tと反対の種族) = dp(d,t) + ((d+1)~e日目に受診予定のtと反対の種族の不満度の総和)
となる。
最後の項は、(d+1)~(d+e)/2日目の受診予定の物はd日目、((d+e)/2+1)~e日目の受診予定の物は(e+1)日目に受診すると考えると、引数や不満度の累積和を前処理していくことで、このDPは1回O(1)で行える。

int N;
ll A[3030][2];
ll SA[3030][2];
ll TA[3030][2];
ll dp[3030][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,2) {
			cin>>A[i][j];
			SA[i][j]=(i?SA[i-1][j]:0)+A[i][j];
			TA[i][j]=(i?TA[i-1][j]:0)+i*A[i][j];
		}
		FOR(j,2) dp[i][j]=SA[i][j]*(i+1)-TA[i][j];
	}
	ll ret=1LL<<60;
	FOR(i,N-1) {
		for(j=i+1;j<N-1;j++) {
			ll co=0;
			x=(i+1+j)/2;
			FOR(y,2) dp[j][y]=min(dp[j][y],dp[i][y^1]+(TA[x][y]-TA[i][y]-i*(SA[x][y]-SA[i][y]))+((j+1)*(SA[j][y]-SA[x][y])-(TA[j][y]-TA[x][y])));
			
		}
		
		FOR(y,2) ret=min(ret,dp[i][y^1]+(TA[N-1][y]-TA[i][y])-i*(SA[N-1][y]-SA[i][y]));
	}
	cout<<ret<<endl;
}

まとめ

なんか今回狼・狐とかバス停とかどこから出てきたかわからない謎設定が多いね。