kmjp's blog

競技プログラミング参加記です

AtCoder ARC #108 : E - Random IS

さらっと書くのが難しい。
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;
}

まとめ

言われてみるとオーソドックス。