yukicoder : No.3230 Mutual Corresponding System

想定解とは違った。
https://yukicoder.me/problems/no/3230

問題

N人の人が、各人M通の手紙を他全員に出し合う。

• 各人iは、1通目の手紙を時刻T[i]に出す
• 人iが出した手紙が人jに届くには、時間A[i][j]がかかる。
• 各人iが(m+1)通目の手紙を全員に送るのは、m通目の手紙を出した後、かつ他人からのm通目の手紙をすべて受け取ったタイミングである。

各人がM通目の手紙を受け取る時刻を求めよ。

解法

想定解は行列累乗だが、違う方法でも解ける。
O(N^2)通目程度まで愚直にシミュレーションする。
そのうち、各人の受け取る時刻の差が一致するタイミングを求めたら、周期性がわかるのでそこからM通目を受け取る時間を求めよう。

int N;
ll M;
ll T[10101][101];
ll A[101][101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>T[0][i];
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	
	map<vector<ll>,int> memo;
	
	FOR(i,10101) {
		FOR(y,N) FOR(x,N) T[i+1][x]=max(T[i+1][x],T[i][y]+A[y][x]);
		
		if(i+1==M) {
			FOR(x,N) cout<<T[i+1][x]<<" ";
			cout<<endl;
			return;
		}
		
		vector<ll> V;
		FOR(x,N) V.push_back(T[i+1][x]-T[i+1][0]);
		if(memo.count(V)) {
			int a=memo[V];
			int cur=i+1;
			ll loop=(M-a)/(cur-a);
			ll add=(T[cur][0]-T[a][0])*loop;
			int dif=(M-a)%(cur-a)+a;
			FOR(x,N) cout<<T[dif][x]+add<<" ";
			cout<<endl;
			return;
		}
		memo[V]=i+1;
		
	}
	assert(0);
	
}

まとめ

行列累乗も最初思いついたけど、maxの扱いが思いつかなくて周期性に行っちゃったんだよな。