Topcoder SRM 400

Topcoder

div1 easy

問題

数字n(2<=n<=10^18)が与えられる。 n = p^q (p:素数 q:2以上の整数)となるようなp,qが存在するか判定し、存在すればp,qを返す。

解く
  • q>=2だからpは10^9以下
  • 2^60>10^18だからqは60以下
  • n^(1/i)を求めて、n^(1/i)が整数であり素数であればp=n^(1/i) q = iが答え
  • 整数かどうかはn^(1/i)を整数に丸めたものをi乗してnに一致するかを調べる。
  • あれ……WAだ…。
  • どうやらpow(n,1/i)を丸めるときに誤差死してたみたい。
  • (long long)(pow(n,1/i)+0.05)に書き換えた

div1 middle

問題

文字列のi番目からj番目までの部分を反転する操作をr(i,j)と書き、その操作列r(i1,j1),r(i2,j2)...をrevasal chainとよぶ(ただしi1>=i2>=... , j1<=j2<=...) initとgoalが与えられるので、initからgoalを作るrevasal chainの最小サイズを求める。

解けない

greedyでやったけどだめだったみたい。(正解率20％という恐ろしい問題)
DPでやればいいのだけど、解説を見てもよくわからなかった。悲しい。