SRM 636

Div9851 @Div9851

@camypaper 片方だけ試せばよいことに気づけるかですか？

kmjp @kmjp_pc

はてなブログに投稿しました TopCoder SRM 636 Div1 Medium ClosestRabbit - kmjp's blog kmjp.hatenablog.jp/entry/2014/10/…

紙ぺーぱー @camypaper

@Div9851 僕は本番で出たら絶対解けないと思いましたねあれは…

紙ぺーぱー @camypaper

@Div9851 二分探索+片側全探索という解法についての話という認識であってます？

kmjp @kmjp_pc

SRM636の面白さは、D1M > D2H >> D1H > D1E > D2Mだったな。Div1Mediumの２頂点サイクルペアの確率を求めればよい、って着眼点が面白かった。

ぱ @purple_jwl

div2hardまだ解けてないから通勤しながら考えようか

ぷち＠プログラマ日本一です @takapt0226

逆に一番実行される部分のassertは地味にやばいというのをこないだのDiv2Hardで知った

ぱ @purple_jwl

解法全く思いつかん

はまづ @hama_du

会社のPCだとスペック不足でTopcoder Arenaがまともに動かない #仕事しろ

ぱ @purple_jwl

解法チラ見してしまった

ぱ @purple_jwl

てっきり切る場所を二分探索するかと思ったら違った

ぱ @purple_jwl

俺氏、とても弱い

紙ぺーぱー @camypaper

@purple_jwl あれ，もうeditorial出てましたっけ

ぱ @purple_jwl

@camypaper 正確に言うと（コードを）チラ見した

紙ぺーぱー @camypaper

@purple_jwl Div2hard，あれは普通に難しいですよねぇ…(Div1easyやってると余計に難しく感じる気もする？)

ぱ @purple_jwl

@camypaper やってることは難しくないのに思いつかなかったので無限につらみが増しますね...

紙ぺーぱー @camypaper

@purple_jwl はい…(´・_＿＿・`)

ぱ @purple_jwl

二分探索、全く使いこなせてないんだよなぁ

ぱ @purple_jwl

自力ではないけど、div2hard解けた

kinaba @kinaba

この前のSRMのMedは考えれば考えるほど解けるべきだった気がしてくるなあ。「連結成分の数＝サイクルの数」はすぐわかる、サイクルにせよ連結成分にせよ所属数が小さいなら期待値の線形性でばらして数えやすいこともわかる、とくれば実際小さくなっててくれるのではないかとは当然考えないと

ぱ @purple_jwl

TopCoder SRM 636 Div2 Hard: ChocolateDividingHard - ぱーぽーの日記 purple-jwl.hatenablog.com/entry/2014/10/…

ぱ @purple_jwl

二分探索できません。