Codeforces Round #339

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Dは、根付き木のミサワさんを面倒にした感じの問題だった。

koyumeishi @koyumeishi_

幾何ライブラリの「点と線分の距離」が何故か「点と直線の距離」を返していることに気付くのに無限時間要して、修正してたらコンテスト終わってた…

有為 @uwitenpen

@koyumeishi_ 罪深い

koyumeishi @koyumeishi_

ていうかdiv2 B読めなさすぎでしょ

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

D：必要な頂点だけ取り出したグラフを作って適当にやる。行きがけ順で並べて隣接のLCAを列挙して、もう一回ソートしたら辺をどこに張ればいいかが少し求めやすい。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

今回結構pretest強そうだけど、hack成功した人いるんだろうか。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Cだけ面白かった。

koyumeishi @koyumeishi_

div2 Dもちょっと怪しい気がするから最悪0完あるで

有為 @uwitenpen

D,結局はぶち切る頂点はK個より少ないはずだし、いかに余計な頂点にさわらずにぶち切るかって考えた

kmjp @kmjp_pc

Div2Aはずいぶん派手なHack祭りになってるけど、これオーバーフロー狙いだろうなぁ…。Div2Aでやる制限では無い気がするが。

koyumeishi @koyumeishi_

div2 A落ちたｗ オーバーフローしたら負になるやろｗｗｗ的な雑な考えで if(unko < 0) break; とやったのがいけなかった。 やっぱダメだよね

kmjp @kmjp_pc

あれ、B落ちてる…。せっかく年初め好調な出だしを飾れると思ったのに。まぁレート微増にはなりそうだけど…。

koyumeishi @koyumeishi_

div2 Dは通っててセーフ。 最悪は免れた

よすぽ @yosupot

Cで1時間使ったのもうダメダメ。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

あー、今回pretestめっちゃ強いと思ったけど、Bはそこそこ落ちてるのか。

よすぽ @yosupot

Dの概要を聞いた。実装がヤバイ。

kmjp @kmjp_pc

B通った、途中まで意識していたはずなのに、なぜこのケースを忘れていた…。

pekempey @pekempey

Dは最大にする個数を決め打ってから最小値を二分探索した

koyumeishi @koyumeishi_

はい、div2 Cも直した幾何ライブラリで通ってた。 ホントなんで "line segment"って書いてあったんだ…

koyumeishi @koyumeishi_

アナウンス見てなくてn=1, n=2のケースも含めてしまったな

koyumeishi @koyumeishi_

div2 D は Aにする個数を全探索、 残りのやつの最小の値を2分探索、 その値に出来るか判定を2分探索( ただし探索範囲はn-(Aの数)個でだんだん減る) の O(n log A log hoge) ぐらいでやったら140msで通った

koyumeishi @koyumeishi_

（当然あらかじめソートしておいてAにするのはコストが小さいのから、最小の値に出来るかは累積和でほげる

ゆらふな @yurahuna

Codeforces Round #339 (Div. 2) A, B, C 解答 - ゆらのふなびと pakapa104.hatenablog.com/entry/2016/01/… pic.twitter.com/Ll7hhbSHso

拡大

pekempey @pekempey

はてなブログに投稿しました #はてなブログ Codeforces Round #339 (Div. 1) A. Peter and Snow Blower - pekempeyのブログ pekempey.hatenablog.com/entry/2016/01/… pic.twitter.com/KWHLdX9HQw

拡大

pekempey @pekempey

はてなブログに投稿しました #はてなブログ Codeforces Round #339 (Div. 1) B. Skills - pekempeyのブログ pekempey.hatenablog.com/entry/2016/01/… pic.twitter.com/58ckB0D8ph

拡大