PKU2249まとめ(1)

以前取り上げたPKU Judge Onlineだが、私もときどき取り組んでいる。PKU1145祭りはもはや伝説と言っても過言ではないだろう。

いまhotなのはPKU2249である。確率の計算のときに出てくる組み合わせnCrを求めるだけの問題なのだが、これが最短コードにしようと思うと意外と難しい。

種明かしを最初にしておくと入力にn=20億,r=20億-1という巨大整数がある。何も考えずに書くと途中計算がint型では収まらないし、収まったとしても実行時にTLE(Time Limit Exceed:時間超過)になり認められない。

Ozyさんがid:Ozy:20060603#p2で通るコードを示している。見てもらえればわかるように、

・rがn/2より大きいか小さいかで場合わけする
・結果をdouble型で計算する

のがポイント。このdoubleをfloatにしたいのだが、floatにすると途中計算で誤差が出てWA(Wrong Answer)になる。ここまでが基本事項。(つづく)