kojingharangの日記

Facebook Hacker Cup Round1 A - Card Game

19:32 |

• N個の数が与えられる。そこからK個選んで、その中で最大の数を得点とする。K個取るすべての組み合わせについて、得点の合計を mod 1000000007 で求める問題。
• 1≦K≦N, N≦10000, 0≦a[i]≦2*10^9

• 最大の数を決めると、それが最大になるような選び方は Combination(それより小さい数の個数, K-1) 通りある。ので、全ての最大の数についてその数 * Combination(...) を足したものが答え。
• 「それより小さい数の個数」は最初に１回ソートすればわかる
• Combination の分母の部分は 1000000007 は素数なのでフェルマーの小定理より x * x^(1000000007-2) ≡ 1 (mod 1000000007) であることを使った。

• wrong answer

• しまった ans に足していくところで mod をとってなかった
• 冷静に出力を見ると明らかに 1000000007 より大きな数が出てるからおかしいと気づくことはできたかもしれないけど、気づかないなぁ。

• ↓正解者の答えと一致した版

static const ll MODVAL = 1000000007;
ll MODADD(ll x, ll y) { return (x+y)%MODVAL; }
ll MODSUB(ll x, ll y) { return (x-y+MODVAL)%MODVAL; }
ll MODMUL(ll x, ll y) { return (x*y)%MODVAL; }
ll MODPOW(ll x, ll e) { ll v = 1; for(;e;x=MODMUL(x,x),e>>=1) if(e&1) v = MODMUL(v, x); return v; }
ll MODINV(ll x) { return MODPOW(x, MODVAL-2); }

#define MAXN 10010
ll facts[MAXN];
ll inv_facts[MAXN];

ll MODCOMB(ll n, ll r) {
	assert(0<=n && n<MAXN);
	assert(0<=r && r<=n);
	return MODMUL(facts[n], MODMUL(inv_facts[r], inv_facts[n-r]));
}

int main() {
	facts[0] = 1;
	inv_facts[0] = MODINV(facts[0]);
	RANGE(i, 1, MAXN) facts[i] = MODMUL(facts[i-1], i);
	RANGE(i, 1, MAXN) inv_facts[i] = MODMUL(inv_facts[i-1], MODINV(i));
	
	REP(i, MAXN) assert(MODMUL(facts[i], inv_facts[i])==1);
	
	int T;
	cin>>T;
	REP(ttt, T) {
		ll N, K;
		cin>>N>>K;
		VI w(N);
		REP(i, N) cin>>w[i];
		sort(ALL(w));
		ll ans = 0;
		REP(i, N) {
			if(i-(K-1)>=0) {
				//ans += MODMUL(w[i], MODCOMB(i, i-(K-1)));           // だめ
				ans = MODADD(ans, MODMUL(w[i], MODCOMB(i, i-(K-1)))); // OK
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする