SRM 612
「朝トップコーダーに参加 → 朝から他人のコードのバグを探すのに集中 → 日中の仕事で、コードレビュー時に他人のバグを発見しやすくなる。→ 出世・昇給 → もてまくり！」 by @nico_shindannin
-
masashinakata
- 7121
- 0
- 0
- 0
-
- いいね！0
はむこ
@hamko_intel
4WA。コスト付きの操作の最小回数ってどうするのがいいんだろうなあ…はっこれが所謂ダイクストラか！！ #はてなブログ TopCoder SRM 612 Div1 Easy EmoticonsDiv1 - はむこの勉強記録 hamko.hatenadiary.jp/entry/2017/02/…
2017-02-15 22:34:07
はむこ
@hamko_intel
@y_mazun うーん、再計算が無いならメモ化再帰と言って良いのは理解できます。メモ化再帰でも答えは出るが、以前に計算された答えよりも良い答えが途中で出てきた時に再計算な場合、計算量はダイクストラよりも遅い？、という意図です（SRM 612 D1Eで混乱しました）。
2017-02-15 23:43:25
not
@not_522
@ryo_wk 辺の重みが0か1の場合、priority_queueの代わりにdequeを使うとlogが落ちます（0なら先頭に追加・1なら末尾に追加）。同じように重みが小さい範囲にあるならqueueをたくさん用意するとlogが落ちます。
2017-02-15 23:56:24
まっつん
@y_mazun
@ryo_wk 再計算が必要なやつはDPとは呼ぶイメージはないですね。一般的には全点再計算の可能性があるので計算量はn倍くらいされる(=ダイクストラより遅い)と思います(あまり自信ないです)。
2017-02-16 00:27:23
はむこ
@hamko_intel
@y_mazun 部屋に来ていただいたのを見ました！！ありがとうございます。全点再計算されるようなやつは、多分これだと計算量ダメっぽいですよね。（今回、たまたま再計算があまりなかったので通ってしまいましたが…）
2017-02-16 00:31:11
はむこ
@hamko_intel
練習のために、今の僕にできる最高の一般性でダイクストラを実装した(SRM 612 Div.1 Easy EmoticonsDiv1)。 github.com/hamko/procon/b…
2017-02-16 01:46:10