TLE対応に手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=17124&rd=18774
問題
車N台分のスペースが円形に並んでいる駐車場がある。
そこにN人の人が車を止めることを考える。
各人、最初に止めようとする位置が決まっているとする。
そこが空いていればそこに止めるし、埋まっていたら時計回りに回って隣のスペースに止めようとする。
最終的に空きスペースがあるまで時計回りに回る。
N人が最初に止めようとする位置の組み合わせはN^N通り考えられる。
その際、「埋まっていたら」の条件がちょうどB回発生するのは何通りか。
解法
まずこの問題を考える上で、止める順番は気にしなくてよい。
i番目の人とj番目の人が同じ位置に止めようとしたとして、どちらが先でどちらが後でも、「埋まっていたら」の条件の発生回数の合計は一緒である。
そこで、以降は順番を無視して、その位置に止めようとする人が何人いたかだけを考えてよい。
あとは以下を考える。
f(i,c,n,s,z) := (N-1)番目の位置に止めたくて止められない人がi人いたとき、0番目以降n番目まで止めようとする人数を定めたとき、n番目から溢れた人がc人で、ここまで「埋まっていたら」の条件が発生した回数がs回で、かつc=0だったことがあるかどうかを示す真偽値がzであるときの、組み合わせの数
とする。
「(N-1)番目の位置に止めたくて止められない人がi人いたとき」を前提として処理を回すので、実際(N-1)番目の位置まで処理をしたとき、i人があふれていないといけない。
なので解はf(i,i,N-1,B,True)の総和となる。
zの有無について、仮に全員がバラバラの位置に止めようとした場合、本来「埋まっていたら」は1回も発生しないはずなのだが、i＞0のケースを考えると「埋まっていたら」がi*N回発生してしまう。
これは不自然である。
実際は、最初に止めようとする位置がどのような状態であっても、どこかでc=0となる位置が存在するので、そこだけ重複なく数えるようにする。
なお、この問題はBが微妙に小さく設定されている。
状態の数が多く、ループ回数が非常にかさむため、この問題は愚直に処理するとTLEする。
Bが小さいことを利用し、早めにループを抜けるようにして極力ループ回数を抑えよう。
ll from[2][21][51][202]; ll to[2][21][51][202]; const ll mo=1000000007; static const int N_=102; static ll C_[N_][N_]; int fix[51][51]; class ParkingSequences { public: int count(int N, int B) { int i,j; FOR(i,N_) C_[i][0]=C_[i][i]=1; for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo; FOR(i,50) { for(j=1;j<=50;j++) { fix[i][j]=fix[i][j-1]+max(0,(i-j)); } } ll ret=0; for(i=0;i<=min(N-1,20);i++) { ZERO(from); from[0][i][N][0]=1; FOR(j,N) { ZERO(to); for(int NZ=0;NZ<=1;NZ++) { for(int C=0;C<=20;C++) { for(int S=0;S+fix[C][N-j]<=B;S++) { for(int L=0;L<=N;L++) if(from[NZ][C][L][S]) { for(int add=(C==0?1:0);add<=L&&S+fix[C+add][N-j]<=B;add++) { (to[NZ|(C+add-1==0)][C+add-1][L-add][S+(C+add-1)]+=from[NZ][C][L][S]*C_[L][add])%=mo; } } } } } swap(from,to); } ret+=from[1][i][0][B]; } return ret%mo; } }
まとめ
本番出てたらTLEしてたわ。
