TopCoder SRM 376 Div1 Medium MarbleMachine

行列カテゴリを新たに作った。

問題

マーブルを操作する機械がグリッド上に並んでいる。
layout[i][j]が数字kであるとき、(i,j)のマスにはk番の機械があることを意味する。


機械は、機械ごとに定められた動作actions[i]を繰り返す。
actions[i]の最後まできたら、先頭からまた同じ動作を繰り返す。
actions[i]のj文字目が

  • N,S,E,W : それぞれの方向へ、機械のマーブルを送る。グリッドからはみでたマーブルは捨てられる
  • '0'-'9' : マーブルを書かれた数字だけ中央から取ってくる(中央には無限にマーブルがある)


機械の操作は、ターンの最初に、機械の中にあるマーブルに対して行われる。
すなわち、あるターンにおける機械の動作がNで、その機械にマーブルが送られてくるとき、Nに送り出すのは最初においてあった分だけである。


tターン経過した後で、それぞれの機械にあるマーブルのうち、最も多いのはいくつであるか、求めよ。

制約条件

layout[i][j]は数字
actionsの要素数≦10
actions[i]の文字数≦10

方針

操作の周期は最大でgcd{1〜10} = 3600くらい。
なので、3600通りの操作を考えればよい。


一ターンの操作は、行列で表すことができる。
(h*w+1行h*w+1列行列で、右下の成分は常に1)


tの周期の倍数の分だけは繰り返し二乗法を使って計算して、
余りの部分は普通に行列の掛け算によってまとめた操作を求める。

ソースコード

typedef vector<vi> mat;
mat operator*(mat &a,mat &b){
	mat c(a.size(),vi(b[0].size()));
	rep(i,c.size())rep(j,c[0].size())rep(k,a[0].size())
		c[i][j]+=a[i][k]*b[k][j];
	return c;
}
mat pow(mat m,int n){
	mat res(m.size(),vi(m.size()));
	rep(i,m.size())res[i][i]=1;
	for(;n;n/=2){
		if(n&1)res=m*res;
		m=m*m;
	}
	return res;
}
class MarbleMachine {
	public:
	long long maxMarbles(vector <string> layout, vector <string> actions, int t) 
	{
		int h=layout.size(),w=layout[0].size(),N=h*w+1;
		int T=1;
		rep(i,actions.size())
			T=T*actions[i].size()/__gcd(T,(int)actions[i].size());
		
		vector<mat> Ms(T);
		mat M(N,vi(N));
		M[N-1][N-1]=1;
		rep(i,T)Ms[i]=M;
		
		rep(i,h)rep(j,w)rep(k,T){
			char a=actions[layout[i][j]-'0'][k%actions[layout[i][j]-'0'].size()];
			if(isdigit(a))Ms[k][i*w+j][N-1]+=a-'0', Ms[k][i*w+j][i*w+j]=1;
			else if(a=='W'&&j)Ms[k][i*w+j-1][i*w+j]++;
			else if(a=='E'&&j<w-1)Ms[k][i*w+j+1][i*w+j]++;
			else if(a=='N'&&i)Ms[k][(i-1)*w+j][i*w+j]++;
			else if(a=='S'&&i<h-1)Ms[k][(i+1)*w+j][i*w+j]++;
		}
		
		M=mat(N,vi(N));
		rep(i,N)M[i][i]=1;
		rep(i,T)M=Ms[i]*M;
		
		M=pow(M,t/T);
		rep(i,t%T)M=Ms[i]*M;
		
		ll ans=0;
		rep(i,N-1)ans=max(ans,M[i][N-1]);
		return ans;
	}
};