問題
$N$ 個のノード（鍵は $1, 2, \ldots, N$）からなる二分探索木（BST）について以下の2問を解け。
- 鍵の挿入順列 $\pi$ を空の BST に順番に挿入した結果の木の高さ（根の深さ = 0）を求めよ。
- $N$ 個のノードからなる BST の形状（構造）の総数を $10^9+7$ で割った余りで求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| $\pi$ | $1$ から $N$ の順列 |
| 時間制限 | 2秒 |
入出力例
入力例 1
7
4 2 6 1 3 5 7出力例 1
3
429挿入順列 [4,2,6,1,3,5,7] による BST の高さ = 3（根4→子2,6→孫1,3,5,7）。7ノードの BST 形状総数 = $C_7 = 429$。
概念図: BST の構造と Catalan 数
ヒント（段階的開示）
ヒント1: 方向性
BST への挿入は決定的（同じ順列 → 同じ木）。高さはシミュレーションで求まる。
形状の総数は $n$ ノードの二分木の個数 = Catalan 数 $C_n = \binom{2n}{n}/(n+1)$。
ヒント2: アプローチ
- BST 高さ: 反復挿入でスタックオーバーフロー回避。各ノードに深さを記録。
- Catalan 数: $C_n = \binom{2n}{n} \cdot (n+1)^{-1} \pmod{10^9+7}$
- mod 逆元: フェルマーの小定理 $a^{-1} \equiv a^{p-2} \pmod{p}$（$p$ 素数）
- 階乗テーブルと逆階乗テーブルを線形前計算で $O(N)$ 構築
ヒント3: コード骨格
MOD = 10**9 + 7
def build_fact(n):
fact = [1] * (n+1)
for i in range(1, n+1): fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (n+1)
inv_fact[n] = pow(fact[n], MOD-2, MOD)
for i in range(n-1, -1, -1): inv_fact[i] = inv_fact[i+1]*(i+1)%MOD
return fact, inv_fact
def catalan(n, fact, inv_fact):
return fact[2*n] * inv_fact[n] % MOD * inv_fact[n+1] % MOD
class Node:
__slots__ = ['key', 'left', 'right', 'depth']
def __init__(self, k, d): self.key=k; self.left=self.right=None; self.depth=d
def bst_height(perm):
root = Node(perm[0], 0); max_depth = 0
for x in perm[1:]:
cur = root
while True:
if x < cur.key:
if cur.left is None:
d = cur.depth+1; cur.left=Node(x,d); max_depth=max(max_depth,d); break
cur = cur.left
else:
if cur.right is None:
d = cur.depth+1; cur.right=Node(x,d); max_depth=max(max_depth,d); break
cur = cur.right
return max_depth模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def build_fact(n):
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i + 1) % MOD
return fact, inv_fact
def catalan(n, fact, inv_fact):
if n < 0: return 0
return fact[2*n] * inv_fact[n] % MOD * inv_fact[n+1] % MOD
class Node:
__slots__ = ['key', 'left', 'right', 'depth']
def __init__(self, k, d):
self.key = k; self.left = self.right = None; self.depth = d
def bst_height(perm):
if not perm: return 0
root = Node(perm[0], 0)
max_depth = 0
for x in perm[1:]:
cur = root
while True:
if x < cur.key:
if cur.left is None:
d = cur.depth + 1
cur.left = Node(x, d)
if d > max_depth: max_depth = d
break
cur = cur.left
else:
if cur.right is None:
d = cur.depth + 1
cur.right = Node(x, d)
if d > max_depth: max_depth = d
break
cur = cur.right
return max_depth
def solve():
N = int(input())
perm = list(map(int, input().split()))
# 問1: BST の高さ
h = bst_height(perm)
# 問2: N ノードの BST 形状総数 = Catalan 数 C_N
fact, inv_fact = build_fact(2 * N + 5)
cn = catalan(N, fact, inv_fact)
print(h)
print(cn)
solve()
Step-by-Step 解説
1BST 挿入の決定性
鍵集合が固定なら挿入順列が BST 形状を完全に決定する。根 = $\pi_1$、左部分木 = $\pi_1$ より小の鍵群、右部分木 = 大の鍵群。
鍵集合が固定なら挿入順列が BST 形状を完全に決定する。根 = $\pi_1$、左部分木 = $\pi_1$ より小の鍵群、右部分木 = 大の鍵群。
2反復挿入で高さ計算
各ノードを挿入する際に「根から辿った深さ」を記録。全ノードの最大深さが高さ。 再帰では $N = 10^5$ で深さ $O(N)$ になりうるため、反復 while ループを使う。
各ノードを挿入する際に「根から辿った深さ」を記録。全ノードの最大深さが高さ。 再帰では $N = 10^5$ で深さ $O(N)$ になりうるため、反復 while ループを使う。
3Catalan 数の公式
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{n! \cdot (n+1)!}$$ 漸化式: $C_0 = 1$, $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$（二分木の左右部分木のサイズで分類）
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{n! \cdot (n+1)!}$$ 漸化式: $C_0 = 1$, $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$（二分木の左右部分木のサイズで分類）
4mod 逆元と線形前計算
$p = 10^9+7$ は素数。$a^{-1} \equiv a^{p-2} \pmod{p}$（フェルマーの小定理）。 逆階乗テーブル: $\text{inv\_fact}[n] = n!^{-1}$，$\text{inv\_fact}[i] = \text{inv\_fact}[i+1] \cdot (i+1)$。
$p = 10^9+7$ は素数。$a^{-1} \equiv a^{p-2} \pmod{p}$（フェルマーの小定理）。 逆階乗テーブル: $\text{inv\_fact}[n] = n!^{-1}$，$\text{inv\_fact}[i] = \text{inv\_fact}[i+1] \cdot (i+1)$。
計算量
BST 高さ計算: $O(N \cdot h)$ 最悪 $O(N^2)$（偏った木）、期待 $O(N \log N)$（ランダム）
階乗テーブル構築: $O(N)$
Catalan 数計算: $O(\log p)$（pow での逆元）または $O(1)$（テーブル使用時）
空間: $O(N)$（木のノード + テーブル）
階乗テーブル構築: $O(N)$
Catalan 数計算: $O(\log p)$（pow での逆元）または $O(1)$（テーブル使用時）
空間: $O(N)$（木のノード + テーブル）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Catalan 式の混同 | $C_n = \binom{2n}{n}$ と間違える | fact[2*n] * inv_fact[n] * inv_fact[n+1] |
| 再帰 BST で RecursionError | $N=10^5$ で深さ最悪 $N$ | 反復 while ループで実装 |
| 深さのカウントずれ | 根の深さを 1 と定義してしまう | 根を 0 とし、挿入時に depth+1 |
inv_fact[n] の境界 | テーブルサイズ不足 | build_fact(2*N+5) で余裕を持つ |
次のステップ
- 発展問題: ランダム挿入 BST の期待高さ $O(\log N)$ の確率的証明
- 関連: Treap（ランダム優先度で BST をバランス化）、AVL 木の形状カウント
- 応用: $k$ 番目の BST 形状（辞書順）を Catalan 数と二分探索で特定