ぷの日記

作問・解説・日記など

へやわり！(AOJ 2829) 解説

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 19 日目の記事です

問題

https://onlinejudge.u-aizu.ac.jp/problems/2829

順を追って考察していけば解けるような数え上げの問題です

問題概要

整数 $N$ と長さ $N$ の配列 $A$ が与えられます

次の条件を全て満たす配列の集合として考えられる最大の大きさを $mod$ $1000000007$ で答えなさい

集合に含まれる任意の配列は以下の条件を満たす

・長さが $N+1$ である

・配列を $B$ とする時、 $B$ には $0$ から $N$ までの整数が $1$ つずつ含まれる

・各 $i (1 \leq i \leq N+1 , B_i \neq 0)$ について、 $B_{i-1},B_{i+1}$ のいずれかは $A_{B_i}$ に等しい

・ $B$ の $0$ である要素と $0$ でない要素のいずれかとを $swap$ した時、新しくできる配列は集合に含まれない。(この操作を、以下 $swap$ 操作と呼ぶ)

解法

各 $i$ について $i$ から $A_i$ へ辺を貼ったグラフを考えると、(有向辺を無向辺と考えた時の)各連結成分は以下のようになっている必要がある

また、 $swap$ 操作において新しくできた配列が集合に含まれている時、新しくできた配列も条件を満たしているため、 $swap$ 操作において問題であるのはパターン $1$ の場合のみであることがわかる

さて、ここで $1$ つ大事になってくることが、この操作において連結成分のブロックの並びは変わらないということである

例えば、初め $B = {{1,3,2},{0},{4,5},{6,7}}$ であった時、操作をしても $B = {{1,3,2},{5,4},{0},{6,7}}$ のように、 ${{1,3,2},{4,5},{6,7}}$ の並びは変わらない

観察

上の $4$ つの配列について、上下に隣接するもの同士が同じ集合に入っていてはならない → $2$ つは同じ集合に入れることができる

この観察を元にすると、ある連結成分のブロックの並びにおいて、集合に含まれるその並びの配列の個数の最大値がわかる。

パターン $2$ であるような連結成分の個数が $0$ 個であるような場合を除いておくと、 $0$ を挿入できる場所は以下の $2$ つの場合に分けることができる

$1.$ [配列の端][パターン $1$ が $x$ 個][パターン $2$ ]

$2.$ [パターン $2$ ][パターン $1$ が $x$ 個][パターン $2$ ]

いずれについても、 $0$ は最大で $floor(x/2)+1$ 個入れることができる。

よって、それぞれ $x$ の値で主客転倒して答えを求めてやり、足し合わせれば良い。

具体的には、パターン $1$ の配列の数が $a$ 個、パターン $2$ の配列の数が $b$ 個あり、パターン $1$ の配列が $x$ 個連続しているようなものについて

$1.$ $(floor(x/2)+1)$ $\times$ $binom(a,x)$ $\times$ $b$ $\times$ $2$ $\times$ $(a+b-x-1)!$ $\times$ $x!$ $\times$ $2^{a+b}$

$2.$ $(floor(x/2)+1)$ $\times$ $binom(a,x)$ $\times$ $binom(b,2)$ $\times$ $2$ $\times$ $(a+b-x-1)$ $\times$ $(a+b-x-2)!$ $\times$ $x!$ $\times$ $2^{a+b}$

を足してやれば良い

計算量は $O(N)$ である

提出

onlinejudge.u-aizu.ac.jp

終わりに

こういう問題、好きです

アドカレ大幅に遅刻してすみません