Codeforces ECR #089 : F. Jog Around The Graph

本番はギリギリで解けた。
http://codeforces.com/contest/1366/problem/F

問題

連結無向グラフが与えられる。各辺には重みがついている。
整数Qが与えられる。頂点1から始まる長さが1～Qのパスにおいて、それぞれの辺の重みの総和の最大値の和を求めよ。

解法

パス中で最大の重みの辺に到着したら、あとはその辺を往復するのがベストである。
そこで、各辺について、そこまで最速で到達して、あとはその辺を往復することを考える。
そうすると、そうして作れるパスの重みの総和は、長さLに応じた一次関数として表現できる。

あとは、たくさんの1次関数の最大値を求める問題になるので、Convex Hull Trickで解いていく。

int N,M,Q;
vector<pair<int,int>> E[2020];
ll dp[2020][2020];
const ll mo=1000000007;


template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) {
		return ((__int128)(B.second-C.second)*(B.first-A.first)<=(__int128)(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		if(Q.size() && Q.back().first==a) {
			//aが同じ場合
			if(b<Q.back().second) return; //minの場合
			Q.pop_back();
		}
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(0^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};
ConvexHull<ll> cht;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,2020) FOR(j,2020) dp[i][j]=-1LL<<60;
	dp[0][0]=0;
	FOR(i,2010) {
		FOR(j,N) FORR(e,E[j]) dp[i+1][e.first]=max(dp[i+1][e.first],dp[i][j]+e.second);
	}
	
	ll ret=0;
	for(i=1;i<=min(Q,2010);i++) {
		ll ma=0;
		FOR(j,N) ma=max(ma,dp[i][j]);
		(ret+=ma)%=mo;
	}
	
	vector<pair<ll,ll>> cand;
	FOR(i,N) {
		int ma=0;
		FORR(e,E[i]) ma=max(ma,e.second);
		cand.push_back({ma,dp[2010][i]-2010*ma});
	}
	
	cht.add(cand);
	
	int cur=min(Q,2010);
	while(cur<Q) {
		ll dif=cht.query(cur+1)-cht.query(cur);
		for(i=29;i>=0;i--) {
			ll nc=cur+(1<<i);
			if(nc>Q) continue;
			if(cht.query(nc)-cht.query(cur)==(nc-cur)*dif) {
				ll now=cht.query(cur)%mo;
				(ret+=now*(nc-cur))%=mo;
				(ret+=(nc-cur)*(nc-cur+1)/2%mo*dif)%=mo;
				cur=nc;
			}
		}
	}
	
	
	cout<<ret<<endl;
	
	
}

まとめ

解けて良かった。