SRM 623

すね @sune232002

よく見たら日本語やばすぎたので削除

laycrs @laycrs

@drken1215 値が10^9オーダーなので，1e-9足しても丸め誤差で何も足してないのとおなじになると思います．doubleは15～16桁しか精度ないです

くりんぺっと @climpet

lower_boundは比較しか使わないので

ツカサ し・×・U。 @tsukasa_diary

丸め誤差こわいなぁ

けんちょん @drken1215

@laycrs なるほどです！！！1e-6なら上手くいき、1e-7より小さいと上手くいかない理由が分かってスッキリしました！！！ありがとうございます！

くりんぺっと @climpet

丸め誤差というより情報落ちでは

けんちょん @drken1215

@sune232002 ありがとうございます！！！やっぱり誤差の世界は闇ですね………

laycrs @laycrs

@climpet 正確に言えばそうですね．自分の心の中では情報落ちは丸め誤差の特殊ケースなので丸め誤差に入れてしまっています…．

laycrs @laycrs

（（桁落ちはやばいので名前あっていいけど，情報落ちがなんでわざわざ名前付いているのかが不思議に思っているタイプです

けんちょん @drken1215

@tsukasa_diary 実装されているみたいですねー。違った理由でした！

パーポーフルート @ParpooFruit

(ブログ更新) SRM 623 Div1 300 UniformBoard: A or P or . が入ったマスがgrid状にNxN個ある. AかPをどこか他の.のマスに移す操作を最大K回できるとき、全部Aに... bit.ly/1hd47nY

ツカサ し・×・U。 @tsukasa_diary

@drken1215 浮動小数はこわい・・・

tsukuno @tsukuno

今朝の 450 の TLE の件、1M 要素の配列のソートを定数倍高速化したら通った。 N log N になんか定数かかってるからかね？とはいえ 1.998s とからしいが

tsukuno @tsukuno

開始地点から到達できないノードを除去するという、あんま意味のない最適化をしたら 1.947s になった。

tsukuno @tsukuno

Segment Tree だとちょっとオーバーヘッドでかいんだろうね。L の順に score を insert してって、R が自分より小さいやつらの max を拾いたいだけなので、もっとシンプルなヤツにすればいいはず

tsukuno @tsukuno

あれ？他のヤツの R に到達した時点で、そのデータ削除しているから、どうでもいい？

tsukuno @tsukuno

待て、L の時点で R で検索しているからダメだ。

tsukuno @tsukuno

どうでもいいが abstract class 使うと、30% ルールにひっかかる。

tsukuno @tsukuno

なんかおかしい

tsukuno @tsukuno

2 の乗算と除算をシフト演算に変更してみたら、気持ち早くなったが、確率的に TLE が発生して謎。っていうか、1.5s くらいのヤツが TLE したりしなかったりなので、GC か何か起きてる？

tsukuno @tsukuno

メモリ 64MB 使ってないのだが、なんか設定まずい？

tsukuno @tsukuno

取り敢えず 64MB の空配列を確保したら、ちゃんとメモリ使用量増えたので、GC ではなさそうだなぁ。

tsukuno @tsukuno

long 使ってたところを int にしたら遅くなった......

tsukuno @tsukuno

なんか sort が一貫性ないらしい。意味分からん

tsukuno @tsukuno

む、int の加算で overflow してた。long => int にするのは問題ないが、cmp(A, B) { return A - B; } はまずいみたい