AtCoder ABC 151 E - Max-Min Sums (500 点)

初めてのABC

問題へのリンク

Dは飛ばして、EをTLEでフィニッシュ

問題概要

• 定義：f(X) = max X - min X (Xは有限個の整数からなる集合)
• N個の整数A_1,....,A_Nが与えら、そのうちK個を選び集合Sを作る。このとき、A_iが同じ値でも添え字iが違う場合は区別する。
• 上記の組み合わせ全てについてのf(S)の合計を求めよ。
• 大きな値に備えて、答えはmod 10⁹ + 7で出力すること。

制約

• 1<=N<=10⁵
• 1<=K<=N
• |A_i|<=10⁹

解法1（本番でTLEしたやつ）

組み合わせを単純にArray#combinationで用意したが、N,Kが大きくなると爆発的に組み合わせが増えるためそこでダメだった。

n, k = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

combos = nums.combination(k).to_a

sum = 0

combos.each do |combo|
  f = combo.max - combo.min
  sum += f
  sum %= 1000000007
end

puts sum

解法2

TBD

課題を理解した上で再度解く

課題

解説や参考記事を見てると色々知識が足りてないので課題となるトピックと参考記事をリスト化しておく。

• 公式解説

• AtCoder ABC 151 E - Max-Min Sums (500 点) - けんちょんの競プロ精進記録

• 2項係数を求める

  • よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
    • ユークリッドの互除法、拡張: 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
    • フェルマーの小定理: フェルマーの小定理の証明と使い方 - Qiita

感想

強くなって戻ってくるぞ！