Search on the blog

2011年1月30日日曜日

Facebook Hacker Cup Round 1C

えーと、Round 1Cがありました。
ドラゴンボールとワンピースを見たいという誘惑に耐えて、ちゃんと真面目に解きました。

ちょっと難しかったです。数学的な問題が多かったです。

1. Polynomial Factoring
最初見たとき、「Gauss-Jordan??」と思って、2.に行く。
2.を解いて、じっくり考えると、簡単な割り算に帰着できることに気付く。
以外とすんなり実装が終了し、F, Gが定数のとき, Fの次数 < Gの次数のときの例外ケースをテストしてちょっと直す。submit。

2. N-Factorful
まず、この問題に取り掛かる。
[a, b]内の整数xの中で素因数の数がちょうどn個である数がいくつあるか数えるだけです。
が、、
Straight-forwardなやり方は通じません。1 <= a, b <= 10^7なので、まともに毎回素因数分解していては間に合いません。
で、思いつかず。。取りあえず、エラトステネスで素数リストを作って、sqrt(x)までまわしてみるという方法を試みるも上手くいかず。これでも、O(x*sqrt(x))なのでキツイのか。。
悩む。焦る。。。
で、漸化式を思いつく。dp[x]をxの素因数の数とすると、

dp[x] = 0 (if x == 1)
dx[x] = 1 (if x is a prime number)
dp[x] = dp[x/p] + (x/p % p) (else)

で行けるじゃないか!ここで、pはxの素因数です。あとは、メモ化再帰にすれば時間どおりに間に合いました。(メモ化すれば、各xに対して定数時間で解が出るので、O(x)。)答えはあってるかどうかまだ不明~。

3. Risky Slide
2. が無理そうだと思い、ちょっと3.を読む。
これは、DFSかDPっぽいと思う。PKUの「滑雪」と同じような雰囲気だ。。
これは解けそう!
と思って、テストケースを見るが、意味不明。。
問題がよく読めてないのでは。。英語力が足りない・・・。挙句の果てに辞書を引いて単語の意味を調べる始末。。ひどい・・。

[追記]
やった~。1.2.とも通ってました!
次はRound2という名のSemi-final。T-shirt取れるようベストを尽くします!

0 件のコメント:

コメントを投稿