abc151

考えたこと
- アルゴリズム的に工夫する路線もありそうだけど数式変形でも良さそう
- 部分集合のmaxであるmax(S)がmax(A)であるのはmax(A)を一つ以上含んでる時
- 逆にそうでないのは、c(x)をx以上の数の個数としてN-c(max(A))個からK個を選ぶ組み合わせの数　余事象を引く
- というわけでソートして数えればcがわかって、各数ごとのそれがmaxになる回数も求まる
  - 二項係数テーブルを作れば高速
- 差の和は和の差でmaxの項だけ先に話を求めてもよい
  - $\sum_{s \in S} (f (s) - g (s)) = \sum_{s \in S} f (s) - \sum_{s \in S} g (s)$
- minに関しても同様の議論ができて、引けば答えが得られる
公式解説
- 重複した値に関しての扱いが少し違う
- 同じ値A1, A2があった時、最大値がA1になるのは「A1を選んでA2以降からK-1個選ぶ」と「A2を選んでA3以降からK-1個選ぶ」の和、なるほど確かに背反だ

🪴 Quartz 4.0