C,Dで時間をかけすぎたため、本番解法はわかったのに数分間に合わず…。
http://codeforces.com/contest/593/problem/E
問題
H*Wのグリッドがある。
プレイヤーは初期状態で(1,1)にいる。
時刻1ごとに、プレイヤーはその位置にとどまるか隣接マスに移動できる。
ただし時間経過に伴い途中ネコが登場する場合がある。その場合そのマスにいることはできない。
以下のクエリQ個に答えよ。各クエリの時刻は昇順である。
- 時刻tに座標(x,y)に到達するような移動経路の組み合わせ数を答えよ。
- 時刻tに座標(x,y)にネコが登場する。
- 時刻tに座標(x,y)にいたネコが去る。
解法
H*Wは高々20と小さい。
各位置にいる組み合わせ数をベクトルで表現し、時刻1枚の状態遷移を行列で表現して、行列乗算を用いて組み合わせ数を高速に用いていくだけ。
途中クエリにより猫が増減するが、その都度は処理する行列の要素を変えていこう。
int W,H,Q; ll mo=1000000007; const int MAT=20; struct Vec { ll v[MAT]; }; struct Mat { ll v[MAT][MAT]; }; Mat mulmat(Mat& a,Mat& b,int n=MAT) { int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) r.v[x][y] += (a.v[x][z]*b.v[z][y]) % mo; FOR(x,n) FOR(y,n) r.v[x][y]%=mo; return r; } Mat powmat(ll p,Mat a,int n=MAT) { int i,x,y; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(i,n) r.v[i][i]=1; while(p) { if(p%2) r=mulmat(r,a,n); a=mulmat(a,a,n); p>>=1; } return r; } Vec mulmatvec(Mat& a,Vec& b,int n=MAT) { int x,y,z; Vec r; FOR(x,n) r.v[x]=0; FOR(x,n) FOR(y,n) (r.v[x] += a.v[x][y]*b.v[y]) %= mo; return r; } Mat G; Vec V; int is[20][20]; int id(int y,int x) { return y*W+x;} void setup() { int y,x; ZERO(G.v); FOR(y,H) FOR(x,W) if(is[y][x]==0) { G.v[id(y,x)][id(y,x)]=1; if(y) G.v[id(y,x)][id(y-1,x)]=1; if(x) G.v[id(y,x)][id(y,x-1)]=1; if(y<H-1) G.v[id(y,x)][id(y+1,x)]=1; if(x<W-1) G.v[id(y,x)][id(y,x+1)]=1; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>Q; setup(); V.v[0]=1; ll cur=1; while(Q--) { ll t; cin>>i>>y>>x>>t; y--; x--; auto GG=powmat(t-cur,G,H*W); V=mulmatvec(GG,V,H*W); if(i==1) { cout<<V.v[id(y,x)]<<endl; } else if(i==2 || i==3) { is[y][x]^=1; V.v[id(y,x)]=0; setup(); } cur=t; } }
まとめ
Dよりだいぶ楽でない?
なんでDの方が解いてる人多いんだ。