Search on the blog

2011年2月3日木曜日

One of the Best Hackers in the World!

Facebook HackerCupのsemifinalが迫ります。
finalには行けなくてもT-shirtが欲しいです。
ロゴはこんな感じ。

"You are one of the best hackers in the world.
certified by Facebook"

やばい。。

今日は1Aの問題を解いてみた。「Wine Tasting」という問題。
g本ワインを試飲して、c本以上正しく正解する場合のパターン数を求めよ。という問題。
Ai = {1,2,3,4, ... g}と定義すれば、Ai == iとなる要素数がc以上になる場合の数列のパターン数を求めよ。
という問題に帰着できる。

SjをAi==iとなる要素数がj個である場合のパターン数と定義すると、求める値が
Sum_{c <= j <= g} Sj
となるのは自明。

あとは、Sjの求め方を考えればよい。

まず、Ai==iとなる場所を選ぶパターンは、gCjである。

次に、残ったg-j個をAi == iとならないように並べる。
このパターン数をptn(j)とおくと、
ptn(j) = (j-1) * (ptn(j-1) + ptn(j-2))という漸化式が成り立つ。
これは、難しいので解説。(これに気付くのに2日かかった。。。この問題解いた人は閃いたのか?それとも知っていたのか??)
j-1個のAi==iとならないパターン{A1, A2, ..., Aj-1}の後ろにAjをおく。
Ajと任意のAk, 1<=k<=j-1を交換してもこの数列は、Ai == i, 1<=i<=jとならない。
よって、(j-1) * ptn(j-1)のパターンを数え上げた。

次に、Ajとスワップする要素に関しては、最初の段階でAi==iとなっていても問題ない(スワップするため)。Ai==iとする場所をj-1個の要素から選び、残りのj-2個を並び変えるパターンは、
(j-1) * ptn(j-2)

よって、前述を2つを足して、
ptn(j) = (j-1) * (ptn(j-1) + ptn(j-2))
となるわけである。

むずっ。。
ここまで出来れば、実装は簡単。
コンビネーションは「パスカルの三角形」で計算すればOK。
残ったものの並び変えも、DPで計算すればOK。
あとは、MODULOの比較的大きいため、64bitに入れないと掛け算でオーバーフローするので注意。
ソースはこちら。(今回は何回もチャレンジして書きなおしたため、最終的なソースは結構きれい。。)

#define MOD 1051962371
uint64_t cmb[126][126];
uint64_t ptn[126];

int main() {
cmb[0][0] = 1;
FOR (i, 1, 126) cmb[i][0] = 1;
FOR (i, 1, 126)FOR (j, 1, i+1)
cmb[i][j] = (cmb[i-1][j-1] + cmb[i-1][j]) % MOD;

ptn[0] = 1, ptn[1] = 0;
FOR (i, 2, 126) {
ptn[i] = (i-1) * (ptn[i-1] + ptn[i-2]);
ptn[i] %= MOD;
}

int n, g, c;
cin >> n;
while (n--) {
cin >> g >> c;
uint64_t ret = 0;
FOR(i, c, g+1) {
int t = cmb[g][i] * ptn[g-i] % MOD;
ret = (ret + t) % MOD;
}
cout << ret << endl;
}

return 0;
}







0 件のコメント:

コメントを投稿