Weird LIS(AtCoder Grand Contest 055)
問題概要
ある $1$ から $N$ までの順列 $P$ があって、$P$ の $i$ 要素目を取り除いたときのLISの長さを $A_i$ とする。$2\leq A_{i}\leq M $ を満たすような $A$ は何通りあるか。
事実
$P$ のLISが $K$ だとすると、$A_i$ は $K$ か $K - 1$ である。また $K$ であるとき、 $i$ 番目の要素を使わないような長さ $K$ のLISが存在する。 $P$ の要素は3種類に分類できる。
・取り除くとLISの長さが短くなる要素
・取り除いてもLISの長さは変わらないが、LISに含まれることもある要素
・LISに含まれることはない要素
解法
$A$ の全ての要素が等しい場合とそうでない場合に分けて考える
全ての要素が等しい場合
以下のようにして $A_i = K \space (2\leq K\leq N/2)$ を満たす $A$ を作ることができる。
$2,1,4,3,...,2K,2K-1$
以下のようにして $A_i = N - 1$ を満たす $A$ を作ることができる。
$1,2,...,N-1,N$
全ての要素が等しい場合以外
$2\leq A_{i}$ の条件より、$2 < A_i$ を満たす要素がある。これは $P$ のLISの長さが $3$ 以上であることを意味する。 また、$A$ に異なる要素があるため、$P$ の中に取り除くとLISの長さが短くなる要素を $1$ 個以上、それ以外の要素を $1$ 個以上含む必要がある。
LISの長さが短くなる要素 $X$ 個とそうでない要素を割り振ったとき、LISの長さは $X$ 以上である。LISの長さを $X$ にしたければそうでない要素を全てLISに含まれることはない要素にすれば良いし、$X+n$ にしたければ、そうでない要素のうち左から貪欲に連続した二つをLISに含まれることもある要素にすれば重複なく数えられる。
これを数えることを考える。
以下のような遷移を行いつつ通り数を数えると良い。
①取り除くとLISの長さが短くなる要素を一つ追加する。
②取り除いてもLISの長さは変わらないが、LISに含まれることもある要素を二つ追加する。今後②と③を使用できなくするかわりに④を使用できるようにしても良い。
③LISに含まれることはない要素を一つと取り除くとLISの長さが短くなる要素をこの順番で一つずつ追加する。
④LISに含まれることはない要素を一つ追加する。
その際、以下のような情報を持っておく
・追加した要素の数
・LISの長さ
・①か③を行ったかどうか
・①以外を行ったかどうか
・④を行うことができるかどうか
