Codeforces Global Round 24 : E. Doremy's Number Line

まぁまぁの出来だった回。
https://codeforces.com/contest/1764/problem/E

問題

N要素の整数列A,Bと正整数Kが与えられる。

整数が並んでおり、初期状態でいずれも未彩色である。
[1,N]の範囲の色Cを任意の順で選び、以下のように彩色する。

• 以下を満たす未彩色の整数Xを1つ選び、色Cで彩色する。
• X≦A[C]または彩色済みの整数YのうちY≦A[C]かつX≦Y+B[C]なものがある。

整数Kを、色1で彩色できるか判定せよ。

解法

ある整数を塗れるなら、より小さな整数も塗れる。
よって、色2～Nを(A[C],B[C])の昇順にソートし、できるだけ大きな番号を塗れるようにシミュレートしていく。

最終的に色1で塗れるか判定しよう。

int T,N;
ll K;
ll A[101010],B[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		vector<pair<ll,ll>> V;
		FOR(i,N) {
			cin>>A[i]>>B[i];
			if(i) V.push_back({A[i],B[i]});
		}
		sort(ALL(V));
		ll cur=-1LL<<60;
		ll cand=0;
		FORR2(a,b,V) {
			cur=max({cur,a,min(cur,a)+b,cand});
			cand=max(cand,a+b);
		}
		if(A[0]>=K||min(cur,A[0])+B[0]>=K) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
	}
}

まとめ

なんか数式が不自然なので、もう少し納得できる設定が欲しかったな。