kmjp's blog

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

Codeforces ECR #180 : F. Variables and Operations

こちらもECRのボス問にしてはコードが短い。
https://codeforces.com/contest/2112/problem/F

問題

N要素の整数列Aがあったとする。
ここで、M通りの処理が行える。

各処理は整数(X[i],Y[i],Z[i])で表現され、A[X[i]]=min(A[X[i]],A[Y[i]]+Z[i])とすることを意味する。
その際、処理の順番は任意に変更できるが、各処理は1回ずつしかできないものとする。

以下のクエリに答えよ。
Aの初期値と整数Kが与えられる。
Aの要素を、合計K回までデクリメントできるとする。
その後、どんな順で処理を行っても、A[i]が同じ値のままとなるようにできるか判定せよ。

解法

N点のグラフを考え、点Y[i]→X[i]にコストZ[i]の辺を張る。また、各点vのコストの初期値をA[v]とする。
するとこのグラフにおいて、点x→yに致るパスにおいて、最短ではない経路を、最短経路にするために必要なコストのデクリメント回数がK回以下であれば条件を満たせる。

int N,M;
ll E[555][555];
ll D[555][555];

ll K;
int Q;
ll A[555],ME[555],MD[555],op[555];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) E[x][y]=(x==y)?0:1LL<<40;
	FOR(i,M) {
		cin>>x>>y>>k;
		E[y-1][x-1]=min(E[y-1][x-1],(ll)k);
	}
	FOR(x,N) FOR(y,N) D[x][y]=E[x][y];
	FOR(k,N) FOR(x,N) FOR(y,N) D[x][y]=min(D[x][y],D[x][k]+D[k][y]);
	
	cin>>Q;
	while(Q--) {
		cin>>K;
		FOR(i,N) {
			cin>>A[i];
			ME[i]=MD[i]=A[i];
			op[i]=1LL<<40;
		}
		FOR(x,N) FOR(y,N) {
			//最短路
			MD[y]=min(MD[y],A[x]+D[x][y]);
			//最短ではないかも
			ME[y]=min(ME[y],A[x]+E[x][y]);
		}
		
		// 最短路にするために必要な操作回数
		FOR(x,N) FOR(y,N) if(D[x][y]<E[x][y]) op[y]=min(op[y],A[x]+D[x][y]-(ME[y]-1));
		FOR(x,N) cout<<(op[x]<=K);
		cout<<endl;
	}
}

まとめ

コードは短いんだけど、この考え方は思いつかない。