CSA #81 (Div. 2 only)

てんぷら @tempura_cpp

Highestが競プロ始めて1ヶ月ちょっとの2月なのおかしくないですか？おかしいですね。CSAやめます。

こたつがめ @kotatsugame_t

CSA Round 81 oooox 34th(rated 12th) 1758->1840(+82)highest 黄色になりました

てんぷら @tempura_cpp

Dちゃんと解いてたら黄色いけてたね、悲しいね。

アルハンブラ宮殿のゆるキャラ @nebukuro09

CSAやっと黄色に戻った

アルハンブラ宮殿のゆるキャラ @nebukuro09

CSAもう38回も出てんのかよ

kmjp @kmjp_pc

MST求めるのはいつも何も考えずクラスカル法使ってたけど、プリム法じゃないと間に合わない問題初めてであったかも知れない。

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ CSAcademy Round #81 : D. Gerrymandering - kmjp's blog kmjp.hatenablog.jp/entry/2018/06/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ CSAcademy Round #81 : E. Fold Polygon - kmjp's blog kmjp.hatenablog.jp/entry/2018/06/…

けんちょん @drken1215

昨日のCSA中に襲われた眠気は尋常じゃなかったのん。問題考えるどころか、起きてることも困難だったから、順位表見てレーティング爆下げってことはなさそうだったから寝たのん。。。

けんちょん @drken1215

それでも、とりあえずレーティング微増して、青から黄色に復帰できて良かったん。次回頑張るのん。

けんちょん @drken1215

@kotatsugame_t @tempura_pp おめでとうなのんっ！！！！！\\ｳｵｵｵ(っ `-´ c)ｵｵｵｵｵ//

こたつがめ @kotatsugame_t

@drken1215 ありがとーなのん！

けんちょん @drken1215

D、貪欲だけでなく実家風 DP でも行けるんのんな。

beet @beet_aizu

O(3^n)とO(n^2 2^n) の感覚的な差がよくわからん

けんちょん @drken1215

ダイクストラ法は容量 1 の最小費用流だし、水の流れは納得なのん。 twitter.com/mistter_gp/sta…

けんちょん @drken1215

Dijkstra 法、紐を伸ばしていくイメージはよく語られるけど、水を流していくイメージもそれとよく似てるのんな。

beet @beet_aizu

O(E logV)のDijkstraを先に覚えたせいでO(V^2)のDijkstraを知らない人がいるのめっちゃおもしろい事象だと思う

beet @beet_aizu

Dijkstraを1. O(ElogV) 2. O(V^2) で実装できるか

けんちょん @drken1215

昨日の CSA E もごく稀に見る、 O(ElogV) だとダメで O(V^2) なら間に合う系の問題だったらしい (？) のん。 ダイクストラじゃなくて、MST だけどよく似た事情なん。

けんちょん @drken1215

ダイクストラ法、ナイーブな O(V^2) よりも priority_queue を使った O(E logV) の方が速いという言及がよくなされるけど誤解で、密グラフ (E = O(V^2) なグラフ) のいては、O(V^2) の方が速いのん。

(nは自然数) @n_vip

これは罠で、priority_queueのlogは定数

けんちょん @drken1215

コンテストにおいては、疎なグラフの方が圧倒的に出題が多いので、ほとんどの問題においては O(E logV) の方が速いのはそれはそうなのん。