AtCoder Beginner Contest 151 E - Mac-Min Sums
自分がやった解法じゃうまくいかない理由がわからない。
時間がある時に、見直して間違いがわかったら追記する。
問題のリンクはしたから。
提出コード(間違い)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
int n, k;
cin >> n >> k;
COMinit();
vector<long long> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.begin(), a.end());
long long ans = 0;
for(int i=0;i<n-1;i++) {
ans += (a[i+1]-a[i]) * (COM(n, k) - COM(i+1, k) - COM(n-i-1, k));
ans %= MOD;
}
cout << ans << endl;
}
提出コード(正答)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
int n, k;
cin >> n >> k;
COMinit();
vector<long long> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.begin(), a.end());
long long ans = 0;
for(int i=0;i<n;i++) {
ans += a[i] * COM(i, k-1);
ans -= a[i] * COM(n-i-1, k-1);
ans %= MOD;
}
cout << ans << endl;
}
経過と感想
時間をだいぶかけた(1時間ほど)。普通に計算すると死ぬので死なないようにどうするかずっと考えた。結局最初の不正解コードまでしか辿りつかなかった。Editorialを見てコードを書き正答。
間違いのコードを修正してACしたかったが、間違いがどこなのかわからなかった。また戻ってきた時に間違いを探したい。まあ良い線までは行ってたのではないか。
追記用