kmjp's blog

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

AtCoder ARC #212 : E - Drop Min

ARC

こちらも手間取ったけど解けて良かった。
https://atcoder.jp/contests/arc212/tasks/arc212_e

問題

1～NのPermutation Pが与えられる。
ここに以下の処理を(N-1)回繰り返し、整数列Aを作る。

  • 連続する２要素を選び、うち小さい方の値をPから削除して間を詰めるとともに、その値をAの末尾に追加する。

こうして構築できるAは何通りか。

解法

dp(L,R) := (前提として、P[L-1]またはP[R+1]の少なくとも片方はmax(P[L...R])以上であるとしたとき)P[L...R]から構築できるAは何通りか。

Pの最大値P[x]=Nを考えると、P[0...(x-1)]とP[(x+1)...(N-1)]はそれぞれ独立に考えることができるので、その解はC(N-1,x) * dp(0,x-1) * dp(x+1,N-1) となる。あとはこのdp(L,R)を考える。

区間[L,R]の長さが１以下の場合、dp(L,R)は明らかに1。
それ以外の場合、P[L...R]の最大値をP[M]=max(P[L...R])とする。
P[M]をAに加えることができるのは、P[L-1]が存在してかつP[L...(M-1)]を削除した後か、P[R+1]が存在してかつP[(M+1)....R]を消した後である。
よって、dp(L,M-1)*dp(M+1,R)に、P[L..(M-1)]、P[M]、P[(M+1)...R]の計(R-L+1)要素の並べ方のうちP[M]が消えるタイミングが適切な並べ方を掛けたものがdp(L,R)となる。

int N;
int P[202020],R[202020];
const ll mo=998244353;
int A[202020],B[202020];

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;
}

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<20> st;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll hoge(int L,int R) {
	if(L+1>=R) return 1;
	int ma=st.getval(L,R).second;
	ll a=hoge(L,ma);
	ll b=hoge(ma+1,R);
	ll ret=0;
	if(L==0) {
		ret=comb(R-L,R-ma);
	}
	else if(R==N) {
		ret=comb(R-L,ma+1-L);
	}
	else {
		ret=comb(R-L,ma+1-L)+comb(R-L,R-ma)-comb(R-L-1,ma-L)+mo;
	}
	ret=ret*a%mo*b%mo;
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		R[P[i]]=i;
		st.update(i,P[i]);
	}
	
	x=R[N-1];
	ll a=hoge(0,x);
	ll b=hoge(x+1,N);
	ll ret=a*b%mo*comb(N-1,x)%mo;
	
	cout<<ret<<endl;
}

まとめ

途中別解法でしばらく頑張ってしまい、Fに時間が残せなかった…。