- masashinakata
- 3073
- 0
- 0
- 0
SRM DIV2 1000 の解法を書いてる人がいた codeforces.com/blog/entry/133…
2014-08-13 19:13:07なんかちょっと偉そうに書いた方が受けがいいから頑張ってエラそうに書いてるけど、ほんとは「こんな風に強気に色々書いていいのかなぁ・・・ふええ・・・」みたいな心境でツイート書いてる事のが多い気がする
2014-08-13 19:23:46Medium、凄く実装方針ミスってたなぁ、と今更ながら感じるし、もうちょっとグラフ問題華麗に解けるようになりたい気分だ。
2014-08-13 19:34:22昨日のTopcoderの Div2 Med 解き方がわからなかったんだけど最小化すべき関数の形から自明って感じなのかな?
2014-08-13 20:36:52昨日のTopcoderのDiv2 Medを堅く考えると、絶対値は凸関数でその和も凸関数だからソートしてから劣微分が0になりうる点を二分探索で求めればO(n log n)で求められるかな?nの最大は50とかだったから無駄な努力だけど
2014-08-13 20:37:54これ、while (u - l < 1e-9)にしてたら落ちたんだよなあ。理由が分からん... > RT twitter.com/hogeover30/sta…
2014-08-14 02:59:30@chokudai 皆さんのお話を伺っていると固定回反復させるほうがロバストだということっぽいので、次回からはそのように書くよう心がけますー
2014-08-14 03:12:25あとあれだ。@kuuso1さんの言ってたこれも腑に落ちてないんだった… > twitter.com/kuuso1/status/…
2014-08-14 03:13:37@camypaper あ、Σ|weight[i] - x*vol[i]| のグラフって、下向きにくの字の関数を足し合わせているだけなので、極値点はweight[i]/vol[i]にしか無い気がしてきました><
2014-08-13 02:21:46@masashinakata 最近の一番のお勧めは相対誤差での評価だったりするんですが、微妙に書くの面倒なので、SRM系では固定回が安心ですねー
2014-08-14 03:19:39@__math TLEするケースまでシステムテストが進まなかった、っていう感じかもしれないっすねw 皆さんがすぐTLEを想起するヤバいコードであることが分かってよかったです
2014-08-14 03:19:47@masashinakata 例えば、y=|x-2|+|2x-3|で考えると、x=2またはx=1.5以外のxでは、絶対値の記号がそのまま外れるか、-1倍して外れるので、いずれにしても必ずy=ax+bの形になってます。 なので直線になってて極値点はない、っていう理屈です。
2014-08-14 04:37:03