VK Cup 2017 Round 3(Codeforces Round #412 Div.1 + Div. 2)

有為 @uwitenpen

時間ギリギリだからあぶないかも

はむこ @hamko_intel

@btk15049 しゅごい

btk @btk15049

@hamko_intel どうせ落ちるので、、、

よすぽ @yosupot

E問題、StarrySkyTree * 2 + FastSet + FenwickTreeなので通ったら奇跡です

有為 @uwitenpen

Dテスト書いたほうが良かったかな・・でも時間大量に使ったし・・

はむこ @hamko_intel

@btk15049 ぼくも一緒に落ちてあげるよ（はーと）

はむこ @hamko_intel

Div.2 Bが本当クソなので

かつっぱ@競プロYouTuber @catupper

A：二分探索の時にlong long を忘れて7WA B:あ〜 C:scanfの時に%lldを使って 8WA D:時間なし E:時間なし F：時間なし

タッパーをオーブンで焼かない @DEGwer3456

Eは一点更新と区間askのsegtreeとset使えばできる

chokudai(高橋 直大)🍆 @chokudai

Dは無茶苦茶混乱したよね pic.twitter.com/cStOnHmzbE

拡大

btk @btk15049

d1Cかな？ d2Eはなんか数字を分ける奴はどうせ区間になるじゃろと思ってやってみたらうまくいきそうで 最大は貪欲にやるとできて、最小は二分探索した

(nは自然数) @n_vip

D問題、考察してて「ミュージアムから最小の辺までの距離はlog」っていうのが出てきて使うのかと思ったらただのダイクストラで拍子抜けした

はむこ @hamko_intel

A: 00:12 B: 01:15 C: 01:42 D: 02:34

(nは自然数) @n_vip

E問題はO(n^2log n)が思いついただけで終わり

(nは自然数) @n_vip

こういうそこらへんに転がってる題材のおもしろ問題は好きです（問題文がちょっと長くてかつ気取ってる感は否めない）

(nは自然数) @n_vip

日本人普段からこんなに上位にいっぱい居たっけ？

chokudai(高橋 直大)🍆 @chokudai

Eはなんか、「前半部分は適当にUnionFind的なskip後にBITして、後半部分で別のSegtree書くだけじゃん・・・」って思ったけど時間内に書ける気がしなかったから書かなかった。 （マイナス部分とプラス部分で別々に計算する感じ）

(nは自然数) @n_vip

長いけど読みにくいことは無いと思うんですよ

btk @btk15049

d2Cが災難 なんか式変形しまくったらx+正解者数がpの倍数にならないとまずいっぽいのでそこを二分探索した

有為 @uwitenpen

A問題でクソミスしたよね・・

タッパーをオーブンで焼かない @DEGwer3456

ああそうか、最小辺のコストを引いておけばdijkstraして最後の辺を2倍するかどうか全部やればいいだけになるのか、解けるべきだったなぁ(見た目が最短路なんだから最短路しようと思えという話だ)(おもしろい)

タッパーをオーブンで焼かない @DEGwer3456

こういう癖のないセット好きですよ

btk @btk15049

d2Dは人数決めうちしたらあとは各問題正解か不正解にぶっぱするのがお得なので3e5×2^5ぐらいを全探索しました

chokudai(高橋 直大)🍆 @chokudai

とりあえずわかったことはtouristすき

有為 @uwitenpen

C,Dが考察>実装という感じなので日本人結構いけてるのでは