kmjp's blog

競技プログラミング参加記です

CPSCO2019 Session1 : F - Fruits in Season

誤読で時間を浪費した。
https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_f

問題

N個の果物をN日間に1個ずつ食べていく。
i番の果物は元のおいしさがA[i]であり、食べごろがT[i]日目なのでそこから離れた日に食べるとおいしさが1日あたりB[i]減少する。

果物を最適な順で食べる場合、N日間の最低のおいしさの最高値はいくつになるか。

解法

二分探索で解く。
おいしさを定めれば、各果物をそのおいしさ以上で食べられる日の区間が求まるので、区間スケジューリングの要領でN個の区間でN日をカバーできるか判定すればよい。

int N;
ll T[202020];
ll S,A[202020],B[202020];
vector<int> ev[202020];

int ok(ll v) {
	int i;
	FOR(i,N) ev[i].clear();
	FOR(i,N) {
		if(A[i]<v) return 0;
		ll d=(A[i]-v)/B[i];
		ll L=max(T[i]-d,0LL);
		ll R=T[i]+d;
		ev[L].push_back(R);
	}
	
	multiset<int> T;
	FOR(i,N) {
		FORR(e,ev[i]) T.insert(e);
		while(T.size() && *T.begin()<i) return 0;
		if(T.empty()) return 0;
		T.erase(T.begin());
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>T[i]>>A[i]>>B[i];
		T[i]--;
	}
	
	ll ret=-1LL<<30;
	for(i=30;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	cout<<ret<<endl;
}

まとめ

最初おいしさの総和を最大化しようとしちゃった。
それでも500-600ptかな。