■

だいぶはまった。
とりあえず、http://blog.chinaunix.net/u/26924/showart_351195.htmlに解いてソース上げてる人がいてくれてよかった。

問題は、小数Aと整数Lが与えられて、小数Aに最も近くなるような分数(N/D)を求めよと言う問題。ただし、N,DはL以下でなければならない。

この人は、分子分母を、共に1からはじめて、Aに近づくように徐々に増やしていくと言う手法。
でも、自分はDをforで1からLまでまわして、可能性のあるNを求めて解くという手法でやった。
そこがWrong Answerの原因かと思ったら、理由はそれではなかったようだ。

問題では

abs(A - N / D)

が最も小さくなるようになN,Dを求めろとなっているけれど、それを式変形した

abs(A * D - N)

を最小にするほうがいいだろうと思って、下の式で実装したらWA。で上の式で実装したらAC。

これって下の式のほうが誤差も少なくなるような気がするんだがどうなんだろうか・・・。PKUの正解セットの間違いなような気もするんだけれど・・・。PKUのほうが正しいです。