さらっと書くのが難しい。
https://atcoder.jp/contests/arc108/tasks/arc108_e
問題
1~Nの順列となっている数列Aが与えられる。
以下の手順で、いくつかの要素に印をつける。
- まだ印のついていない要素のうち、新規に印をつけたとき、印をつけた全要素がLISとなるようなものを選択の候補とする。
- 上記候補が1個以上ある場合、どれかを等確率で1つ選択し、実際に印を付ける。
- 候補がなければ終了。
印を付けた要素の数の期待値を求めよ。
解法
Aの先頭にA[0]=0、末尾にA[N+1]=N+1を番兵としておいておく。
f(L,R) := A[L]とA[R]に印が付いている場合、その間の要素で追加できる印の数の期待値
とする。f(0,N+1)が求める値である。
f(L,R)を求める場合、L<M<RであるMのうちA[L]<A[M]<A[R]であるMが次の印の候補となる。
そのようなMがk通りある場合、
f(L,R) = 1 + ave(f(L,M)+f(M,R))
となるので、f(L,R)をメモ化再帰すればO(N^3)で解ける。
ただO(N^3)だとTLEするのでもう少し高速化が必要。
A[R]の小さい順にRを総当たりし、対応するLを総当たりすることを考える。
f(L,*)やf(*,R)の区間和を取れるBITを作っておくと平均を取る作業がO(logN)で済むので全体でO(N^2*logN)に抑えることができる。
int N; int A[2020],B[2020]; ll dp[2020][2020]; const ll mo=1000000007; template<class V, int ME> class BIT_mod { public: V bit[1<<ME]; BIT_mod(){ZERO(bit);}; V operator()(int e) {ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;} void add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}} }; BIT_mod<ll,12> S[2020]; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i+1]; B[A[i+1]]=i+1; } A[N+1]=B[N+1]=N+1; FOR(i,N+2) { k=B[i]; BIT_mod<ll,12> num; for(j=i-1;j>=0;j--) { x=B[j]; int n=num(k-1)-num(x); if(n>0) { dp[x][k]+=(2*mo+S[x](k-1)-S[x](x)+S[k](k-1)-S[k](x))%mo; dp[x][k]=(dp[x][k]*modpow(n)+1)%mo; S[x].add(k,dp[x][k]); S[k].add(x,dp[x][k]); } num.add(x,1); } } cout<<dp[0][N+1]<<endl; }
まとめ
言われてみるとオーソドックス。