ゆるふわ競プロオンサイト #2 : I - pino assort

どこかで開催されてたオンサイトのようです。
https://www.hackerrank.com/contests/yfkpo2/challenges/pino-assort

問題

N人中K人を選ぶ。
各人を選ぶためには、バニラ・アーモンド・チョコそれぞれいくつかのピノを与える必要がある。
ただし、３種類中２個以上必要なのは１種だけで、残り２種は１個固定である。

ピノは１箱にバニラ・アーモンド・チョコがそれぞれ10,7,7個入っている。
K人選ぶのに最小何箱必要か求めよ。

解法

箱が多ければ多いだけ多くの人の要求を満たせるので、箱の数を二分探索しよう。
あとは箱の数を決めたとき、何人の要求を満たせるか考える。
各人最低バニラ・アーモンド・チョコ1個ずつは必要なので、K人選ぶ時点でK個ずつは固定で必要である。
例えばバニラを２個以上要求する人について、その数を昇順にソートして累積和も取っておこう。
そうすると、バニラの数がわかれば最大何人の要求を満たせるか高速に判定できる。
アーモンド・チョコも同様に人数を求めよう。
総和がK人以上ならOK。

int N,K;
vector<int> V[3];

int ok(int val) {
	int num=0;
	ll sum=0;
	FORR(v,V[0]) {
		sum+=v;
		if(sum>val*10-K) break;
		num++;
	}
	sum=0;
	FORR(v,V[1]) {
		sum+=v;
		if(sum>val*7-K) break;
		num++;
	}
	sum=0;
	FORR(v,V[2]) {
		sum+=v;
		if(sum>val*7-K) break;
		num++;
	}
	return num>=K;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>j>>k>>r;
		if(j>1) V[0].push_back(j-1);
		else if(k>1) V[1].push_back(k-1);
		else V[2].push_back(r-1);
	}
	FOR(i,3) sort(ALL(V[i]));
	
	int ret=1<<25;
	for(i=24;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
	cout<<ret<<endl;
}

まとめ

チョコ味派かな。