Good Bye 2014 : F. New Year Shopping

これは自力では解けないな…。
http://codeforces.com/contest/500/problem/F

問題

商店でN個の商品を扱っている。
各商品は購入可能な時間帯が決まっている。ただし購入可能な時間の長さPは等しい。
各商品は価格がC[i]、購入時の満足度がH[i]であり、購入可能な時間帯はT[i]～T[i]-P-1である。

ここで以下のクエリQ個を処理せよ。
各クエリは来店時刻A[i]と所持金B[i]からなる。
時刻A[i]に購入可能な商品のうち、合計金額が所持金B[i]以下で得られる総満足度の最大値を求めよ。
なお、各商品は１クエリで１個しか購入できない。

解法

愚直に解くと、各クエリでO(NB)程度のDPを解く必要があり、TLEする。
そこで、何とか購入可能な時間帯の長さが共通なことを利用したい。

時刻をPごとに分割すると、各商品はどこか１個の時間帯でしか購入開始しないことを利用する。
１回のループで、来店時刻がt=(k*P+1)～(k+1)*Pの範囲のクエリを処理することを考える。

まず、購入開始時刻が(k*P+1)～(k+1)*Pである商品に対し、普通にDPで総購入価格に対する最大満足度を求める。
同時に、時刻t=(k*P)→((k-1)*P+1)と時刻の逆順で、同様にDPで総購入価格に対する最大満足度を求める。

クエリの来店時刻A[i]=k*P+mと表現したとする。
この場合前者のDPの結果から、時刻(k*P+1)～(k*P+m)の間に購入開始となる商品群に対し、購入価格と最大満足度の対応が得られる。
同時に、後者のDPの結果から、時刻(k*P-m+1)～(k*P-1)の間に購入開始となる商品群に対し、購入価格と最大満足度の対応が得られる。
よって所持金B[i]を前者と後者に振り分け、満足度の和を最大化すればよい。

各商品は２回までしかDPの対象とならないので、DPは全体でO(NB)で済む。

int N,P,Q;
int C[5005],H[5005],T[5005];
vector<int> eva[20100];
vector<int> evq[20100];

int A[20100],B[20100];
int dp[2][5005][5005];
int numb[20101],numf[20101];
int ret[20101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,N) cin>>C[i]>>H[i]>>T[i], eva[T[i]].push_back(i);
	cin>>Q;
	FOR(i,Q) cin>>A[i]>>B[i], evq[A[i]].push_back(i);
	
	for(i=1;i<=20000;i+=P) {
		ZERO(dp[0][0]);
		ZERO(dp[1][0]);
		numb[i]=numf[i]=0;
		
		for(x=i-1;x>=i-P+1 && x>=0;x--) {
			int& nm=numb[x];
			nm=numb[x+1];
			ITR(it,eva[x]) {
				FOR(y,5000) dp[0][nm+1][y]=dp[0][nm][y];
				for(y=C[*it];y<=5000;y++) dp[0][nm+1][y]=max(dp[0][nm+1][y],dp[0][nm][y-C[*it]]+H[*it]);
				numb[x]++;
			}
		}
		
		for(x=i;x<i+P && x<=20000;x++) {
			int& nm=numf[x];
			ITR(it,eva[x]) {
				FOR(y,5000) dp[1][nm+1][y]=dp[1][nm][y];
				for(y=C[*it];y<=5000;y++) dp[1][nm+1][y]=max(dp[1][nm+1][y],dp[1][nm][y-C[*it]]+H[*it]);
				nm++;
			}
			numf[x+1]=nm;
		}
		for(x=i;x<i+P;x++) if(x<=20000) {
			ITR(it,evq[x]) {
				FOR(y,B[*it]+1) ret[*it]=max(ret[*it], dp[0][numb[max(0,A[*it]-P+1)]][y]+dp[1][numf[A[*it]]][B[*it]-y]);
			}
		}
	}
	
	FOR(i,Q) _P("%d\n",ret[i]);
}

まとめ

このDPは思いつかないなぁ。