CSA Round #54

有為 @uwitenpen

F, ある1点から伸ばして最小となる区間の極大なものをとるとO(n)とかO(nlog n)で抑えられる？

HIR180 @HIR180

Gそういう系かあ.... (よくわからんけど綺麗に解けるやろ！ｗみたいな気持ちになってしまい爆発した)

iwashi31 @iwashi31

こないだのAtCoderの完全グラフor完全二部グラフになる問題が印象に残っていて、奇数長の閉路があったらなんかするのかなぁという考えに固執してしまった

olphe @_olphe

これ！

iwashi31 @iwashi31

Dまではかなり好調だったんだけどなぁ

よすぽ @yosupot

右端にxを追加するときは、[x, INF]で最も右のものを求めて(y_1とする)、次は[x, (x+y_1)/2]で最も右のものを求めて、次は[x, (x+y_2)/2]、...みたいな操作になる

iwashi31 @iwashi31

やはり構築系の問題はこんな感じやろ！が通用しやすいので比較的得意な気がする

olphe @_olphe

？？？「日本人3位やぞ、道を開けろ」

olphe @_olphe

ratedかunratedか知らんけどratedだったら+70ぐらいもらえそう

kmjp @kmjp_pc

Fは分割統治とかかと思ったら普通に平方分割か…。

olphe @_olphe

votingどう解いたの？マンが定期的に表れるの好きすぎる

olphe @_olphe

現れるやが

HIR180 @HIR180

やっぱ困った時の平方分割は常に意識しとかないとダメだなぁ (JOIから離れてAtCoderばっかり埋めてると完全に忘れる)

olphe @_olphe

1814->1876(highest!!)

hamayanhamayan @hamayanhamayan

はてなブログに投稿しました #はてなブログ Spanning Trees [CSAcademy #54] - はまやんはまやんはまやん hamayanhamayan.hatenablog.jp/entry/2017/10/…

koyumeishi @koyumeishi_

Fの(解説の方針の)平方分割頭にあったんだけど、一つのバケツの中の diff_i,j の O(1) 求め方がわからなくて駄目だった

iwashi31 @iwashi31

1793->1794(+1) オー

とーらす🌸📦🌕✨🍀 @torus711

CS Academy 54, ooo-o-- = 900 pts (126), 146 th, Rating 1668 -> 1711 (+43)

HIR180 @HIR180

(もとのレート) -> (もとのレート)-2

よすぽ @yosupot

1651 -> 1872、よくわからないけど赤くなった…

olphe @_olphe

1675黄色で1775赤なんで1875で虹にしてくれませんか

hogeover30 @hogeover30

Your rating has decreased by 3 points .

koyumeishi @koyumeishi_

一つのバケツの中には sqrt(N) 個の要素しかないからバケツの中で O(M^2) かけて事前計算しても O(N^1.5) にしかならないのか…そっか…。

よすぽ @yosupot

と思ったけどそもそも赤色のラインが相当低いのか

olphe @_olphe

touristのレート、2200ぐらいで収束するんかなあ