解いた問題のソースコードと解説など。


小数を扱う

POJ 2613 Choose and divide

問題 二項係数同士の除算C(p,q)/C(r,s)を行い、小数点第五位までを出力せよ。p,q,r,sは10000未満で、答えは常に1e7を超えないとしてよい。 やりかた 素直にやると精度が落ちて誤差死する。なので優先度付キューを2つ用意して式の分母と分子の数字をそれぞれ…

SRM 540 Div2 Hard FractionInDifferentBases

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11135&rd=14732 P / Q(既約とは限らない)をX進数で表現した時に割り切れないとする。AからBの間にこのようなXはいくつ存在するか。 やりかた Editorialを参考にしました。まずP、Qをこれらの最…

SRM 586 Div1 Easy PiecewiseLinearFunction

問題 http://community.topcoder.com/stat?c=problem_solution&rm=318227&rd=15698&pm=12691&cr=23058389 (y[0], 1) (y[1], 2) (y[3], 3)・・・となるようなvector int yが与えられる。これらの点を順につないでいき、直線の関数のつなぎあわせをつくる。y =…

SRM 483 Div2 Hard BestApproximationDiv2

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11073&rd=142361未満の小数numberが与えられる。A / Bとnumberの、整数部から連続して一致する桁数がもっとも長くなるような自然数A、Bを探せ。ただし分母の最大値はmaxDen以下で、答えが複数あ…

Get up! 明日のSUPER ST@R!