CodeTON Round 2 : E. Count Seconds

出来がいまいちだった回。
https://codeforces.com/contest/1704/problem/E

問題

N点M辺のDAGを成すグラフが与えられる。
なお、出次数が0の点は1つだけである。

各点には非負整数値が設定されている。

毎秒、以下の手順を行うとする。

• 正整数値が設定された点の設定値をデクリメントし、辺が差す先の各点の設定値をインクリメントする。
• この作業は全点同時に行う。

全点の設定値が0になるまで何秒かかるか。

解法

まず最初にN秒ほど愚直にシミュレートしよう。
そうすると、DAG上自身より前に来る点の設定値が正なのに、自身の設定値が0というケースはなくなる。

その後、0以外の設定値を持つ点のうち、設定値が最大のものについて、その値が0になるまでの時間愚直にシミュレートする、という手順を繰り返す。

int T,N,M;
int A[1010],B[1010];
vector<int> E[1010],RE[1010];
int in[1010];
int D[1010];
const ll mo=998244353;
int alive[1010];
vector<int> Ds[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
			RE[i].clear();
			in[i]=D[i]=0;
			Ds[i].clear();
		}
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			RE[y-1].push_back(x-1);
			in[x-1]++;
		}
		queue<int> Q;
		FOR(i,N) if(in[i]==0) Q.push(i);
		vector<int> cand;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			Ds[D[x]].push_back(x);
			cand.push_back(x);
			FORR(e,RE[x]) {
				D[e]=max(D[e],D[x]+1);
				if(--in[e]==0) Q.push(e);
			}
		}
		
		ll ret=0;
		//1000ターン回す
		FOR(j,1000) {
			if(*max_element(A,A+N)==0) break;
			ret++;
			FOR(i,N) B[i]=0;
			FOR(i,N) if(A[i]) {
				(B[i]+=A[i]-1);
				FORR(e,E[i]) B[e]++;
			}
			FOR(i,N) A[i]=B[i];
		}
		FOR(i,N) alive[i]=A[i]>0;
		
		while(1) {
			int mi=-1;
			FOR(i,N) if(alive[i]) {
				int ok=1;
				FORR(e,RE[i]) if(alive[e]) ok=0;
				if(ok) {
					if(mi==-1||A[mi]<A[i]) mi=i;
				}
			}
			if(mi==-1) break;
			
			ret+=A[mi];
			FOR(i,N) B[i]=A[i];
			FOR(i,N) if(alive[i]) {
				FORR(e,E[i]) (B[e]+=A[mi])%=mo;
				(B[i]+=mo-A[mi])%=mo;
			}
			swap(A,B);
			alive[mi]=0;
		}
		
		
		
		cout<<ret%mo<<endl;
		
		
	}
}

まとめ

だいぶコード量多くなってしまったな。