Indeed Prime CodeSprint : Hat merchant

これは運の良い。
https://www.hackerrank.com/contests/indeed-prime-codesprint/challenges/hats

問題

N種類の帽子を容積Kの鞄に入れて運びたい。

各帽子は、重ねることで2個目以降の容積を減らすことができる。
i番目の種類の帽子はS[i]個あり、1個当たりの価値がX[i]である。
その帽子を1個運ぶにはA[i]の容積を必要とするが、2個目以降は1個あたりB[i]で済む。

鞄に詰め込める帽子の価値の総和を最大化せよ。

解法

以下のように状態を持ってDPする。
dp[i][k] := i番目までの帽子を合計容積kだけ詰めたときの価値の最大値

• B[i]=0の場合
  • 2個目以降は何個積んでも一緒なので、選択肢は1個も詰めないかS[i]個全部詰めるかである。
  • よってdp[i][k] = max(dp[i-1][k], dp[i-1][k-A[i]] + X[i]*S[i])
• B[i]＞0の場合
  • 以下のDPになるのは容易に想像がつく。
  • dp[i][k] = max(dp[i-1][k], dp[i-1][k-A[i]] + X[i], dp[i-1][k-A[i]-B[i]] + X[i]*2, ... , dp[i-1][k-A[i]-k*B[i]] + X[i]*(1+k)], ... , dp[i-1][k-A[i]-S[i]*B[i]] + X[i]*(1+S[i])])
  • 問題はmaxの式の中にO(S[i])個も式があり、まともに計算しては間に合わないことである。
  • ただこのような形式の式を解く手段はつい最近登場済み。容積が1個目だけA[i]で2個目以降B[i]という点が少しややこしいが、うまく処理していこう。
  • yukicoder : No.317 辺の追加 - kmjp's blog
  • なお、上記記事のように最小値を求めるのにsetを使うとTLEする。蟻本にあるdequeを用いたスライド最小値テクを使おう。

int N,K;
ll X,S,A,B;
ll from[5050],to[5050];
deque<pair<ll,ll>> Q[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K+1) from[i]=-1;
	from[0]=0;
	
	while(N--) {
		cin>>X>>S>>A>>B;
		if(B==0) {
			FOR(i,K+1) {
				to[i]=from[i];
				if(i-A>=0) to[i]=max(to[i],from[i-A]+S*X);
			}
		}
		else {
			FOR(i,B) Q[i].clear();
			FOR(i,K+1) {
				x=i%B;
				if(i>=A && from[i-A]>=0) {
					ll v=from[i-A]-(i-A)/B*X;
					while(Q[x].size() && Q[x].back().first<=v) Q[x].pop_back();
					Q[x].push_back({from[i-A]-(i-A)/B*X,i-A});
				}
				while(Q[x].size() && Q[x].front().second<=i-A-B*S) Q[x].pop_front();
				to[i]=from[i];
				if(Q[x].size()) {
					auto r=Q[x].front();
					to[i]=max(to[i],from[r.second]+(1+(i-A-r.second)/B)*X);
				}
			}
		}
		swap(to,from);
	}
	
	cout<<*max_element(from,from+K+1)<<endl;
}

まとめ

直前にyukicoder No.317及び、他の解説でスライド最小値への言及を見てなかったら今回TLE回避できなかったわ…。