Codeforces Global Round 5 E. Balanced Binary Search Trees

Problem - E - Codeforces

問題概要

以下の条件を満たす根付き木を二分探索木と呼ぶ。

任意の頂点について以下が成り立つ。
- 「左側の子」と「右側の子」がそれぞれ高々1個存在する。
- 左側の子孫が存在する場合、それら全ての頂点番号は $i$ より小さい。
- 右側の子孫が存在する場合、それら全ての頂点番号は $i$ より大きい。

頂点番号 $1, ..., n$ の $n$ 頂点からなり、以下の条件を満たす二分探索木の個数を $\bmod 998244353$ で求めよ。

頂点数 $n$ の二分探索木の中で、各頂点の深さの合計が最小である。
任意の頂点について以下が成り立つ。
- 左側の子が存在する場合、その頂点番号の偶奇は $i$ と異なる。
- 右側の子が存在する場合、その頂点番号の偶奇は $i$ と等しい。

制約

$1 \le n \le 10^{6}$

解法

$\bmod 998244353$ というハッタリがありますが、実は条件を満たす木は高々1つです。その理由を説明します。

まず深さの合計が最小であるという条件は、直感的にはできるだけ根に近いところに頂点が集まっているということです。これは具体的には、木の最下段以外は頂点が詰まっている、つまり完全二分木になっているということを意味します。

ということでまずは、完全二分木になっている部分の深さの最大値 $D$ を求めます（根を深さ0とします）。これは $2^{D+1}-1 \le n$ を満たす最大の $D$ として求められます。このとき深さ $D+2$ 以上の頂点は存在しません。

f:id:betrue12:20191017195356p:plain

条件を満たす木の構成を、以下のように試みましょう。

まず頂点番号 $1, ..., n$ のうち $2^{D+1}-1$ 個を使って、偶奇の条件を満たすような深さ $D$ までの完全二分木を作る。
上記で使わなかった（飛ばした）頂点たちを、深さ $D+1$ の段に適切に付けられるか考える。

ここで飛ばした頂点は、大小関係から「付ける場合は、深さ $D$ のこの頂点のこちら側に付けなければいけない」という位置が一意に定まります。つまりもし連続して2つ以上の頂点が飛ばされている場合、それはどう頑張っても深さ $D+1$ の段には収まりません。これが完全二分木を作る上で強い制約になります。

完全二分木の頂点番号を、番号の小さい位置から順番に決めていきます。番号が最も小さい頂点は左下の頂点ですが、連続して1, 2を飛ばしてはいけないので、左下の頂点は1または2である必要があります。これはとりあえず両方試すことにします。

ある1つの頂点の偶奇が決まると全ての頂点の偶奇が決まります。各頂点の偶奇が指定され、2つ以上の頂点番号を飛ばしてはいけないので、全ての頂点番号が小さい方から順に一意に定まっていきます。

あとは飛ばした頂点が深さ $D+1$ の段に適切に付くかどうかを確認します。頂点番号を飛ばすようなパターンを実際に列挙してみると、ほとんどの飛ばした頂点は偶奇条件に合うように $D+1$ の段に上手く収まります。NGとなるのは完全二分木の右下の頂点番号が $n$ ではない場合です。 $n$ を超えている場合は当然NG、 $n-2$ 以下である場合はそれ以降を連続で飛ばすことになるのでNG、 $n-1$ である場合はその右下に偶奇の異なる $n$ を付けると条件違反になるのでNGです。

このことから結局、完全二分木の右下の頂点番号は必ず $n$ にならないといけないので、左下の頂点の偶奇も片方しか条件を満たさないことになります。これが、条件を満たす木が高々1つである理由です。

以上の考察より、私の解法は以下のようになりました。

完全二分木の深さ $D$ を、 $2^{D+1}-1 \le n$ を満たす最大の $D$ として求める。
完全二分木の左下の頂点の番号を1または2と仮定してそれぞれ試す。DFSのように完全二分木の頂点番号を小さい順に決めていく。その結果、右下の頂点番号が $n$ となった場合、これは条件を満たす。
条件を満たす木の個数を出力する。これは高々1個である。

もしくは、答えが1になる $n$ を並べてみると単純な漸化式を持つ数列になるようです。これを実験等で突き止めて信じる心を持てば、実際に木を構成しなくても解くことができます。