ARC104-E Random LIS
↓これ
まず, これは期待値を求める問題れふが, すべてのについてLISの長さを求めて, その総和を最後にで割ることにしまふ(ここは人によって楽に感じる方法が違いそう).
さて, の各値は(の値を無視すれば)1以上10⁹以下の値を取りまふ. これは範囲が広くて扱いづらいので, いくつかのグループに分けまふ. 例えば, の時,
- グループ1:1以上1以下の整数
- グループ2:2以上3以下の整数
- グループ3:4以上10以下の整数
としまふ. ここで, のいずれについても, 「あるが存在して, グループに属する整数はvalidで, グループに属する値はinvalidである(あるいは, グループが存在しない).」というのが成り立つようにしまふ. グループの数は高々個れふ.
グループを定義したのち, の順に, 次のことを決めまふ.
- の値がどのグループに属する整数か
- の, 以前に決めた同グループ内の値との大小関係(大きいか, 小さいか, 同じか
すべて決まると, たとえば次のように集合の列がグループの個数だけ出来まふ.
- グループ1:
- グループ2:
- グループ3:
- グループ4:
これは, がグループ1に属している上にが成り立ち, がグループ4に属していることを表しまふ.
すべて決まったら, LISの長さを求めまふ. これは, 定めた大小関係等をもとに適当に0,1,2,...と値を与えて単に求めれば良いれふ.
次に, 定めた大小関係やグループに矛盾しないようなの値の通り数を求めまふ. グループに対応する集合の列に集合が個含まれるとすると, グループに属する整数から相異なる個の整数を選ぶことになりまふ. これは, コンビネーションの計算で何とか出来まふ.
以上で考察は完了したので, 実際に決め方すべてを列挙してやりまふ. これは, 再帰的に現在見ている値をどのグループに入れるか・そのグループ内のどこに入れるかを全部調べれば良いれふ.
計算量れふが, 各値を個のグループに入れ, 順序を決めるので回LISを求めることになりそう……?れふ. 実際は順序を決めたうえ値が同じパターンも考えるので少し増えそうれふが, グループの入れ方が順序に矛盾したりもするのでその分削減されて……という感じでちゃんと解析するのが大変れふ. ……が, 実際に再帰の終端に何度到達するか数えると大したことないのでTLEの恐れはないと分かりまふ.
↓提出コード