SRM 664

nico_shindannin（診断人） @nico_shindannin

やっと昨日のDiv1 Med理解した…

nico_shindannin（診断人） @nico_shindannin

のぞえりRadio Garden聴きながら、まとめを書くのじゃ。

nico_shindannin（診断人） @nico_shindannin

SRM664 Medのまとめを書いてたけど、無限に時間が無くなりそうなので、手抜きすることにした！

nico_shindannin（診断人） @nico_shindannin

SRM664 Medの問題 pic.twitter.com/VUTzTJPRN5

拡大

nico_shindannin（診断人） @nico_shindannin

ポイント。（つながってる都市数^2）でスコアを出すと、都市の壊れ方2^Nパターンそれぞれに対してスコアを出さないとダメなので計算時間的に無理。ここで、実は経路の繋がってるならスコア+1と置き換えて良いことに気づきましょう（ムリ） pic.twitter.com/FrlayEIj4b

拡大

nico_shindannin（診断人） @nico_shindannin

この置き換えをして、さらに期待値の線形性の性質を使うと、各始点終点がつながっている確率を全部足し合わせたものを、スコアにして良いことになる。これは初見では難しい気がするのじゃ…。

nico_shindannin（診断人） @nico_shindannin

（この図は超手抜きじゃ）あとは各始点終点ペアごとに、つながってるかの確率の和を求める。そのままだとO(N^2)になるので、木DPでO(N)にする必要がある。部分木内の頂点から根まで繋がる確率の和をまず求めて、上手に重複なく全列挙して！ pic.twitter.com/5sXVRH0SpA

拡大

nico_shindannin（診断人） @nico_shindannin

ちなみに、他にも逆元を求めたり、都市番号の大小関係のルールに気づくと楽にかけたりとか、小さいポイントはあるのじゃ。これはわしには無理…

agw @masashinakata

を、competitiveprogramming.infoで点数クリックと実装が見られるようになってる!

kmjp @kmjp_pc

SRM664のMedium通った。本番近いところまで行ってたけど、数え上げをダブらせちゃって失敗したか。あと逆数求めるのに何度も繰り返し自乗法やったらTLEした。Nの上限が10^6だから結構きついのか。

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoder SRM 664 Div1 Easy BearPlays - kmjp's blog kmjp.hatenablog.jp/entry/2015/08/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoder SRM 664 Div2 Medium BearPlaysDiv2 - kmjp's blog kmjp.hatenablog.jp/entry/2015/08/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoder SRM 664 Div2 Hard BearSortsDiv2 - kmjp's blog kmjp.hatenablog.jp/entry/2015/08/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ TopCoder SRM 664 Div1 Medium BearAttacks - kmjp's blog kmjp.hatenablog.jp/entry/2015/08/…

platypus @platypus999

【SRMDiv1Easy埋め】 SRM664 BearPlaysを解きました。 これはAtCoderっぽい問題。今までずっとBruteForceだったのが急に数学になるのやめて

はむこ @hamko_intel

@PlatypusSurface なんか実験してたら答えが生えたやつだった気がする

platypus @platypus999

@ryo_wk 実験 #とは

はむこ @hamko_intel

@PlatypusSurface (1) 実験したら、A+Bが一定っぽい→B=n-Aとおく。 (2) 実験したら、A, Bは常にA+B以下っぽい (3) 実験したら、第k項はただのA*2^kじゃん→おわり みたいな docs.google.com/document/d/15C…