Editorial - AtCoder Grand Contest 056

Contest Duration: 2021-12-04 21:00:00+0900 - 2021-12-05 00:00:00+0900 (local time) (180 minutes) Back to Home

Official

F - Degree Sequence in DFS Order Editorial by maroonrk_admin

頂点にDFS順で $1,2,\cdots,N$ と番号をつけます．

DFS で頂点 $1,2,\cdots,N$ と訪れることが可能なグラフを，よいグラフと呼ぶことにします．まず，よいグラフにおいては，各 $2 \leq v \leq N$ について，$v$ と何らかの頂点 $u$ ($u < v$) を結ぶ辺が存在します．

ここで，「各 $2 \leq v \leq N$ について，$v$ と何らかの頂点 $u$ ($u < v$) を結ぶ辺が存在する」ようなグラフをよさそうなグラフと呼ぶことにします．

よさそうなグラフを一つ取った時，各頂点の次数が同じよいグラフが存在することが示せます．

証明

$a \lt b \lt c \lt d$ に対して，辺 $(a,c)$ と辺 $(b,d)$ があれば，それらを削除し辺 $(a,d)$ と辺 $(b,c)$ に加えても，依然としてよさそうなグラフであり，各頂点の次数は変化しません．辺 $(u,v)$ に対して $(u-v)^2$ を対応させると，辺の値の和が操作によって常に増加するため，この操作を繰り返すといつか操作不可能な状態になります．こうして得たよさそうなグラフがよいグラフとなっていることは簡単に確認できます．

以下，よさそうなグラフの次数列としてありうるものを数えます．

正整数列 $a=(a_1,a_2,\cdots,a_N)$ が固定されたときに，条件を満たすかどうかを判定する方法を考えます．

まず $a_1 \leq M, \sum_{1 \leq i \leq N}a_i=2M$ が明らかに必要です．

次に，適当な $2 \leq v \leq N$ をとります．このとき，各 $u=2,\cdots,v-1$ について，$u$ と番号 $u$ 未満の頂点を結ぶ辺が必要なので，$v$ を端点としない辺が少なくとも $v-2$ 本存在します．この考察と，自己ループが存在しないという条件を合わせると，以下の不等式が導かれます．

$\sum_{i < v} a_i \geq 2(v-2) +1$　($+1$ は，頂点 $1,2,\cdots,v-1$ のいずれかと頂点 $v$を結ぶ辺の分)
$a_v \leq M-(v-2)$

これらは $a$ の必要条件ですが，実は十分条件でもあります．

証明

次のような貪欲を考えます．

$v=2,3,\cdots,N$ について，以下のことをする．
$1,2,\cdots,v-1$ の中から，$v$ と結ぶ頂点 $u$ を一つ選ぶ．この時，$a_u$ が最も大きい $u$ を選ぶ．$a_u$ と $a_v$ の値を $1$ 減らす．

この操作が終わった後，$a_i$ の最大値が高々 $M-(N-1)$ であることが言えれば，残りの $a_i$ に合わせて辺を貼ることができます．操作が終わった後，$a_i>M-(N-1)$ であったとします．このとき，$i<v$ であって，$v$ と $i$ を結んでいないものがあります．ここで $v$ と結んだ頂点を $j$ とおくと，貪欲の動きから，最終的に $a_j \geq a_i-1 \geq M-(N-1)$ であることがわかります．すると，$a_i+a_j > 2M-2(N-1) = \sum_{1 \leq k \leq N} a_k$ であることになり，矛盾します．よって示されました．

ここで，$b_0=a_1$, $b_i = a_{i+1}-1$ ($1 \leq i \leq N-1$) と定義すると，$b$ が満たすべき条件は

各 $b_i$ は非負整数
$\sum_{0 \leq i \leq N-1} b_i=2M-(N-1)$
$\sum_{j<i} b_j \geq i$　($0 \leq i \leq N-1$)
$b_i \leq M-i$　($0 \leq i \leq N-1$)

とまとめられます．

最後の条件を無視した場合に条件を満たす $b$ の個数を考えます．格子点上を進むパスとして，原点から出発し，$b_0$ 上に進み，$1$ 右に進み，$b_1$ 上に進み，$1$ 右に進み，$b_2$ 上に進み $\cdots$ というパスを考えます．このパスが満たすべき条件は，$y < x$ の領域を通らないことと，最終的に座標 $(N-1,2M-(N-1))$ に至ることです．これはカタラン数と同じ要領で数えることができます．

ここから，最後の条件を満たさないパスの個数を引くことを考えます．まず，最後の条件に違反するような $i$ の個数は，どの $b$ に対しても高々一つです．

証明

ある $i=p,q$ ($p \lt q$)に対して条件に違反したとします． $\sum_{j \lt p} b_j \geq p$, $b_p \geq M-p+1$, $b_q \geq M-q+1$ より，$\sum_{0 \leq i \leq N-1} b_i \geq p+(M-p+1)+(M-q+1)=2M-q+2 \gt 2M-(N-1) = \sum_{0 \leq i \leq N-1} b_i$ となり矛盾します．よって示されました．

最後の条件に違反する $i$ を一つ決め打ち，$K$ とおきます． $b_K$ の代わりに $b_K-(M-K+1)$ を用い，先ほどと同じようにパスの条件を考えると，以下の図のような領域を通るパスの個数を求める問題になります．

この領域は，長方形と三角形がくっついた形をしています．左下からスタートし，初めて長方形に触れる座標を $(x,k)$ とすると，$(0,0) \to (x,K-1)$ のパスの個数と $(x,K) \to(N-1,M-N+K)$ のパスの個数がそれぞれ数えられるため，$0 \leq x < K$ をすべて試すことで条件を満たすパスの個数を数えられます．

最後に，$K$ を動かしてこれらの値の和を取ることを考えます． $(x,K) \to(N-1,M-N+K)$ のパスの個数は $K$ に依存しないことを用ると，各 $x$ について，$x<K$ を満たすすべての $K$ に対する $(0,0) \to (x,K-1)$ のパスの個数の和が求まればよいことになります． $(0,0) \to (x,K-1)$ のパスの個数をコンビネーションの式で書くと，$K$ を動かして和を取った後の式も明示的に求められます．結局，各 $x$ について必要な値は $O(1)$ で計算できるため，全体で $O(N)$ 時間でこの問題は解けます．なお，$M$ が大きくないので，階乗の前計算などに $O(N+M)$ かけてもよいです．

posted:
last update: