Codeforces #1026 : Div2 D. Fewer Batteries

妙に簡単だった回。
https://codeforces.com/contest/2110/problem/D

問題

N個の町が並んでいる。
各町iでは、バッテリーがB[i]個置いてあり、その町を通る際、0～B[i]個までのいずれかの個数バッテリーを取得できる。
また、手持ちのバッテリーをすべて充電できる。

加えてM個の道路があり、道路jでは、町S[j]からT[j]に、充電済みのバッテリーをW[i]個使い移動できる。
(そのW[i]個のバッテリーは、空のバッテリーとして手元に残る)。

初期状態で町1にバッテリー0個の状態でいるとき、町Nに至るのに必要な最小の手持ちのバッテリーの個数を求めよ。

解法

解vを二分探索する。
そのうえで、各町に至るバッテリー数の最小/最大値を町番号の小さい順に求めて行こう。
その際、vより多くのバッテリーを持たないようにしていく。

int T,N,M;
ll B[202020];
ll L[202020],R[202020];
vector<pair<int,ll>> E[202020];

int ok(ll v) {
	int i;
	FOR(i,N) L[i]=1LL<<60,R[i]=-1;
	L[0]=R[0]=0;
	
	FOR(i,N) {
		R[i]+=B[i];
		R[i]=min(R[i],v);
		if(L[i]<=R[i]) {
			FORR2(t,w,E[i]) if(R[i]>=w&&w<=v) {
				L[t]=min(L[t],max(w,L[i]));
				R[t]=max(R[t],R[i]);
			}
		}
	}
	return L[N-1]<=R[N-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>B[i];
			E[i].clear();
		}
		FOR(i,M) {
			cin>>x>>y>>k;
			E[x-1].push_back({y-1,k});
		}
		
		if(ok(1LL<<60)==0) {
			cout<<-1<<endl;
		}
		else {
			ll ret=(1LL<<60)-1;
			for(i=59;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
			cout<<ret<<endl;
		}
		
	}
}

まとめ

問題のストーリーに毎回2077年が登場するので、なぜかと思ったらサイバーパンク2077が元ネタだった。