DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦 : B - Hawker on Graph

相変わらずタイトルが長め。
https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_b

問題

有向グラフが与えられる。
各辺には整数値が設定されており、移動すると所持金が設定分加算される。
設定値は負の場合もあるが、所持金はマイナスにはならず0になる。

今点SにいてWだけ所持金をもつ。辺に沿ってK回移動したとき、所持金の最大値を求めよ。

解法

所持金マイナス云々がなければ行列累乗に持ち込めるが、そのままではそうはいかない。
辺の設定値を2値(a,b)で表すことにする。(a,b)は、通過前の所持金がwの時max(w+a,b)となることを意味する。
最初の辺の設定値cに対し、2値表現は(c,max(c,0))となる。

この2値表現は、合成(2つの辺を連続してたどる)または最大値(2つの辺のうち都合のいい方の値を取る)の計算が可能である。

• 設定値(a,b)の辺あと設定値(c,d)の辺を通ることは(a+c,max(b+c,d))の辺を1つ通るのと等しい。
• 設定値(a,b)の辺と設定値(c,d)の辺のいずれか都合のいい辺を通ることは(max(a,c),max(b,d))の辺を1つ通るのと等しい。

あとはこの2値表現において行列累乗を考えればよい。

int N,M;
ll W;
int S,K;
pair<ll,ll> D[200][200][32];
pair<ll,ll> from[200][200];
pair<ll,ll> to[200][200];

pair<ll,ll> comp(pair<ll,ll> A,pair<ll,ll> B) {
	if(A.second<-1LL<<59||B.second<-1LL<<59) return {-1LL<<60,-1LL<<60};
	return {A.first+B.first,max(A.second+B.first,B.second)};
}
pair<ll,ll> par(pair<ll,ll> A,pair<ll,ll> B) {
	if(A.second<-1LL<<59) return B;
	if(B.second<-1LL<<59) return A;
	return {max(A.first,B.first),max(A.second,B.second)};
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>W>>S>>K;
	S--;
	FOR(x,N) FOR(y,N) FOR(i,32) D[x][y][i]={-1LL<<60,-1LL<<60};
	FOR(i,M) {
		cin>>x>>y>>r;
		D[x-1][y-1][0]={(ll)r,max((ll)r,0LL)};
	}
	FOR(i,30) {
		FOR(x,N) FOR(y,N) FOR(r,N) D[x][r][i+1]=par(D[x][r][i+1],comp(D[x][y][i],D[y][r][i]));
	}
	
	FOR(x,N) FOR(y,N) from[x][y]={-1LL<<60,-1LL<<60};
	FOR(x,N) from[x][x]={0,0};
	FOR(i,30) if(K&(1<<i)) {
		FOR(x,N) FOR(y,N) to[x][y]={-1LL<<60,-1LL<<60};
		FOR(x,N) FOR(y,N) FOR(r,N) to[x][r]=par(to[x][r],comp(from[x][y],D[y][r][i]));
		swap(from,to);
	}
	
	ll ret=-1LL<<60;
	FOR(x,N) ret=max(ret,max(W+from[S][x].first,from[S][x].second));
	
	if(ret<-1LL<<59) ret=-1;
	cout<<ret<<endl;
	
	
}

まとめ

方針はすぐ立ったけど合成周りの式をすんなり出せず苦戦。