ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Regular Contest 104 E - Random LIS

AtCoder プログラミング競技プログラミング

公式解説とは違う解法です（たぶん）。

解法

あり得る全ての場合に対するLISの長さを合計して、全事象数 $\prod A_{i}$ で割ることにします。

取っ掛かりが非常に掴みにくい問題ですが、 $1 \le N \le 6$ という制約から何らかの全探索をやることを目指してみます。

座標圧縮とゾーン分け

座標圧縮をします。数列 $A$ に含まれる値の種類数を $M$ として、 $A$ に $0$ を加えてソート・重複排除した数列を $p_{0}, p_{1}, ..., p_{M}$ （ $p_{0} = 0$ ）と置きます。するといずれかの $X_{i}$ が取り得る正整数の範囲は、 $(p_{0}, p_{1}\rbrack$ , $(p_{1}, p_{2}\rbrack$ , $(p_{M-1}, p_{M}\rbrack$ という半開区間で表される $M$ 個のゾーンに分けることができます。それぞれの $X_{i}$ は最大値 $A_{i}$ の値に応じて、このゾーンのうち前からいくつかに属することになります。

まず、 $X_{1}, ..., X_{N}$ がそれぞれどのゾーンに属するかを全探索します。これは $M^{N}$ 通りの全探索をすれば良いです。このとき $X_{i}$ がそのゾーンに属することができない（ $A_{i}$ が区間の下端以下である）ような $i$ がある場合、そのパターンは無視します。

ゾーン内部の大小関係

その上で各ゾーンについて、その内部での大小関係を全探索します。このとき複数の要素が同じ値を取り得る場合があるので、それも含めて全探索する必要があります。

ゾーンに含まれる要素の数が $n$ であるとき、数列 $\lbrace x_{0}, x_{1}, ..., x_{n-1}\rbrace$ の大小関係の列挙は、

長さ $n$ の非負数列で、その最大値が $m$ であるときに $0, 1, ..., m$ が全て含まれているもの

として列挙できます。この数列の個数が公式解説に書かれている Ordered Bell Numberです。例えば $n=4$ であって非負数列が $\lbrace 2, 0, 1, 0\rbrace$ であれば、大小関係は $x_{1}=x_{3} \lt x_{2} \lt x_{0}$ です。

この数列を予め要素数 $n=1, ..., N$ のそれぞれについて列挙しておくと、ゾーン分けを固定した後にそれぞれのゾーン内の大小関係を全探索できます。

場合の数とLISの長さ計算

ゾーン分けとゾーン内部の大小関係を全探索したら、そのパターンに該当する場合の数とLISの長さを計算して合計します。

場合の数は、各ゾーンで使う整数の選び方を計算した積になります。 $j$ 番目（0始まり）のゾーンに含まれる整数は $p_{j+1}-p_{j}$ 個であり、その中で $k$ 種類の整数を使う場合、その選び方は $_{p_{j+1}-p_{j}}C_{k}$ 通りです。

LISの長さは、ゾーン分けとゾーン内部の大小関係に応じて $X$ と大小関係が等しい数列を適当に作り、そのLISを求めれば良いです。例えば小さい方から $j$ 番目のゾーンで小さい方から $k$ 番目の値を $10j+k$ とすれば $X$ と大小関係が等しくなります。

計算量の評価は難しいですが、 $N=6$ で $A_{i}$ が全て異なる入力ケースにおいてパターン数を実際に計算すると $39208$ 通りでした。なのでこの中で毎回LISのアルゴリズムを回しても問題ないでしょう。

ACコード

Submission #17196593 - AtCoder Regular Contest 104

実装はなかなかの筋肉系です。