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; } };