Codeforces #683 Div1 A. Knapsack

Cまでが遅いうえDが解けず大ダメージ。
https://codeforces.com/contest/1446/problem/A

問題

変則的なナップサック問題を考える。
N個の荷物とその重さが与えられる。
荷物のうち一部を選び、重さの合計をCの半分以上C以下にできるか。
できるならその一例を求めよ。

解法

単独でCの半分以上の重さの荷物があれば、それを答えればよい。
そうでない場合、残りの荷物はCの半分未満なので、Cの半分以上になるまでその荷物を選んでいけばよい。
Cの半分未満から、荷物を1つ追加することでいきなりCを超えることはない。

int T;
int N;
ll V;
ll W[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>V;
		vector<ll> A[2];
		ll S=0;
		FOR(i,N) {
			cin>>W[i];
			if(W[i]<(V+1)/2&&S<(V+1)/2) {
				A[0].push_back(i);
				S+=W[i];
			}
			else if(W[i]>=(V+1)/2&&W[i]<=V) {
				A[1].push_back(i);
			}
		}
		
		if(A[1].size()) {
			cout<<1<<endl;
			cout<<A[1][0]+1<<endl;
		}
		else if(S>=(V+1)/2) {
			cout<<A[0].size()<<endl;
			FORR(v,A[0]) cout<<v+1<<" ";
			cout<<endl;
		}
		else {
			cout<<-1<<endl;
		}
		
	}
}

まとめ

ナップサック問題がこの条件だけでさっくり解けるようになるのは面白いな。