SRM400

250

n(<=10^18)が与えられた時n = p^q(p素数、q>=2)の形で表せるかどうか答えよ、表せるならば{p,q}も求めよという問題。
qを固定したらp=exp(log(n)/q)で求まるので、これで出して素数かどうか確認する。

500

1,0からなる文字列s1,s2が与えられたときにs1の部分文字列をひっくり返していくという操作を繰り返してs2に至るまでの最短手数を答えよという問題、ただしs1[a]からs1[b]までをi回目にひっくり返す操作をr(a_i,b_i)と書いたとき,a_1 <= a_2 <= ... a<=i , b_1 >= b_2 >= .. b>=iが成り立ってなければならない、貪欲でいけると思い込んでしまって失敗。

1000

n種類の景品があって、ジュースを買うたびにランダムにどれか1個の景品がつくとする。このときk種類の景品を集めるために必要なジュースの期待本数を答えよという問題。
この値は

となる、ただしn,k<10^18なのでうまい近似をしてやる必要があるのだが単純に

で(HはHarmonic number)Hを4次ぐらいまで近似しただけだと精度的に微妙になるようです。