NOMURA Programming Competition 2020 C,D問題メモ

NOMURA Programming Competition 2020

C - Folia

• 根を深さ0として、深さ $N$ の二分木を考える
• $A_0,A_1,...,A_N$ が与えられる
• $d=0～N$ について、深さ $d$ の「葉の数」が $A_d$ となるようにしたい
  • 葉とは、子を持たない頂点を指す
• 可能か判定し、可能ならその中で頂点数の最大値を求めよ
• $0 \le N \le 10^5$
• $0 \le A_i \le 10^8$
• $A_N \ge 1$

配列なんかでたまにある「左から可能な最大」「右から可能な最大」をそれぞれ求めて、minを取ったのが全体で可能な最大、というのを木でやる感じ。

葉でない頂点は、1個または2個の子を持つ。

  ○    ○     深さ d-1
 ／    ／＼
○    ○  ○        d

なので、ある深さ $d$ で作れる頂点数は、$d-1$ の葉でない頂点数の1倍～2倍となる。

適当に子が1つの頂点と2つの頂点の個数を調整すれば、この範囲内なら深さ $d$ の頂点数を自由に決められる。

なので、深さ $d$ の頂点数をこの範囲内にどうやったってできないというのが、不可能な場合である。

「少なすぎてできない」というのはあり得なくて、やろうと思えばずっと子が1つだけの頂点を繋げていける。

          子の数
      ○    0
     ／
    ○      0
   ／
  ○        0
 ／
...

「多すぎてできない」のを考える。つまり、深さ $d$ で作れる頂点数が $V_d$ なのに、それを超える $A_d$ 個の葉を作れと言われても、無理である。

根から、できる最大の頂点数を調べていく。

Ai                       頂点数の最大    葉でない頂点の最大
 0      ○                                      1
       ／＼                           ↙ x2
 0    ○  ○                  2       → -Ai    2
      /\  /\
 1   ○○○●  ←1個は葉      4                 3
 
 0   OOOOOO                   6                 6
 
 2  OO....OO                 12

こんな感じで、2倍して、葉なる頂点数 $A_i$ を引いて、とすればよい。

この過程で、頂点数の最大が $A_i$ より少なくなったらアウト。アウトにならなければ、可能。

ただ、これはあくまで根から考えた最大であって、このままでは $A_N$ との整合が取れない。

よって、次に下から考える。

さっきの計算を逆に考えると、ある深さ $d$ の頂点数がわかっているとすると、$d-1$ の頂点数はこれを1～2で割った数となる。

なるべく頂点数を多く保ちたいのであれば、1で割る（つまり、全ての親を別々の頂点にする）のがよい。

  ○   ○   ○   ○   ○  深さ d-1  頂点数 5
 ／   ／   ／   ／   ／
○   ○   ○   ○   ○    深さ d    頂点数 5

これをもとに、下から可能な頂点数の最大を調べる。その際、根から求めた頂点数を超えないようにする。

※木を上下ひっくり返す

             根から考えた      下から考えた      上下統合した
Ai           頂点数の最大  葉でない頂点数の最大  頂点数の最大
 2  ●  ●        12                                  2
     \   \                              ↙------'
 0   ○  ○        6                2      +Ai →     2
      \   \
 1    ○  ○  ●   4                2                 3
       \  /   /
 0      ○  ○     2                3          3  →  2
         ＼／       `→ 根からの最大を超えてしまう場合は、minをとる
 0        ○       1                2          2  →  1
                                                    -----
                         ここの合計が、答えとなる→  10

D - Urban Planning

• 都市が $N$ 個あり、はじめ、道路はない
• 以下に従って、都市間を結ぶ双方向の道路を作る
  • 各都市は、自分以外の都市を1つだけ指定する
  • 都市 $i$ が $P_i$ を指定したら、この2都市は道路を通って行き来できるようにする（直接でなくてもよい）
• 今、いくつかの都市は既に指定を決めたが、決まっていない都市もある
• 各都市の指定状況は $P_1,P_2,...,P_N$ で与えられる
  • '-1' なら未定、それ以外なら指定した都市を示す
• ここで、未定の都市数を $k$ とすると、これらの指定の決め方は $(N-1)^k$ 通りある
• 全ての決め方について、それを満たすために必要な最小の道路数を求め、総和を $\mod{10^9+7}$ で答えよ
• $2 \le N \le 5000$

$i$ と $P_i$ が、他の都市の指定により既に道路を通って行き来できるなら新たな道路を建設する必要は無い。

なので、既に指定済みの都市に関しては、Union-Find木で連結成分を管理する。（連結の頂点数も求められるようにしておく）

各都市からは最大1つしか辺を伸ばせないため、ある連結成分に $P_i=-1$（未指定）の都市が含まれているとしても、多くとも1つである。 （連結な $N$ 頂点のグラフの最小辺数は $N-1$。“-1” からはこの時点ではまだ辺を伸ばさないため、2個以上含まれると辺数が $N-2$ 以下になる）

指定済みの都市を繋げた結果、こんな感じになる。この時点の6本の道路は、残りをどのように決めるとしても必要になる。

○-○-○     頂点数 3  ○: 指定済み
●-○-○-○  頂点数 4  ●: 未指定
●-○        頂点数 2
●           頂点数 1

ここから、●を決めた時の新設道路数を考えていく。

基本的には、「自身が含まれる連結成分内の頂点を指定すると0」「含まれない頂点を指定すると+1」となる。

しかし、ここでも他の●の決め方によっては、指定した頂点が既に連結かも知れない。

   ❶-○-○-○    ❶が、❷の連結成分の頂点を指定した場合
   ↓
❷-○           →❷を決めるとき、自身に加え、❶の頂点も既に連結成分

2個だけならまだしも、3個、4個をまたいで広く連結になっているかも知れない。

❶-○-○-○
↓    ↑
❸    ❷-○       ❸は、既に❶とも❷とも連結

これを、上手く除いて考えなければならない。この方法がわからなかった。

---

この問題のように、各頂点から「1本のみ」辺を伸ばすとき、無駄な辺ができるとしても、各連結成分内に多くとも1本である。 （無駄な辺ができる場合、閉路ができる）

●←●  ●⇄●←●
↓↗
●

この「閉路」を固定して考えると、閉路ごとに独立に考えられて上手くいく。

元の問題に戻って、❶❷が互いに互いの連結成分を指定し合う閉路を考える。 以下、|❶| で❶の連結成分数を示すとする。

❶-○-○-○
↓ ↑
○-❷      ❸

この場合の選び方は、$|❶| \times |❷|＝8$ 通り。（あとは❸の選び方が $N-1$ 通り）

同様に❶❸、❷❸の閉路も考えると、経由する連結成分が2個である閉路は以下になる。

• $(|❶||❷| + |❶||❸| + |❷||❸|) (N-1)^{k-2}$
  • $k$ は未指定の都市数

また、長さ3の、❶❷❸全てを巡る閉路は、巡る順番もパターンに含まれる。

❶-○-○-○    ○-○-○-❶
↓       ↑    ↑       ↓
○-❷ → ❸    ❷-○ ← ❸

よって、閉路の部分だけを考えるとパターン数は $|❶||❷||❸| \times 2!$ 通りある。

このパターン数は、経由成分数ごとに、以下のようなDPでまとめて計算できる。

経由成分数  0         1            2            3
            1
                ↘ |❶|倍して加算
❶          1       |❶|
                ↘           ↘
❷          1     |❶|+|❷|     |❶||❷|
                ↘           ↘          ↘
❸          1  |❶|+|❷|+|❸|   |❶||❷|   |❶||❷||❸|
                               +|❶||❸|
                               +|❷||❸|

経由成分数 $l$ の閉路は $DP[l] \times (l-1)!$ 通りあり、同じ閉路が他の未指定頂点の決め方 $(N-1)^{k-l}$ 通りで1個ずつ生じる。

他の未指定頂点の中で閉路ができたとしても、「今、着目中の閉路が生じるパターン数」には関係ない。別々に数えることができる。

よって、各未指定頂点につき、とりあえず閉路は考えないで +1 して数えた後、上記の閉路を引けばよい。

ただし、経由成分数が1つ（自身の連結成分に繋ぐ）場合、この問題では自分自身は選べないため、実際に選べる頂点は1ずつ少ない点に注意。

• |❶|-1 + |❷|-1 + |❸|-1 + …

まとめると、

• 指定のある都市だけで、連結成分と、どんなパターンでも必要な辺数 $b$ を算出
  • $ans += b \times (N-1)^k$
• 各未指定頂点が含まれる連結成分のサイズ $s_1,s_2,...,s_k$ を求める
• 各未指定頂点につき、以下を算出
  • 自身の連結成分以外の頂点に繋ぐパターン数
    • $ans += (N-s_i) \times (N-1)^{k-1}$
  • 閉路のパターン数のDPを更新
    • $DP[1:] += DP[:M] \times s_i$
• 経由連結成分数 $l$（$l \ge 2$）の閉路について、
  • $ans -= DP[l] \times (l-1)! \times (N-1)^{k-l}$