雑記

競技プログラミングについての話題(?)

さんすう

JOIが終わって翌日の12/12、1day1pro復活祭をしました

 

今度こそ死なないように頑張りたいところですがさっそく先が見えてきて怪しいなあみたいな気持ちです

 

まあ頑張る

 

 

さっそく違う話になりましたがさんすうの話をします

 

12/13の1day1proで出された問題です

 

宝探し | Aizu Online Judge

 

まあ実装する問題なんですが、ここで某氏に謎のエラーが起きます

 

そのあたり全然詳しくないので原因についてはさっぱりなんですが、sin、cosなどの三角関数が未定義みたいなことを言われているっぽく、誰にも原因がわかりませんでした。

 

まあコンパイラあたりの問題だろうしそのあたりを解決すべきだと思うんですけど、ぼくにはその力がなかったので、sinとcosを自分で実装しました

 

まあ有効数字15桁くらいあれば誤差は大丈夫そうだったので簡単に実装したんですけど、結構楽しかったです。

 

 

以下コード

sin, cosの実装(有効数字およそ15桁)

 

 

言われるまでもなさそうですが各関数の説明をします

 

 

abs(long double)

 

絶対値を返すだけの関数です

引数の値が負なら-1かけて返すだけ

別に必要なかったんですが、次の sqrt の内部の if 条件文が汚くなったので分けました

 

 

sqrt(long double)

 

引数の2乗根を返す関数です

処理自体は簡単なものなので見てもらえればいいんですが、数学的な話は適当に調べてください

piの値を求めるために使いました

 

 

pi(int)

 

特に引数は必要なかったんですがとりあえず書いておきました

Gayss-Legendre algorithmと呼ばれている有名なアルゴリズムです

この関数だけは有効桁数を大量に生やすことができます

この問題の角度は弧度法で与えられないのでsin、cos内部でラジアンに変更することにしたのでこれを書きました

 

 

fact (int)

 

引数の階乗を返すだけの関数です

int やら long long だとすぐ爆発して死んでしまうのであえてlong doubleにしました

制度が出せていない一番の原因はこいつです

 

 

pow(long double, int)

 

第一引数の第二引数乗を返します(わかりづらい)

こいつも精度を悪くしている

 

 

sin(int, int)

cos(int, int)

 

本来実装したかったやつらです

幾何学的な定義だとアルゴリズムとして処理できないのでいい感じにします(多分調べれば出てくる)

実装は似ているので片方実装したらコピペすると優勝します

 

 

内部のアルゴリズムに関して一切触れていなくて申し訳ないのですが(TeXが書けないので)

誤差をどうにかしたいみたいな気持ちがあります

 

おわり