CODE FESTIVAL 2018 Final : I - Homework

こちらの方がGより簡単だった。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_i

問題

N個の問題がある。
各問題を解くのにかかる時間A[i]が与えられる。各時間は2の累乗であることが保証される。
また、各問題の得点B[i]が与えられる。
同時に解くことのできる問題が1問であるとき、計K点得るのにかかる最短時間を求めよ。

解法

二分探索で解く。
今時刻Tで解けるかどうか考えるとき、2進数表記で下の桁から見ていくことにする。
下から(0-originで)d桁目を判定するとき、ちょうど時間(2^d)で解ける問題群の得点をソートして持っておこう。
ここでTにおいて2^dのbitが立っている場合、問題群のうち得点最多の物を解くこととし、問題群から取り除く。
次は2^(d+1)以上の値を見ていくことになるので、(2^d)以下の時間で解けるものはそんな細かい単位で持っていても意味がない。
そこで上から順に２つずつ足しこみ、「時間(2^(d+1))で解ける問題群の得点」として表現していこう。

int N;
ll K;
vector<ll> V[51];

ll ok(ll v) {
	vector<ll> C;
	
	int i;
	ll tot=0;
	FOR(i,50) {
		FORR(v,V[i]) C.push_back(v);
		sort(ALL(C));
		if((v&(1LL<<i)) && C.size()) {
			tot+=C.back();
			C.pop_back();
		}
		vector<ll> C2;
		while(C.size()>=2) {
			C2.push_back(C[C.size()-1]+C[C.size()-2]);
			C.pop_back();
			C.pop_back();
		}
		if(C.size()) C2.push_back(C[0]);
		swap(C,C2);
	}
	return tot;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x>>y;
		V[x].push_back(y);
	}
	
	ll mi=1LL<<50;
	for(i=49;i>=0;i--) if(ok(mi-(1LL<<i))>=K) mi-=1LL<<i;
	cout<<mi<<endl;
	
}

まとめ

これは割とすんなり思いつけた。