コンテンツにスキップ

スタック

タグ「スタック」の記事 3 件

Codeforces Round 1125 (Div. 3) B - Did Not Go to Print

文書 1,…,n1, \dots, n と、最初は空のプリンターのメモリがあります。ii 番目の操作 sis_i は次のいずれかです。

  • 1:文書 ii をメモリの一番上に積む
  • 2:メモリが空でなければ、一番上の文書を印刷してメモリから取り除く。空なら文書 ii を印刷する
  • 3:文書 ii を印刷する

すべての操作のあとで、一度も印刷されなかった文書の番号を昇順に出力してください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

メモリは「最後に積んだものから取り出す」ので、スタックそのものです。操作を順にシミュレーションして、印刷された文書を記録すれば、残りが答えです。

  • 1:スタックに ii を push する
  • 2:スタックが空でなければ pop した文書を、空なら ii を印刷済みにする
  • 3:ii を印刷済みにする

なお、2 でスタックが空でないときは、文書 ii 自身は印刷されません。2 の操作では文書 ii はメモリにも入らないので、その文書が印刷されることはもうありません。

各操作は O(1)O(1) なので、全体で O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
t = []
l = []
for i, c in enumerate(S):
if c == "1":
l.append(i)
elif c == "2":
if l:
t.append(l.pop())
else:
t.append(i)
else:
t.append(i)
ans = set(range(N)) - set(t)
print(len(ans))
print(*[i + 1 for i in sorted(ans)])

l がメモリのスタック、t が印刷された文書のリストです。文書番号は 0 始まりで持っておき、出力するときに 1 を足しています。k=0k = 0 のときは print(*[]) が空行を出力するので、そのままで大丈夫です。

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 を足します。

ABC478 F - Min-First Search

頂点 1,…,N1, \ldots, N の木 TT について、頂点 11 から始めて「訪問候補の集合 SS から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を SS に加える」ことを繰り返したときの訪問順を f(T)f(T) とします。順列 QQ (Q1=1Q_1 = 1) が与えられるので、f(T)=Qf(T) = Q となる木 TT の個数を 998244353998244353 で割った余りを求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、添字を 00 始まりにして Q0=1Q_0 = 1 とします。

i≥1i \ge 1 について、QiQ_i を SS に加えたのは、QiQ_i より先に訪問された隣接頂点です。木なので、QiQ_i に隣接する頂点のうち QiQ_i より先に訪問されるものはちょうど 1 つで、これを QiQ_i の親 QkQ_k (k<ik < i) と呼ぶことにします。木は「各 i≥1i \ge 1 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。

QkQ_k を訪問した時点で QiQ_i が SS に入り、QiQ_i は ii 番目に取り出されるまで SS に残ります。その間に取り出される Qk+1,…,Qi−1Q_{k+1}, \ldots, Q_{i-1} はそのときの SS の最小値なので、すべて QiQ_i より小さくなければなりません。

そこで、QiQ_i より前にある QiQ_i より大きい要素のうち最も後ろのものの位置を pip_i とします(なければ pi=0p_i = 0)。すると親の位置 kk の条件は

pi≤k≤i−1p_i \le k \le i - 1

で、選び方は i−pii - p_i 通りです(QpiQ_{p_i} 自身は大きくても、親として先に訪問されるので構いません)。

逆に、すべての ii についてこの範囲で親を選べば、ii 番目の時点で SS に残っている他の頂点 QmQ_m (m>im > i) は、親が ii より前にあるので条件から Qi<QmQ_i < Q_m となり、QiQ_i が最小として正しく取り出されます。したがって各 ii の選び方は独立で、答えは

∏i=1N−1(i−pi)\prod_{i=1}^{N-1} (i - p_i)

です。

pip_i は「直前にある自分より大きい要素の位置」なので、

  • 区間最大値のセグメント木で min_left を使って二分探索する(O(Nlog⁡N)O(N \log N))
  • 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で O(N)O(N))

のどちらでも求められます。

C++(セグメント木)
#include "ou-library/modint.hpp"
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
using mint = modint998244353;
void solve() {
LL(N);
VL(Q, N);
Q--;
mint ans = 1;
RMaxQ<ll> seg(Q);
rep(i, 1, N) {
ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; });
if (j)
j--;
ans *= i - j;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

min_left(i, x <= Q[i]) で「Ql,…,Qi−1Q_l, \ldots, Q_{i-1} がすべて QiQ_i 以下になる最小の ll」を求め、その 1 つ前が pip_i です。RMaxQ は区間最大値のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

cLay(ポインタをたどる)
#define MD 998244353
ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);

g[i] に pip_i を記録しておき、Qi−1Q_{i-1} から始めて自分より小さい間は g をたどることで pip_i を求めています。Q0=1Q_0 = 1 は最小なので、より大きい要素がなければ p=0p = 0 で止まります。