Codeforces Round #429 (Div. 2) C. Leha and Function
問題ページ
Problem - C - Codeforces
概要
関数 F(n, k)を次のように定める。
集合{1,2,…,n}からk要素を選んだ部分集合を全て列挙する。各部分集合の値をその部分集合の最小の要素の値とするとき、この値を平均をF(n, k)とする。
\sum F(a[i], b[i]) が最大になるようにa[i]を並び替えろ。
解法
実際にF(n, k)の値がどうなるか試してみる。
F(3, 1) {1} {2} {3} (1+2+3)/3 = 2
F(3, 2) {1, 2} {1, 3} {2, 3} (1+1+2)/3 = 4/3
nが大きく、kが小さいほどF(n, k)の値は大きい。
a[i]が大きいものに小さいb[i]をあわせるのが効率がよいので、貪欲に合わせていく。