AtCoder Beginner Contest 478 E,F問題メモ

AtCoder Beginner Contest 478

E - lt and le

• $1$ 以上 $N$ 以下の整数からなる長さ $N$ の整数列 $A$ であって、次の $Q$ 個の条件をすべて満たすものが存在するか判定し、存在する場合 $1$ つ求めてください。
• $i$ 番目 $(1\le i\le Q)$ の条件は整数の $3$ つ組 $(t _ i,u _ i,v _ i)$ で与えられ、以下のように定義されます。
  • $t _ i=0$ のとき、$A _ {u _ i}\le A _ {v _ i}$
  • $t _ i=1$ のとき、$A _ {u _ i}\lt A _ {v _ i}$
• すべての条件を満たす列が複数存在するときは、どれを出力しても構いません。

• $1\le N\le2\times10 ^ 5$
• $1\le Q\le2\times10 ^ 5$
• $t _ i\in\lbrace0,1\rbrace\ (1\le i\le Q)$
• $1\le u _ i\le N\ (1\le i\le Q)$
• $1\le v _ i\le N\ (1\le i\le Q)$
• 入力はすべて整数

$t_i=0$ と $1$ の違いは、イコールを許すか許さないか。

$u_i→v_i$ に辺を張ったグラフを考え、上流の頂点ほど小さい値を割り当てる、的なことを考えたい。 だが、ループが発生していると困りそう。

ループが $t_i=0$ だけからなるなら、全てに同じ値を割り当てればよいのでセーフ。
$t_i=1$ が絡むと不可能となる。よって、

• $t_i=0$ のみで辺を張り、強連結成分分解する。
  • 同じ成分に入った頂点群は、同じ値を割り当てることが確定する。
• 強連結成分を縮約する。（1成分を1頂点とする）
• 縮約後のグラフに $t_i=1$ の辺を追加する。
  • ただし、両端が同じ強連結成分に属する場合は、その時点で不可能が確定する。
• 再度、強連結成分分解し、複数個の頂点からなる強連結成分ができたら不可能が確定。
• そうでなければ、上流から小さい値を割り当てて完成。

Python3

from atcoder.scc import SCCGraph


def solve(n, q, conditions):
    cond0 = []
    cond1 = []
    for t, u, v in conditions:
        u -= 1
        v -= 1
        if t == 0:
            cond0.append((u, v))
        else:
            cond1.append((u, v))
    scg = SCCGraph(n)
    for u, v in cond0:
        scg.add_edge(u, v)
    result = scg.scc()
    tmp = [0] * n
    for i, grp in enumerate(result):
        for v in grp:
            tmp[v] = i
    scg2 = SCCGraph(len(result))
    for u, v in cond1:
        if tmp[u] == tmp[v]:
            return False
        scg2.add_edge(tmp[u], tmp[v])
    for u, v in cond0:
        if tmp[u] == tmp[v]:
            continue
        scg2.add_edge(tmp[u], tmp[v])
    result2 = scg2.scc()
    ans = [0] * n
    for i, grp in enumerate(result2, start=1):
        if len(grp) >= 2:
            return False
        w = grp[0]
        for v in result[w]:
            ans[v] = i
    return ans


n, q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, edges)
if ans:
    print('Yes')
    print(*ans)
else:
    print('No')

F - Min-First Search

• 頂点 $1,$ 頂点 $2,\ldots,$ 頂点 $N$ からなる $N$ 頂点の木 $T$ に対して、以下の手順で得られる $(1,2,\ldots,N)$ の順列 $P$ を $f(T)$ とします。
  • はじめ、列 $P$ を空列 $()$ とし、集合 $S$ を $\lbrace1\rbrace$ とする。
  • 以下を $N$ 回繰り返す。
    • $S$ の最小値を $x$ とする。$S$ から $x$ を削除し、$P$ の末尾に $x$を追加する。
    • その後、$T$ において頂点 $x$ に隣接する頂点を頂点 $v _ 1,$ 頂点 $v _ 2,\ldots,$ 頂点 $v _ k$ とする。$i=1,2,\ldots,k$ について、$P$ に $v _ i$ が含まれていなければ $S$ に $v _ i$ を追加する。
• $(1,2,\ldots,N)$ の順列 $Q=(Q _ 1,Q _ 2,\ldots,Q _ N)$ が与えられます。$f(T)=Q$ となる木 $T$ の個数を $998244353$ で割った余りを求めてください。
  • ただし、ふたつの木は、ある頂点の組 $(u,v)$ が存在して、一方の木では頂点 $u$ と頂点 $v$ の間に辺があり、もう一方の木では辺がないとき、区別されます。

• $1\le N\le2\times10 ^ 5$
• $1\le Q _ i\le N\ (1\le i\le N)$
• $Q _ i\ne Q _ j\ (1\le i\lt j\le N)$
• $Q _ 1=1$
• 入力はすべて整数

数ヶ月前のARCに、似たような考察をする問題があったような。

頂点 $1$ を根とし、$v$ の親を $p_v$ とする。

各 $v$ は、$p_v$ が $S$ の最小値となって取り出され、$P$ に追加されたときに、$S$ に追加される。
つまり、$Q$ において、$v$ の親は $v$ より先に出現している。

頂点 $1$ のみがあり、そこに $Q_2,Q_3,...$ の順に頂点、およびその頂点と親を結ぶ辺を追加していくことを考える。
前述の考察より、$v$ を追加するとき、$p_v$ は（どれにするかは自由度があるが、どれにするにしろ）既に木に追加されている。

途中経過の一例
    ①        Q:  1 16 23 14 [18] ...
  ／｜↖
 ⑯ ㉓ ？
 /↖ ↖
⑭ ？ ？
 ↖
  ？

ある頂点を追加するとき、既存の頂点のどれなら親にして問題ないか？
これは、「その頂点から遡って、初めて出てくる、自身より大きい頂点まで」（その次からアウト）となる。

上例では⑱を追加するのに、⑭と㉓はOKで、①と⑯はアウトとなる。
元の操作を考えたとき、親が $P$ に追加された時点で $S$ には⑱が追加されるため、 ㉓と同時または先に $S$ に入ってしまうと、⑱より先に㉓が取り出されるのが矛盾する。
⑱は $S$ に入るのは、㉓が取り出された後でないといけないからである。

⑱は2通りの接続先があることになる。
接続先の個数は、木の構造がどうであるかは関係なく、$Q$ のみによって決まる。

よって、各 $i$ につき、「$L_i:=Q_i$ より遡って最初に出現する $Q_i$ より大きい値のindex、存在しない場合は $1$」とすると、

• $\displaystyle \prod_{i=2}^{N}(i-L_i)$

が答えとなる。$L_i$ は、セグ木に載せて min_left を使ったり、Editorialにある方法を使ったりすると求められる。

Python3

from atcoder.segtree import SegTree


def solve(n, qqq):
    MOD = 998244353
    sgt = SegTree(max, -1, qqq)
    ans = 1
    for i in range(1, n):
        q = qqq[i]
        j = sgt.min_left(i, lambda a: a < q)
        if j == 0:
            cf = i
        else:
            cf = i - j + 1
        ans *= cf
        ans %= MOD
    return ans


n = int(input())
qqq = list(map(int, input().split()))
ans = solve(n, qqq)
print(ans)