ARC104-E Random LIS

↓これ

atcoder.jp

  まず, これは期待値を求める問題れふが, すべてのXについてLISの長さを求めて, その総和を最後にA_1 \times A_2 \times ... \times A_Nで割ることにしまふ(ここは人によって楽に感じる方法が違いそう).

 さて, Xの各値は(A_iの値を無視すれば)1以上10⁹以下の値を取りまふ. これは範囲が広くて扱いづらいので, いくつかのグループに分けまふ. 例えば, A = \{1,10,3,10 \}の時, 

  • グループ1:1以上1以下の整数
  • グループ2:2以上3以下の整数
  • グループ3:4以上10以下の整数

としまふ. ここで, X_1,X_2,...,X_Nのいずれについても, 「あるxが存在して, グループxに属する整数はvalidで, グループ(x+1)に属する値はinvalidである(あるいは, グループ(x+1)が存在しない).」というのが成り立つようにしまふ. グループの数は高々N個れふ.

 グループを定義したのち, i=1,2,...,Nの順に, 次のことを決めまふ.

  • X_iの値がどのグループに属する整数か
  • X_iの, 以前に決めた同グループ内の値との大小関係(大きいか, 小さいか, 同じか

 すべて決まると, たとえば次のように集合の列がグループの個数だけ出来まふ.

  • グループ1: \{  \{ 4 \} \{ 1,3 \} \}
  • グループ2: \{ \}
  • グループ3: \{ \}
  • グループ4: \{ \{ 2 \} \}

 これは,  X_1,X_3,X_4がグループ1に属している上に X_4 \lt X_1 = X_3が成り立ち, X_2がグループ4に属していることを表しまふ.

 すべて決まったら, LISの長さを求めまふ. これは, 定めた大小関係等をもとに適当に0,1,2,...と値を与えて単に求めれば良いれふ.

 次に, 定めた大小関係やグループに矛盾しないようなX_1,...,X_Nの値の通り数を求めまふ. グループaに対応する集合の列に集合がx個含まれるとすると, グループaに属する整数から相異なるx個の整数を選ぶことになりまふ. これは, コンビネーションの計算で何とか出来まふ.

 以上で考察は完了したので, 実際に決め方すべてを列挙してやりまふ. これは, 再帰的に現在見ている値をどのグループに入れるか・そのグループ内のどこに入れるかを全部調べれば良いれふ.

 計算量れふが, 各値をN個のグループに入れ, 順序を決めるのでO(N!N^N)回LISを求めることになりそう……?れふ. 実際は順序を決めたうえ値が同じパターンも考えるので少し増えそうれふが, グループの入れ方が順序に矛盾したりもするのでその分削減されて……という感じでちゃんと解析するのが大変れふ. ……が, 実際に再帰の終端に何度到達するか数えると大したことないのでTLEの恐れはないと分かりまふ.

↓提出コード

atcoder.jp