TopCoderOpen 2021 Regional Qualification Round1 : Div1 Hard AlmostOptimalBST

問題文の理解がややこしい。
https://community.topcoder.com/stat?c=problem_statement&pm=17113&rd=18769

問題

(1～N)のPermutationを、順に探索二分木に入れることを考える。

• 探索二分木が最悪ケース最適とは、値を探すときの探索ノード数の最大値が、N要素の探索二分木のうち最小であるものを差す。
• 探索二分木が平均ケース最適とは、値を探すときの探索ノード数の平均値が、N要素の探索二分木のうち最小であるものを差す。

正整数Nが与えられる。
探索二分木に値を入れる順番N!のうち、

• 最悪ケース最適であって平均ケース最適でないもの
• 平均ケース最適であって最悪ケース最適でないもの

はそれぞれ何通りか。

解法

N要素の探索二分木を作る場合、最小の高さをHとする。

• 最悪ケース最適は、葉までの距離の最大値がHであるものを意味する。
• 平均ケース最適は、葉までの距離の最大値と最小値の差が1以下であることを示す。

明らかに平均ケース最適なら最悪ケース最適なので、「平均ケース最適であって最悪ケース最適でないもの」は0通りである。
あとは「最悪ケース最適であって平均ケース最適でないもの」を考える。
Nが(2^k)-1の形の時、最悪ケース最適も平均ケース最適もいずれも完全二分木の場合だけなので、その差は0である。

それ以外のケースを考える。
「最悪ケース最適であって平均ケース最適でないもの」は「葉までの距離の最大値がHで、最小値がH-2以下」なものを数え上げればよい。
言い換えると、「葉までの距離の最大値がHなもの」から、「葉までの距離の最大値がHで、最小値がH-1」なものを引こう。

前者はO(N^2*log N)、後者はO(N^2)でdpで求めることができる。

const ll mo=1000000007;
int D[4096];

static const int N_=4020;
static ll C_[N_][N_];

ll dp[4040][13];

class AlmostOptimalBST {
	public:
	vector <int> count(int N) {
		int i,j;
		D[1]=1;
		for(i=2;i<=4000;i++) D[i]=D[i/2]+1;
		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;

		ZERO(dp);
		dp[0][0]=1;
		for(i=1;i<=N;i++) {
			if((i&(i+1))==0) {
				dp[i][0]=dp[i/2][0]*dp[i/2][0]%mo*C_[i-1][(i-1)/2]%mo;
			}
			else {
				for(int L=0;L<=i-1;L++) {
					int R=i-1-L;
					ll p=C_[L+R][L];
					
					if(max(D[L],D[R])+1!=D[i]) continue;
					if(D[L]==D[R]) {
						(dp[i][0]+=dp[L][0]*dp[R][0]%mo*p)%=mo;
						(dp[i][1]+=dp[L][1]*dp[R][0]%mo*p)%=mo;
						(dp[i][1]+=dp[L][0]*dp[R][1]%mo*p)%=mo;
						(dp[i][1]+=dp[L][1]*dp[R][1]%mo*p)%=mo;
					}
					else {
						int x=max(L,R);
						int y=min(L,R);
						if(D[x]==D[y]+1) {
							(dp[i][1]+=(dp[x][0]+dp[x][1])*dp[y][0]%mo*p)%=mo;
						}
					}
					
					
				}
			}
		}
		ll AC=dp[N][0]+dp[N][1];
		ZERO(dp);
		dp[0][0]=1;
		for(i=1;i<=N;i++) {
			for(int L=0;L<=i-1;L++) {
				int R=i-1-L;
				ll p=C_[L+R][L];
				ll s=0;
				for(int x=0;x<12;x++) {
					(s+=dp[R][x])%=mo;
					(dp[i][x+1]+=dp[L][x]*s%mo*p)%=mo;
				}
				s=0;
				for(int x=0;x<12;x++) {
					if(x) (s+=dp[L][x-1])%=mo;
					(dp[i][x+1]+=dp[R][x]*s%mo*p)%=mo;
				}
			}
		}
		
		ll ret=dp[N][D[N]];
		
		return {(int)((ret+mo-AC%mo)%mo),0};
		
	}
}

まとめ

本番出てたら解けてたかな…。解法は思いついても、実装間に合ってるか微妙。