久々に時間通り参加、途中離脱。でもEは時間あっても思いつけてなさそうだった。
https://yukicoder.me/problems/no/801
問題
N階建のビルがあり、プレイヤーは初期状態で1階にいる。
このビルにはM個のエレベーターがあり、それぞれL[i]~R[i]階の間を運航する。
プレイヤーは、自身のいる階にエレベータがあるとき、どれかを選択して乗り込み、そのエレベーターの運行範囲のいずれかで降りる。
(エレベーターが無いときは移動しない)
K回上記処理を行うときの移動経路は何通りか。
なお、同じ階の移動を行う場合でもエレベーターが異なれば経路は異なるとみなす。
解法
f(n,k) := n回エレベータに載った状態で、k階にいるような経路の組み合わせ
とする。
今(n+1)回目の移動でi番のエレベータを使うとする。
その場合、移動元の組み合わせはsum(f(n,L[i])~f(n,R[i]))であり、その値がf(n+1,L[i])~f(n+1,R[i])に加算される。
前者のsumの処理も、後者の範囲加算も累積和を使えば1回O(N+M)で行えるので、全体でO((N+M)K)で解ける。
int N,M,K; int L[3030],R[3030]; ll mo=1000000007; ll from[3030]; ll to[3030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; FOR(i,M) cin>>L[i]>>R[i]; from[1]=1; FOR(i,K) { ZERO(to); FOR(x,N+1) if(x) (from[x]+=from[x-1])%=mo; FOR(x,M) { ll sum=(from[R[x]]-from[L[x]-1]+mo)%mo; (to[L[x]]+=sum)%=mo; (to[R[x]+1]+=mo-sum)%=mo; } FOR(x,N+1) (to[x+1]+=to[x])%=mo; swap(from,to); } cout<<from[N]<<endl; }
まとめ
ここまでは順調でした。