Codeforces Round #429 (Div. 2) C. Leha and Function
長さnでmin(a[i])>=max(b[i])であるような数列a[i], b[i]が与えられる。F(n, k)を Σ[S⊆{1, 2, ... , n}, #S=k] min(S) / nCk (つまり、k個の要素からなる部分集合の最小値の期待値) とする時、a[i]を並び替えて、ΣF(a[i], b[i]) を最大化したい。最大値を与えるa[i]の並び替えを一つ求めよ。
実験してみるとわかるが、F(n, k)はnを固定したときにkの単調減少関数、kを固定したときにnの単調増加関数になっている。(漸化式を立てれば一応証明はできる)
更にこちらは実験でしか確かめていないが、F(n1, k1)+F(n2, k2)について、n1>n2のとき、k1<k2の場合のほうがk1>k2のときよりも大きくなる。そのため、a[i]とb[i]はそれぞれ昇順と降順で組み合わせるのが最適とわかる。
ほとんど実験だけの問題であるが、あとはソートして組み合わせ、元のb[i]の順序で出力すればよい。O(n logn)。
