2008年05月

久々に参加できる時間帯だったので参加．でもボロボロ．解き方わかっても倍精度の壁とかにぶち当たってシステムにはじかれる．多倍長精度が恋しい．

250点問題：与えられた数nが，素数pと2以上の整数qでn=p^qとなるかどうか．最大でn=10^18程度なのでq=60くらいからnのq乗根を丸めてq乗して元に戻ったら素数判定して終わり．根の素数判定は10^5程度のループで終了するので計算量的には問題ない．が，丸め誤差を気にしつつ面倒なので根+1のq乗もついでに計算してたらここでオーバーフローした．そしてオーバーフローした結果が丁度nに一致する入力が待っていたのでSystemTestで落ちた．

500点問題：ネストしたリバース操作で0/1文字列を目的のならびに直したい，最小手数はいくつか？　面倒なので両端をいっぺんに揃えるように貪欲にやったら失敗．やっぱ片方のみを揃えるパターンも考えないとダメなのね．

1000点問題：n種類のコードが一つのビンに一つ付いている．k種類のコードを手に入れるにはどれくらいのビンが必要か？　たぶんビンは無限にあるのでしょう．確率の問題．すでに(i-1)種類持っているときにi種類目のコードを手に入れる確率は(n-i)/n なので，必要なビン数はn/(n-i)．後はこれをi=1..kで足しこんだら終わり．nが10^18とかいっているので，Harmonix Numberの近似式を使って求めることになる．が，doubleで計算してたせいでnが大きくてkが小さいときに精度が足りなかったらしい．BigDecimal使えば問題ない．