ドラゴンボールとワンピースを見たいという誘惑に耐えて、ちゃんと真面目に解きました。
ちょっと難しかったです。数学的な問題が多かったです。
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 件のコメント:
コメントを投稿