かっつのメモ帳

主に競プロ　時々日記

Educational Codeforces Round 21 E. Selling Souvenirs

DP

リンク

https://codeforces.com/contest/808/problem/E

問題概要

ナップサック問題

ただ制約が特殊

1 \leqq N \leqq 10\  ^5　 1 \leqq M \leqq 10\  ^5

1 \leqq v \leqq 3　 1 \leqq c \leqq 10\  ^9

解法

い　つ　も　の　dp[i]:iの重さを持つ時の価値の最大値,というDPは計算量がO(NM)になってしまい間に合わない。

明らかに怪しい制約があるのでそれを生かす方向性で考える。

これと似た問題をAtCoderで前やったなぁと思ったけどその問題を思い出せず・・・

思い出しました　D - Simple Knapsack

 

v=1,v=2,v=3となるものを選ぶ個数をそれぞれ,a,b,c個とすると、 a+2b+3c \leqq Mを満たせば良く、このうち変数を2個固定させれば残りの1個は取れるだけ貪欲に取るのが最善になる。

dp[i]:i以下の重さを詰めた時の価値の最大値、その時のa,bの値

としてdp配列の情報を持たせてあげればいつものようなDPをすることによって遷移させていくことが出来る。

実装

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

pair<ll,pair<int,int>> dp[310000];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m; cin >> n >> m;
	vector<ll> w[3];
	vector<ll> cnt(n+1,0);
	for(int i=0;i<n;i++){
		int a,b; cin >> a >> b;
		w[a-1].push_back(b);
	}
	for(int i=0;i<3;i++){
		sort(w[i].rbegin(),w[i].rend());
		if(i==2){
			for(int j=0;j<w[i].size();j++){
				cnt[j+1]=cnt[j]+w[i][j];
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=m;i++){
		dp[i]=dp[i-1];
		int a=dp[i-1].second.first;
		if(a<w[0].size()&&dp[i-1].first+w[0][a]>dp[i].first){
			dp[i].first=dp[i-1].first+w[0][a];
			dp[i].second.first++;
		}
		if(i>1){
			int b=dp[i-2].second.second;
			if(b<w[1].size()&&dp[i-2].first+w[1][b]>dp[i].first){
				dp[i]=dp[i-2];
				dp[i].first=dp[i-2].first+w[1][b];
				dp[i].second.second++;
			}
		}
		ans=max(ans,dp[i].first+cnt[min((int)w[2].size(),(m-dp[i].second.first-dp[i].second.second*2)/3)]);
	}
	ans=max(ans,cnt[min((int)w[2].size(),m/3)]);
	cout << ans << endl;
	return 0;
}

感想

こういうDPバグらせずに一発で書けるの偉いな、と思った（自分に甘い）

 

追記(2020/1/5)

dp[i]から向かう遷移先としてdp[i+1],dp[i+2]として良いのか、という正当性の議論があった。

Educational Codeforces Round 21 — Editorial - Codeforces

多分解説としては一番これがわかりやすい

 

一応当時のTLの様子も貼っておきます。

 

 

  • この追記をした思い立ち