Hatena::Grouptopcoder

hotpepsiの練習帳

2012-03-04

SRM 535 Div2

03:20

Easy (250) FoxAndIntegers

問題

  • A-BとB-CとA+BとB+CからA、B、Cを求める。

方針

Medium (500) FoxAndGCDLCM

問題

  • 最大公約数Gと最小公倍数Lが与えられる。
  • GとLを満たす数AとBの和の最小値を求める。

方針

  • LがG未満とかのケースは不能としてはじく
  • ぐぐるとA×B=G×Lだが、直接役には立たない
  • 別の表現をするとA=x×G、B=y×G、x×y×G=L
  • すなわちL÷G=x×y
  • (xとyの和の最小値)×Gが答え
  • xとyの組み合わせを因数分解して全探索するのは面倒
  • 範囲は1~sqrt(x×y)、たかだか10^6だから全数探索すればいいや
  • sample4が合わない
  • AとBのGCDがGになるためには、xとyは互いに素、つまりxとyのGCDは1
  • 合った!
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndGCDLCM.cpp

Hard (1000) FoxAndSorting

問題

  • 0から1000000000000000000までの数を、桁の数値の和で、和が同じもの同士は辞書順で並べる。
  • idx番目の数値を求める。

方針

結果

oo- 240.45 + 296.80 = 537.25pt 63rd 1196 -> 1258

div1! 100位以内に入れればいいやと思ってたので目標はクリア。

easyは手抜き実装すると落ちるので、良いdiv2easyだと思った。実際偶数チェックしてない人とか、引数チェックをコピペミスしてちゃんと書けてない人とかいた。撃墜は遅くて間に合わなかった。

mediumは自信ないのでGCDとLCMをぐぐったら基本的すぎてあまり載ってなかった。和が最小になるのは、xy=aとx+y=bの接点ぽい感じでxとyが近い数になるとき。なのでsqrt(xy)から試行すればminで更新する必要ないかも。あとGCCには__gcdがあるのでそれ使えばよかったとか。点数はいまいちだけど最終的にはよかった。challengeは、単純なバグ持ちの人は即落とされて、バグってはいるけどサンプルは通るみたいな人だけ残ったので、控えた。

hardはopenしたけど全く見当がつかなかったので残り時間はmediumを見直した。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20120304