コンテンツにスキップ

SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain

サイト
SamCoding
コンテスト
SamCoding Round 7 (Div. 2)
問題
K - Blueprints Washed by the Rain(常設版)

正の整数の列 b1,…,bnb_1, \dots, b_n に対して、g(b)ig(b)_i を「ii より左にあって bj<bib_j < b_i を満たす jj のうち最大のもの(なければ 00)」と定めます。ある bb によって y=g(b)y = g(b) と書ける列 yy を「復元可能」と呼びます。

長さ nn の列 xx が与えられます。xx のいくつかの要素は −1-1 です。−1-1 をそれぞれ 00 以上 nn 以下の整数に置き換えて xx を復元可能にする方法の数を、109+710^9 + 7 で割った余りで求めてください(nn の総和 ≤5000\le 5000)。

bb の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n1, \dots, n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。gg の定義が真の不等号 bj<bib_j < b_i なので、こうすると「bj<bib_j < b_i」と「jj のほうが小さい(j<ij < i のとき)」が一致します。

このとき、ii の左部分木はちょうど区間 [gi+1,i−1][g_i + 1, i - 1] になります。ii の左部分木は「ii から左へ、ii より大きい要素が続く範囲」で、その左端の外側が ii より左で最も近い小さい要素、つまり gig_i だからです。

gg とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。

  • 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
  • ii を追加するときは、bib_i より大きい要素をスタックから pop する。pop した部分が ii の左部分木になり、ii は残ったスタックの一番上の右の子になる。最後に ii を push する

pop し終わったときのスタックの一番上が、ちょうど gig_i です(空なら 00)。そのため、各ステップで何個 pop するかは gg から決まり、ツリーの形も gg から決まります。逆に、どんな形のツリーにも、それを作る bb が存在します(例えば、根からの深さをそのまま bb にすればよいです)。

まとめると、復元可能な yy と、nn 頂点の二分木の形は一対一に対応します。全部が −1-1 のときの答えは Catalan 数 CnC_n で、サンプル 3 の 132=C6132 = C_6 と一致します。

例えば g=[0,1,2,1,0,0,6]g = [0, 1, 2, 1, 0, 0, 6] に対応するツリーの親は、[5,4,2,1,6,−,6][5, 4, 2, 1, 6, -, 6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3][g_4 + 1, 3] = [2, 3] になっていることなどが確かめられます。

この対応を使うと、問題は次のように言い換えられます。

頂点 1,…,n1, \dots, n を中間順に並べた二分木のうち、xi≠−1x_i \ne -1 であるすべての ii について「ii の左部分木がちょうど [xi+1,i−1][x_i + 1, i - 1] である」ものを数える

xi≥ix_i \ge i のときは、そのような左部分木はありえないので答えは 00 です。

固定された左部分木は独立に数えられる

Section titled “固定された左部分木は独立に数えられる”

xi≠−1x_i \ne -1 のとき、ii の左部分木 [xi+1,i−1][x_i + 1, i - 1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと ii に潰してしまえば、ii は「左の子を持たない頂点」 として扱えます。

そこで、左から順に頂点を見ながら、次のように列を潰していきます。

  • xi=−1x_i = -1 のとき:ii を「自由な頂点」として列の末尾に加える
  • xi≠−1x_i \ne -1 のとき:列の中から xi+1x_i + 1 以降に始まる要素をすべて取り出す。それらが ii の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1x_i + 1 から ii までをまとめて「左の子を持たない頂点」1 個として末尾に加える

列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1x_i + 1 から始まる要素になっていないとき、つまり xi+1x_i + 1 がすでに潰された要素の内側にあるときは、答えは 00 です。ii の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。

最後に残った列全体の形の数も掛ければ、答えになります。

左の子を持たない頂点を含む二分木の数え上げ

Section titled “左の子を持たない頂点を含む二分木の数え上げ”

あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。

Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが hh のとき、次の頂点を追加する方法は次のとおりです。

  • 自由な頂点:00 個以上 hh 個以下を pop してから push するので、新しい高さは 11 以上 h+1h + 1 以下
  • 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1h + 1

pop の仕方とツリーの形は一対一に対応するので、dp[h]\mathrm{dp}[h] を「スタックの高さが hh になる方法の数」とする DP で数えられます。自由な頂点の遷移は

dp′[h′]=∑h≥h′−1dp[h]\mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h]

なので、後ろからの累積和で O(長さ)O(\text{長さ}) で計算できます。答えは最後の dp\mathrm{dp} の総和です。

各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ mm の列の DP は O(m2)O(m^2) なので、全体で O(n2)O(n^2) です。

Python
from bisect import bisect_left
from 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 は昇順なので、xi+1x_i + 1 から始まる要素を bisect_left で探しています。

count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。