hotpepsiの練習帳

SRM 535 Div2

03:20

Easy (250) FoxAndIntegers

問題

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

方針

• 安全にいく
• (A-B)と(A+B)を足したら2Aになる。BとCも同様
• 2A、2B、2Cが偶数かつ、引数の条件を満たすかチェック
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndIntegers.cpp

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番目の数値を求める。

方針

• DPぽい
• analysisを写経
• [ある桁数以下][和がS]のテーブルを作成
• S未満までの位置がわかったら、1桁ずつ確定させていく
• その際、同じテーブルが使える
• これは自力で書くの無理
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_535/FoxAndSorting.cpp

結果

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を見直した。