SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- K - Blueprints Washed by the Rain(常設版)
正の整数の列 に対して、 を「 より左にあって を満たす のうち最大のもの(なければ )」と定めます。ある によって と書ける列 を「復元可能」と呼びます。
長さ の列 が与えられます。 のいくつかの要素は です。 をそれぞれ 以上 以下の整数に置き換えて を復元可能にする方法の数を、 で割った余りで求めてください( の総和 )。
g と Cartesian Tree の対応
Section titled “g と Cartesian Tree の対応”の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。 の定義が真の不等号 なので、こうすると「」と「 のほうが小さい( のとき)」が一致します。
このとき、 の左部分木はちょうど区間 になります。 の左部分木は「 から左へ、 より大きい要素が続く範囲」で、その左端の外側が より左で最も近い小さい要素、つまり だからです。
とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。
- 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
- を追加するときは、 より大きい要素をスタックから pop する。pop した部分が の左部分木になり、 は残ったスタックの一番上の右の子になる。最後に を push する
pop し終わったときのスタックの一番上が、ちょうど です(空なら )。そのため、各ステップで何個 pop するかは から決まり、ツリーの形も から決まります。逆に、どんな形のツリーにも、それを作る が存在します(例えば、根からの深さをそのまま にすればよいです)。
まとめると、復元可能な と、 頂点の二分木の形は一対一に対応します。全部が のときの答えは Catalan 数 で、サンプル 3 の と一致します。
例えば に対応するツリーの親は、 です(6 が根)。4 の左部分木が になっていることなどが確かめられます。
問題の言い換え
Section titled “問題の言い換え”この対応を使うと、問題は次のように言い換えられます。
頂点 を中間順に並べた二分木のうち、 であるすべての について「 の左部分木がちょうど である」ものを数える
のときは、そのような左部分木はありえないので答えは です。
固定された左部分木は独立に数えられる
Section titled “固定された左部分木は独立に数えられる”のとき、 の左部分木 は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと に潰してしまえば、 は「左の子を持たない頂点」 として扱えます。
そこで、左から順に頂点を見ながら、次のように列を潰していきます。
- のとき: を「自由な頂点」として列の末尾に加える
- のとき:列の中から 以降に始まる要素をすべて取り出す。それらが の左部分木になるので、その形の数を答えに掛ける。そのあと、 から までをまとめて「左の子を持たない頂点」1 個として末尾に加える
列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が から始まる要素になっていないとき、つまり がすでに潰された要素の内側にあるときは、答えは です。 の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。
最後に残った列全体の形の数も掛ければ、答えになります。
左の子を持たない頂点を含む二分木の数え上げ
Section titled “左の子を持たない頂点を含む二分木の数え上げ”あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。
Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが のとき、次の頂点を追加する方法は次のとおりです。
- 自由な頂点: 個以上 個以下を pop してから push するので、新しい高さは 以上 以下
- 左の子を持たない頂点:pop しないで push するので、新しい高さは
pop の仕方とツリーの形は一対一に対応するので、 を「スタックの高さが になる方法の数」とする DP で数えられます。自由な頂点の遷移は
なので、後ろからの累積和で で計算できます。答えは最後の の総和です。
各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ の列の DP は なので、全体で です。
Python
from bisect import bisect_leftfrom itertools import accumulate
MOD = 10**9 + 7
def count(flags): dp = [1] for f in flags: if f: dp = [0] + dp else: s = list(accumulate(reversed(dp))) s.reverse() dp = [0] + [v % MOD for v in s] return sum(dp) % MOD
def solve(n, x): ans = 1 starts = [] flags = [] for i in range(1, n + 1): if x[i - 1] == -1: starts.append(i) flags.append(False) continue l = x[i - 1] + 1 if l > i: return 0 k = bisect_left(starts, l) if l < i and (k == len(starts) or starts[k] != l): return 0 ans = ans * count(flags[k:]) % MOD del starts[k:] del flags[k:] starts.append(l) flags.append(True) return ans * count(flags) % MOD
t = int(input())for _ in range(t): n = int(input()) x = list(map(int, input().split())) print(solve(n, x))starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、 から始まる要素を bisect_left で探しています。
count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。