-
masashinakata
- 2293
- 0
- 0
- 0
-
- いいね！0
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoder SRM 667 Div1 Medium CatsOnTheCircle - kmjp's blog kmjp.hatenablog.jp/entry/2015/09/…
2015-09-12 13:14:00
kmjp
@kmjp_pc
昨晩のMediumはなぜ三項間漸化式まで見えていて特性方程式に向かわなかったのだろう…。まぁ他にも色々ミスしててどのみち１時間ではバグ潰しきれなかったけどさ。
2015-09-12 13:15:35
agw
@masashinakata
SRM 667 Div I Easy、ノード数O(2^m)のダイクストラとO(2^mn)のDPの両方で復習。恐ろしいくらいの良問だった…
2015-09-12 14:38:30
tshita
@tshita0
求めたいのは分かってたけどそれをどう式で表すのかが分からなかった。分かっていても解けなかったし大変だ。kmjpさんの解説有り難いな。 twitter.com/kmjp_pc/status…
2015-09-12 15:31:51
tshita
@tshita0
apps.topcoder.com/wiki/display/t… 昨日のdiv1easyのEditorialが出てるけど，s1とs2（s1 subseteq s2）の差集合ってs2-s1で良いんだ．そう言われればそうだ．
2015-09-12 17:28:55
kuuso
@kuuso1
ダイクストラの計算量、蟻本先生によるとO(ElogV)らしいけど、どうもO(VlogE)じゃないかと思うし、wikipediaにはO(E+VlogV)と書いてあったりしてもう何が何だか。
2015-09-13 00:06:25
ぷち＠プログラマ日本一です
@takapt0226
@kuuso1 競プロでよく使われるpriorityqueue(二分ヒープ)を使ったdijkstraはO((E + V)logV)です
2015-09-13 00:08:48
kuuso
@kuuso1
@takapt0226 ワーストE回ヒープはpopして、各popとpushはlog（キューの中身の個数）、各vは高々V個のノードをpushするけど、ワーストケースではE個キューに入ってそう、みたいな感じでO(max(E,V) logE)っぽく感じるんですがうーん。
2015-09-13 00:21:17
ぷち＠プログラマ日本一です
@takapt0226
@kuuso1 logの部分は、Eは最大V choose 2なので、O(logE) = O(logV^2) = O(logV)となります 計算量をどこまで省略していいのかよく知らないのですが、実用上O(ElogV)と考えれば十分です
2015-09-13 00:34:32
ぷち＠プログラマ日本一です
@takapt0226
@kuuso1 dijkstraの計算量は、O(辺のpush + 頂点のpop)なので、そもまま当てはめるとO(ElogE + VlogE)ですね
2015-09-13 00:39:55
kuuso
@kuuso1
@takapt0226 個人的にはやっぱりそれが一番しっくりきます。 logVがついてるやつって全部O(E)＝O(V^2)で置き換えていて、それってEとV分ける意味ないじゃんって気がしてしまう。
2015-09-13 00:42:23
とーらす🌸📦🌕✨🍀
@torus711
2 週間ぐらい解けずにいた問題，放置してもアレだし Editorial 見ようとしたらエラーとか表示されて，仕方無いからもっかい自分で考えるかーと思って本腰入れて解いたら普通に解けてしまったしもう色々とダメ．というか横着しなかったら本番でも通せてた気がするしあああああ……．
2015-10-01 22:26:24
とーらす🌸📦🌕✨🍀
@torus711
書いた : TopCoder, Single Round Match 667, Division 1, Level 1 : OrderOfOperations - torus711 の… torus711.hatenablog.com/entry/2015/10/…
2015-10-01 23:30:54