Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

[C41] コメントありがとうございまーすっ

そこの表記に関しては凄く悩んだんですよね・・・
ぶっちゃけ、できる人はそうやって叩いてくれてもいいかな?と思ってましたw

理由としては、「TopCoderをやるのに、小数の構造とかを気にせず気軽に解いてもらいたい」ってのがあります。
includeはおまじない、と似たようなものだと思います。
どちらかといえば、今回の連載で重視してもらいたい所は「発想力」や「どう組むかを考える力」、であって、そういった細かいところで躓いてもらいたくないな、と思ってあのような表記をしました。
(もちろん、TopCoderにおいても実務においても、その「細かい部分」が非常に大切になってくるわけですが・・・)

多分殆どの人はそうは思ってくれないかとは思いますが、あくまで自分はあの連載を「初心者向け」ってつもりで書いてますw
出来るだけ「知識面」では難しいことが出てこないように、と思って書いてるつもりです(つもり、でしかないのは自分の能力不足ですorz)
なので、「この説明が分からない場合には、」という前置きの元で書いたのですが、確かに相対誤差に関しての記述はその中に入れるべきでしたね、そこは少し失敗したかなと思います。

そんな感じですっ、ご意見ありがとうございまーす!
  • 2010-02-06 12:48
  • chokudai
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/972-4ed05ffe
この記事にトラックバックする(FC2ブログユーザー)

トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター (この記事を編集する[管理者用])

という名前の,chokudai先生の連載の最新記事. 二分探索の話.
最後の方に,二分探索の終了条件を書くときに while(high-low<1e-9) と書くと丸め誤差のせいで止まらないことがあるから,定数回回しなさい的なことがやんわり書いてあります.
これを押しつけるのは危険な考え方かな―という気がします.
まぁ,そもそもchokudai先生本人は,超頭柔らかで,定数回ループじゃない方が良い場合は,さくっとそっちで書いちゃう気がするのですが,読者はどうだろうか,ということで.
というか,そもそも,chokudai先生は,定数回ループじゃないとダメ的なことは考えてないと思うのですが,文章はそう言ってるようにも見えるという意味で.

そもそも,TopCoderで要求される精度は,絶対誤差が10^-9以下または相対誤差が10^-9以下.
while(high-low<1e-9) が悪いのは,丸め誤差が悪いんじゃなくて,絶対誤差しか考えていないこと.
相対誤差も考えて, while(high-low<1e-9 && high-low<1e-9*max(abs(high),abs(low))) と書けば良いし,定数回のループを回すよりはこっちの方が自然だと思うわけで.

ただし,TopCoderはあくまで競技プログラミングであって,実行時間が制限時間内に終わるならば,より簡潔でより悩みどころの少ないアルゴリズムを書くべきだと思います.
そういう意味では,定数回ループが正解ですね.
取り敢えず,定数回ループとかぬるいこと言ってるとTime Limit Exceededになる可能性のある問題として,LiveArchive 4412 - The Great Gameを紹介してみます.単純な二分探索の問題ではないですが.
(LiveArchiveって最近サーバ速くなった? そうだったら普通に通りそうな気もする)

まぁ,そもそも自分はプログラミング的な思想とか基本的にはわからないのですが,こういう風に思いましたってことで.

コメント

[C41] コメントありがとうございまーすっ

そこの表記に関しては凄く悩んだんですよね・・・
ぶっちゃけ、できる人はそうやって叩いてくれてもいいかな?と思ってましたw

理由としては、「TopCoderをやるのに、小数の構造とかを気にせず気軽に解いてもらいたい」ってのがあります。
includeはおまじない、と似たようなものだと思います。
どちらかといえば、今回の連載で重視してもらいたい所は「発想力」や「どう組むかを考える力」、であって、そういった細かいところで躓いてもらいたくないな、と思ってあのような表記をしました。
(もちろん、TopCoderにおいても実務においても、その「細かい部分」が非常に大切になってくるわけですが・・・)

多分殆どの人はそうは思ってくれないかとは思いますが、あくまで自分はあの連載を「初心者向け」ってつもりで書いてますw
出来るだけ「知識面」では難しいことが出てこないように、と思って書いてるつもりです(つもり、でしかないのは自分の能力不足ですorz)
なので、「この説明が分からない場合には、」という前置きの元で書いたのですが、確かに相対誤差に関しての記述はその中に入れるべきでしたね、そこは少し失敗したかなと思います。

そんな感じですっ、ご意見ありがとうございまーす!
  • 2010-02-06 12:48
  • chokudai
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/972-4ed05ffe
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。