Thanks Kosen 2020 : F - 卒業RTA

ABCと同じぐらいの難易度。
https://www.hackerrank.com/contests/thankskosen2020/challenges/challenge-2448

問題

卒業にあたり、M種類の科目群のいずれかであるN種類の講義の単位をそろえたい。
各講義、科目・かかる時間・取得単位数が与えられる。
各科目群iにおいてa[i]以上の単位を取りつつ、総単位数をA以上にするのにかかる日数を求めよ。

解法

Mが小さいので科目ごとに処理する。
科目内では
f(i,u) := i番目までの講義のうち総単位数がuになるときの最短日数
をDPで求める。これは典型的なDPである。
あとは科目間で
g(j,v) := j番目までの科目群のそれぞれの条件を満たしたうえで総単位数がvの時に最短日数
を求めよう。
g(j,v)とf(j+1,u)がわかっていれば、f(j+1,a[j+1])～f(j+1,A)だけ使ってg(j+1,v)を求めていけばよい。

int N,M,A;
int D[11];
vector<pair<int,int>> E[10];

ll from[1010];
ll to[1010];
ll dp[1010];
ll to2[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>A;
	FOR(i,M) cin>>D[i];
	FOR(i,N) {
		cin>>x>>y>>k;
		E[x-1].push_back({y,k});
	}
	
	FOR(i,1010) from[i]=1LL<<60;
	from[0]=0;
	FOR(i,M) {
		FOR(j,1010) dp[j]=1LL<<60;
		dp[0]=0;
		FORR(e,E[i]) {
			for(j=1000;j>=0;j--) dp[min(j+e.second,1000)]=min(dp[min(j+e.second,1000)],dp[j]+e.first);
		}
		FOR(j,1001) to[j]=1LL<<60;
		FOR(x,1001) for(y=D[i];y<=1000;y++) to[min(x+y,1000)]=min(to[min(x+y,1000)],from[x]+dp[y]);
		swap(from,to);
	}
	ll ret=1LL<<60;
	for(i=A;i<=1000;i++) ret=min(ret,from[i]);
	cout<<ret<<endl;
}

まとめ

自分はいつ博士論文書き終わるんだろうな…。