kmjp's blog

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

AtCoder ABC #442 (JPRSプログラミングコンテスト2026#1) : G - Lightweight Knapsack

思ったよりコードが長くならなかった。
https://atcoder.jp/contests/abc442/tasks/abc442_g

問題

N種類のアイテムがあり、それぞれの重さ・価値・個数が与えられる。
なお、重さは1,2,3のいずれかである。
重みの総和がCを超えないようにアイテムを選んでナップサックに入れる時、価値の総和の最大値を答えよ。

解法

同じ重さのアイテムであれば、価値が高いものから選ぶとよい。
重さがばらついているが厄介。
そこで、重さ1,2,3のアイテムにおける重さの総和のmod 6を総当たりしよう。
それ以外は重さが6に揃うように同じ重さのアイテムをセットにしていく。

まず、各重さについて上記重さの分だけ確定で価値の高い順にアイテムをナップサックに入れる。
あとは、残ったアイテムを重さ合計が6となるように同じ重さのアイテムを価値の高い順にグループにしよう。
そのうえで、グループの価値の高い順に、詰められるだけナップサックに入れる。

int N,C;
vector<pair<int,int>> W[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>x>>y>>k;
		W[x].push_back({y,k});
	}
	FOR(i,4) {
		W[i].push_back({0,6});
		sort(ALL(W[i]));
		reverse(ALL(W[i]));
	}
	ll ret=0;
	int R[4];
	FOR(R[1],6) FOR(R[2],3) FOR(R[3],2) {
		int LC=C-R[1]-R[2]*2-R[3]*3;
		if(LC<0) continue;
		LC/=6;
		vector<pair<ll,int>> cand;
		ll tot=0;
		for(i=1;i<=3;i++) {
			int r=R[i];
			ll sum=0;
			ll num=0;
			FORR2(a,b,W[i]) {
				int v=b;
				while(r&&v) {
					tot+=a;
					r--,v--;
				}
				if(v==0) continue;
				if(num+v>=6/i) {
					v-=6/i-num;
					sum+=1LL*a*(6/i-num);
					cand.push_back({sum,1});
					num=sum=0;
				}
				else {
					sum+=1LL*a*v;
					num+=v;
					continue;
				}
				cand.push_back({1LL*a*(6/i),v/(6/i)});
				num=v%(6/i);
				sum=1LL*a*num;
			}
		}
		sort(ALL(cand));
		reverse(ALL(cand));
		FORR2(a,b,cand) {
			x=min(LC,b);
			tot+=1LL*a*x;
			LC-=x;
		}
		ret=max(ret,tot);
	}
	cout<<ret<<endl;
	
}

まとめ

余り分を総当たりする、ってのは考えたけどそのあとが詰め切れなかった。