ABC151 E - Max-Min Sums
問題原文
問題要旨
有限個の整数からなる集合 に対し、 とする。
個の整数 が与えられる。このうちから 個選び、それを とする。
全ての 個 の選び方について、 を計算し、その総和を で割ったあまりを求めよ。
解法
こういうのは、「各数が最大値/最小値としてカウントされるような選び方は何通りあるか?」を考えればいい。
ある が最小値になるような選び方を考えた時に、 ある が最大値になるような選び方を考えていることにもなるが、
最小値と最大値のパターンを別個に計算すれば問題ない。重複があってもOK。
実装
途中で大きい順に並び替えれば、最大値については最小値のコードのコピーでいける。
N, K = map(int, input().split()) A = sorted(list(map(int, input().split()))) MOD = 10 ** 9 + 7 ans = 0 # 各Aiについて、それが最小値になるような選び方が何通りあるかを求めながら計算 for i in range(N - K + 1): ans -= A[i] * nCr(N - i - 1, K - 1) % MOD ans %= MOD # 各Aiについて、それが最小値になるような選び方が何通りあるかを求めながら計算 A = A[::-1] # 大きい順に並び替え! for i in range(N - K + 1): ans += A[i] * nCr(N - i - 1, K - 1) % MOD ans %= MOD print(ans % MOD)
感想
9分で解いたらしい。えらい。
- 求めたいものを分けて考える
- 各要素について、何回数えられるかを考える
考え方はド典型なので、常に引き出せるようにしたいですね。