-
masashinakata
- 5815
- 1
- 2
- 0
-
- いいね！0
とーらす🌸📦🌕✨🍀
@torus711
@JohnNakazawa そもそも前提同じだったら揉めにくいし……．で，なんか揉めたときに前提の確認に行くことってあんまり無い印象（と思ったけどあんまりそういうの観戦しないし謎だった）
2016-05-10 00:36:14
laycrs
@laycrs
@beepcap 横からちょっとだけ補足しておくと，競技プログラミングの問題の多くは答えが(2^32)^2で抑えられて，要求誤差が10^-9な事が多いので，この場合ループを93回回せば良いことがわかって，100回のループで十分ってのがほとんどである，と思っているんだと思います
2016-05-10 10:34:37
laycrs
@laycrs
@beepcap 定数回のループを回す人でも，この問題なら60回で良い，この問題なら90回回す，などとやる場合が多いとは思います．多倍長などは遅いので，それが原因で誤答になったり，そもそもコンテストによっては多倍長ライブラリ使えず自分で書かないといけなくて，かなり使いにくいです
2016-05-10 10:35:45
laycrs
@laycrs
ただ，個人的な感想だけど，二分探索で定数回ループさせるのが良いよねって主張はああいう場でああするのは流石に酷い気がする．そもそもあんまり良くない方法だけどまあ書くとき楽だよね，なので，十分な回数の定数回ループでもいいですよぐらいが良さそうな…．
2016-05-10 10:36:12
laycrs
@laycrs
少なくても，テストケースが多いと相対誤差での打ち切りも考えた方が速い場合が多いし，二分探索と言って良いかわからないけど，原点に戻るタイプのループのあるDPだと，区間が毎回半分以下にガリガリ削られるので，ちゃんと判定したほうが（速度面で）良い．
2016-05-10 10:36:22
laycrs
@laycrs
後，相対誤差の判定が，割り算使ったような判定にするのこそ筋が悪い気がする（コード見て意味がすぐわかるのにしたんだろうけど）．相対誤差の判定がめんどいのは，まあそうだとは思うけど．
2016-05-10 10:36:43
laycrs
@laycrs
また，@beepcapさんの言ってた通りだけど，三分探索とかでも100回ループ回すーとかやって誤差死している人たまに良く見るので，そういう人を生み出しそうという意味でも良くなさそう．
2016-05-10 10:37:10
chokudai(高橋 直大)@AtCoder社長
@chokudai
そういえば、プログラミングの課題の採点で、i < n + 1って書いたら×されて、i <= nに直されたことがあるのだけど、こういうのどうなんだろ。 後者の方が視認性という意味では圧倒的に良いのだけど、確か授業でまだ<=を１回も使ってなかったから前者にしたんだよね。
2016-08-01 14:14:12
chokudai(高橋 直大)@AtCoder社長
@chokudai
二分探索の説明で、「mid = (min+max) / 2はmin+maxでオーバーフローの可能性があるからバグのある実装である」みたいな話をちょこちょこ聞くけど、んなこといったら全てのint型で渡された整数において、+1された数も-1された数もint型で持てる保障ないやん
2016-08-01 14:25:45
みけCAT
@mikecat_mixc
@chokudai オーバーフローの可能性がある実装はオーバーフローの可能性があるから、チェックして避けよう securecoding.cert.org/confluence/dis…
2016-08-01 14:29:32
chokudai(高橋 直大)@AtCoder社長
@chokudai
ってことで自分は本とかには(min+max)/2で書くけど、min+maxがオーバーフローする可能性があることをわかっていないわけではないことを明記しています。 こっちのほうがソース読むとき直感的だからね。解説の上ではやっぱりこっち使いたいんだよね。
2016-08-01 14:35:35
AoiMoe a.k.aしお兄P
@AoiMoe
結果が開いているわけではなく、結果が必ずintの範囲内に閉じているのに、途中計算でオーバーフローするのはバグ、という考え方は当然ありうる。さて、どう直すとオーバーフローしないようにできるか。できれば分岐なしで。 twitter.com/chokudai/statu…
2016-08-01 14:50:17
chokudai(高橋 直大)@AtCoder社長
@chokudai
あ、割と有名な話だと思っていたから書いてなかったけど、回避する場合はmid = min + (max-min)/2ね。自分の解説では多分これは使わないけれども。
2016-08-01 14:59:22