kmjp's blog

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

TopCoder SRM 778: Div1 Medium CollectingCoins

ゴリ押し嘘解法で解いてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=15944&rd=17805

問題

N個の機械がある。
各機械iは、毎日最大1枚のコインを出すことができ、その価値はV[i]である。
ただし同じ機械を連日使うことができず、連続するD[i]日に1日はコインを出さない日がなければならない。
また、それとは別に、連続するK日に1日は全機械コインを出さない日を設けなければならない。

M日で得られるコインの総価値の最大値を求めよ。

解法

後者の条件、すなわちP日間のうちP日目を全機械止める日、とすると、残り(P-1)日で出せるコインの最大枚数は各機械で確定する。
f(P)をその時の価値とする。
また、それを複数回組み合わせて計Q日間で出せるコインの価値の最大値をg(Q)とする。

g(Q)は、合計がQとなる数列L[j]におけるf(L[i])の総和の最大値となる。
また、求めたいのはg(M+1)である。

さて以下はゴリ押し嘘解法。
Mはとても大きい場合、基本的にほとんどは1日当たりの価値(f(x)/x)が最大となるx日周期でf(x)を獲得していくのが賢いはず。
そこで、g(1)~g(K^2)程度まで愚直にdpで求め、余った日付をx日単位で区切ることにしよう。xは1~Kまで総当たりすればよい。

この解法はO(K^3)かかるが、1.8sぐらいで何とか間に合う。
公式解法は、g(Q)をg(Q/2-x)とg(Q/2+x)でおよそ半々に分割していくメモ化再帰のようだ。

ll V[1010];
ll dp[1010101];
class CollectingCoins {
	public:
	long long maxValue(int m, int k, vector <int> v, vector <int> d) {
		int N=v.size();
		int i,j;
		m++;
		
		for(i=1;i<k;i++) {
			V[i+1]=0;
			FOR(j,N) {
				int num=i/d[j]*(d[j]-1)+i%d[j];
				V[i+1]+=num*v[j];
			}
		}
		
		ZERO(dp);
		for(i=1;i<=k;i++) dp[i]=V[i];
		for(i=1;i<=1000000;i++) {
			for(j=2;j<=k;j++) dp[i+j]=max(dp[i+j],dp[i]+dp[j]);
		}
		ll ma=0;
		for(i=2;i<=k;i++) {
			int cur=m%i;
			int lef=(m-cur)/i;
			while(cur<=1000000 && cur<=m) {
				ma=max(ma,dp[cur]+1LL*lef*dp[i]);
				cur+=i;
				lef--;
			}
		}
		
		return ma;
		
	}
}

まとめ

SRMのサーバはスペックに差があるのか、テストのたびに1.1s~1.8sぐらいで揺れる気がする…。