ferinの競プロ帳

競プロについてのメモ

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]をあわせるのが効率がよいので、貪欲に合わせていく。