AtCoder Beginner Contest 378 F,G問題メモ

AtCoder Beginner Contest 378

F - Add One Edge 2

• $N$ 頂点の木が与えられます。$i$ 番目の辺 $(1\leq i\leq N-1)$ は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいます。
• 与えられた木に無向辺を一本追加して得られるグラフは、必ずちょうど一つの閉路を含みます。
• そのようなグラフのうち、以下の条件を全て満たすものの個数を求めてください。
  • グラフは単純グラフ
  • グラフの閉路に含まれる頂点の次数は全て $3$

• $3 \leq N \leq 2 \times 10^5$
• $1\leq u_i,v_i\leq N$
• 与えられるグラフは木である
• 入力される数値は全て整数

木の2点間を結ぶパスで、次数が 2-3-3-3-…-3-3-2 となっているものの個数を数えればよい。（3は1個以上）
両端を結ぶと、次数が全て3の閉路ができる。

頂点 $v$ の次数を $d_v$ とする。

木DPをする。

• $\mathrm{DP}[v]:=v$ 以下の部分木で、$v$ から葉方向に向かって次数が 3-3-…-3-2 となっているパスの個数
  • 特に $d_v=3$ でない $v$ に対しては $\mathrm{DP}[v]=0$ となる。

また、$\mathrm{DP}[u]$ を計算する際、子の1つを $v$ として、以下を $\mathrm{DP}'[v]$ とする。

• $d_u=3,d_v=2$ のとき、$\mathrm{DP}'[v]=\mathrm{DP}[v]+1$
• $d_u=3,d_v \neq 2$ のとき、$\mathrm{DP}'[v]=\mathrm{DP}[v]$
• $d_u \neq =3$ のとき、$\mathrm{DP}'[v]=0$

更新は、$\displaystyle \mathrm{DP}[u]=\sum_{v \in \mathrm{Children}(u)}\mathrm{DP}'[v]$ となる。

答えは、DPの途中過程で条件に当てはまるパスが見つかったら加算していく。

• 条件に当てはまるパス
  • $d_u=2$ の頂点 $u$ に来たとき、子から伸びてきたパスを打ち切る。
    • $u$ の各子 $v$ に対し、$\mathrm{DP}[v]$
  • $d_u=3$ の頂点 $u$ に来たとき、親を除く2つの子 $v,w$ それぞれから伸びてきたパスを繋ぐ。
    • $\mathrm{DP}'[v] \times \mathrm{DP}'[w]$

根が次数2や3だったりした場合、上記の法則が崩れてややこしいので、次数1の頂点を根として木DPすれば楽。

Python3

def solve(n, links):
    degrees = [len(lks) for lks in links]
    # print(*enumerate(links))
    dp = [-1] * n
    ans = 0
    i = degrees.index(1)  # 根の処理の場合分けが面倒なので葉の1つを根にする
    q = [i]
    while q:
        u = q[-1]
        if dp[u] == -1:
            dp[u] = -2
            p = -1
            for v in links[u]:
                if dp[v] == -1:
                    q.append(v)
                else:
                    p = v
            links[u].discard(p)
            continue
        q.pop()
        du = degrees[u]
        res = 0
        if du == 2:
            for v in links[u]:
                ans += dp[v]
        elif du == 3:
            assert len(links[u]) == 2
            v, w = links[u]
            ans += dp[v] * dp[w]
            res = dp[v] + dp[w]
            if degrees[v] == 2:
                res += 1
                ans += dp[w]
            if degrees[w] == 2:
                res += 1
                ans += dp[v]
            if degrees[v] == 2 and degrees[w] == 2:
                ans += 1
        dp[u] = res
        # print(f'{u=} {dp=}')

    return ans


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = solve(n, links)
print(ans)

G - Everlasting LIDS

• 整数 $A,B,M$ が与えられます。
• $(1,2,\ldots,AB-1)$ の順列 $P=(P_1,\ldots,P_{AB-1})$ であって、以下の条件を全て満たすものは何通りありますか？個数を $M$ で割ったあまりを求めてください。
  • $P$ の最長増加部分列の長さは $A$
  • $P$ の最長減少部分列の長さは $B$
  • 整数 $n$ であって、$P$ の末尾に $n+0.5$ を追加しても最長増加部分列の長さも最長減少部分列の長さも変化しないようなものが存在する

• 入力される数値は全て整数
• $2\leq A,B$
• $AB\leq 120$
• $10^8\leq M\leq 10^9$
• $M$ は素数

知らないとどうにもならない感がある。

「順列」と「標準タブローの組」との間に成り立つ1対1対応を、ロビンソン・シェンステッド対応という。

• ヤング図形・標準タブローとは
  • ヤング図形
• ヤング図形と競技プログラミング - 最長増加部分列とロビンソン・シェンステッド対応

• ヤング図形
  • $N$ 個の箱を以下のようにグリッド状に並べたもの。分割数を視覚的に表現する際などに用いられる。
  • 上の列ほど長くなるように配置する。また、必ず左詰とする。

  • (例) □□□□□    10 = 5 + 3 + 2
         □□□
         □□

• 標準タブロー
  • $1～N$ の整数を、以下のルールを満たしてヤング図形状に配置したもの
    • $A_{i,j} \ge A_{i-1,j}$ かつ $A_{i,j} \ge A_{i,j-1}$（各数字は上と左の数字より大きい）

  • (例) １２５７９
         ３６10
         ４８

これが最長増加部分列とどう関係するか？

一般に、数列 $A$ の最長増加部分列を求めるDPといえば以下のものが代表的である。

• $\mathrm{DP_{LIS}}[i]:=$ 長さ $i$ の最長増加部分列の末尾としてあり得る最小の値

$A_1,A_2,...$ と順に処理していくにあたり、DP配列には1要素につき1箇所の書き換え、または末尾への追加が発生する。
書き換えによってDPから“追い出された”数字だけで構成されるLISを、2行目で同じように構築していく。
以下、2行目からも追い出された数は3行目、4行目、、、と構築していくと、その配置は標準タブローの条件を満たす。

• 視覚的に実験できるサイト

A = 4 1 8 3 6 2 5 10 7 9

i Ai  標準タブロー
1  4   ４

2  1   １         1行目から 4 が追い出され、2行目に収まる。
       ４

3  8   １８
       ４
:  :    :

続き

4  3   １３
       ４８

5  6   １３６
       ４８

6  2   １２６     2によって1行目から3が追い出され、
       ３８       3によって2行目から4が追い出される。
       ４

7  5   １２５     5によって1行目から6が追い出され、
       ３６       6によって2行目から8が追い出される。
       ４８       8は3行目の末尾に収まる。

8 10   １２５10
       ３６
       ４８

9  7   １２５７
       ３６10
       ４８

10 9   １２５７９
       ３６10
       ４８

すると、順列 $A$ から生成される標準タブローの

• 1行目の長さが $A$ の最長増加部分列の長さ
• 1列目の長さが $A$ の最長減少部分列の長さ

となる。

さらに、$1～N$ からなる「同じ形状の2つの標準タブローの組」と「順列」は、1対1対応する。
これを「ロビンソン・シェンステッド対応」という。

P           Q               順列 R
１２５７９  １３５８10  →  4 1 8 3 6 2 5 10 7 9
３６10      ２４９      ←
４８        ６７

$P$ は先ほどの方法で作られる標準タブローである。
$Q$ は $P$ がどのような順番で拡張されていったかを示す。

どのような $P,Q$ の組でも対応する順列 $R$ が一意に復元できる。

よって、ある標準タブローの形状につき、（その形状になる標準タブローの個数）² が、 「順列のうち標準タブローを生成するとその形状になるようなもの」の個数となる。

ある形状の標準タブローの個数は、以下で計算できる。

• $\displaystyle \frac{N!}{\prod h(i,j)}$
  • $N$ は要素数（上例の $P$ だと 10）
  • $h(i,j)$ は、各要素のフック長

フック長とは、各要素から右または下にある要素の個数を示す。

□□□□□□□
□●■■■      ●のフック長は6
□■□
□■
□

$1～AB-1$ といういかにも意味ありげな順列長は、標準タブローの形を一意に定めるためにある。

□□□□□  ↑  1行目の幅をA、1列目の高さをBに収めて
□□□□□  Ｂ  AB-1 個の要素を配置するには
□□□□    ↓  右下のみ欠けた形しかない。
←- A --→

基本的な方針は、標準タブローがこの形状になるような順列の個数を数え上げればよい。

ただし、「最長増加部分列・最長減少部分列の長さを変化させないようにもう1要素追加できる」という制約がある。
そのように追加できる場所は、右下の1箇所しかない。

“追い出された”数が連鎖的に次の行の数を追い出していき、$B$ 行目で末尾要素より大きくなる。

       n+0.5
        ↓
□□□□○    ○を追い出すような数を n+0.5 に選ぶ。
□□□□◎    追い出された○が◎を追い出す。
□□□△！    ◎は△より大きいので、右下の位置！に収まる、というパターンしかない。

標準タブローの大小関係を考えると、追い出されるのは必ず各行の末尾要素でなければならない。
$i$ 行目から $j$ 列目の数が追い出された場合、$P_{i,j} \lt P_{i+1,j}$ より、追い出された数が $i+1$ 行目に収まる場所は $j$ 列目またはそれより左になる。
$B-1$ 行目から追い出される数が△より大きくなるためには、どの行からも末尾要素が追い出されなければならないことがわかる。

つまり、通常の標準タブローの大小関係に追加で、以下の↙のような大小関係がなければならない。

□<□<□<□<○
＾ ＾ ＾ ＾↙^    ※矢印は 大→小 の方向
□<□<□<□<◎
＾ ＾ ＾ ＾↙
□<□<□<△

これは公式では計算できないが、$AB \le 120$ で十分小さいので、 $k=1,2,...,AB-1$ の順に追加場所を決定していきながら、 「各行にそれぞれ何個の要素を追加したか」を状態に持つDPでおこなえる。
実際にやってみると、状態数は最大50万程度で収まることが実験で分かる。

これで $P$ の個数が求まる。$Q$ に関してはこのような制約はないのでフック長公式で計算できる。

（$P$ の個数）×（$Q$ の個数）が答えとなる。

Python3

from bisect import bisect_left


def lis(aaa):
    res = [aaa[0]]
    for a in aaa[1:]:
        if a > res[-1]:
            res.append(a)
        else:
            res[bisect_left(res, a)] = a
    return res


def bruteforce(a, b):
    from itertools import permutations
    n = a * b - 1
    for ppp in permutations(range(n)):
        inc = lis(ppp)
        if len(inc) == a:
            qqq = [n + 1 - p for p in ppp]
            dec = lis(qqq)
            if len(dec) == b:
                dec = [n + 1 - q for q in dec]
                if inc[-1] > dec[-1]:
                    print(ppp, inc, dec)


def count_tableau(h, w, mod, k, row_counts, memo={}):
    """
    右上だけ欠けてるような標準タブロー亜種の個数を数える
    □□□■
    □□□□
    □□□□
    """
    if k == h * w:
        return 1
    key = tuple(row_counts)
    if key in memo:
        return memo[key]
    result = 0
    pj = w
    for i, j in enumerate(row_counts):
        if j < pj:
            row_counts[i] += 1
            if i == 0 and j == w - 2:
                row_counts[i] += 1
            result += count_tableau(h, w, mod, k + 1, row_counts)
            row_counts[i] = j
        pj = j
    if len(row_counts) < h:
        if len(row_counts) == 0 and w == 2:
            row_counts.append(2)
        else:
            row_counts.append(1)
        result += count_tableau(h, w, mod, k + 1, row_counts)
        row_counts.pop()
    result %= mod
    memo[key] = result
    return result


def solve(a, b, m):
    tails = []
    p_cnt = count_tableau(b, a, m, 1, tails)
    hooks = 1
    for i in range(b):
        for j in range(a):
            h = (b - i) + (a - j) - 1
            if i == b - 1:
                h -= 1
            if j == a - 1:
                h -= 1
            if h > 0:
                hooks = hooks * h % m
    q_cnt = pow(hooks, -1, m)
    for i in range(2, a * b):
        q_cnt *= i
        q_cnt %= m
    return p_cnt * q_cnt % m


a, b, m = map(int, input().split())
# bruteforce(a, b)
ans = solve(a, b, m)
print(ans)