kmjp's blog

競技プログラミング参加記です

TopCoder SRM 730 Div1 Hard ExpectedMinimumPower、Div2 Medium ExpectedMinimumPowerDiv2

こういう言い換え系さっと思いつかないな。
https://community.topcoder.com/stat?c=problem_statement&pm=14813
https://community.topcoder.com/stat?c=problem_statement&pm=14795

問題

整数N,Xが与えられる。
1~Nの整数のうち、X個を当確率で選ぶ場合を考える。
選んだX個のうち最小値がSとすると、選んだX個の値のスコアは2^Sとなる。

Div2ではスコアの期待値、Div1では全組み合わせのスコアの総和を求めよ。

解法

Div2はN,Xが小さいので、Sを総当たりし、S以外の要素は[S+1,N]から(X-1)個選ぶ点に着目して2^Sの平均値を求めればよい。
問題はDiv1である。
Xは大きくないがNがとても大きく、総当たりはできない。

真面目に数式変形をすると大変だが、問題文を言い換えると簡単になる。
元ツイートが削除済みなので出所の言及は避けるが、以下のように考えるとよい。

X個の最小値がSのときスコアが2^Sになるという。
これはSより手前の要素について、さらに選ぶ・選ばないを2^(S-1)通り考えると、個々の組み合わせについてスコアが2ずつ得られることになる。
さらに言い換えると、NからX個以上の値を選ぶと、それは選んだうち上からX個目の要素Sにおける手前の選びかた2^(S-1)通りのうちの1個を選んだことと同じである。

よって、求めるのはN個から任意の個数を選ぶ組み合わせ2^Nから、(X個未満を選ぶ組み合わせ*2)を引くことである。
あとはCombinationを求めながら2^Nから値を引いていくだけ。

ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class ExpectedMinimumPower {
	public:
	int findExp(int n, int x) {
		ll ret=modpow(2,n);
		
		ll c=1;
		for(int i=0;i<x;i++) {
			ret=(ret+mo-c)%mo;
			c=c*n--%mo*modpow(i+1)%mo;
		}
		return ret*2%mo;
		
	}
}

まとめ

こういうの思いつくのは経験なのか…?
本番はWikipediaスターリング数のページ見つつグダグダしてた。