-
masashinakata
- 1780
- 1
- 0
- 0
-
- いいね！0
きひろちゃん（9歳幼女）
@aki33524
WF法って地味に難しい考察が後ろにあるよね。最短経路がDPになるのとメモリを再利用しても問題無いというのが難しい所だろうか。
2016-06-19 04:30:49
くりんぺっと
@climpet
Warshall-Floydでよくあるミスが2つあり、1つは d[i][i]=0 を忘れること、もう1つはループ変数の順番を間違えること
2016-06-19 04:33:26
煉獄会長
@RengokuKaicho
easy:ノード間コストをN^2で求めておいて、1じゃないのがN個程度ならDijkstraでいいんじゃね→Nよりだいぶ多い例が見つかる→スカスカだし一直線じゃなければ2でいいんじゃね→WF解と一致したので提出→map iterでvalueをソートしてたらarenaでfailed
2016-06-19 04:33:48
きひろちゃん（9歳幼女）
@aki33524
ミスらないように俺は変数の順番をk, i, jの順にしてます。d[i][j] = min(d[i][j], d[i][k] + d[k][j])となってミスりづらい。
2016-06-19 04:35:07
programming togetter
@programmingtoge
togetter.com/li/989152 TCO16 Algorithm 2C #programming
2016-06-19 04:45:13
不養生
@satashun
あー, やっぱり4-4-4に分けて, 1回目は4-4で比べる(これで同じだとまあ出来るので違ったとする), 重い方と軽い方を混ぜてみるが2個ずつ入れ替えてしまうと次の候補が4個になって辛いので, 軽い方2個ずつに重いのを1個ずつ足して左右に乗せるといける気がする
2016-06-19 05:05:12
煉獄会長
@RengokuKaicho
いやこれは int overflowが原因だった。dx=dy=32768, ll v=dx*dx+dy*dy で手元では 2147483648 になってしまう。int overflowは未定義なのか。 stackoverflow.com/questions/1618…
2016-06-19 05:15:02
煉獄会長
@RengokuKaicho
普段 ll にしてるのに今日は w[1501][1501] するしケチるかの流れで dx dy も int にしてしまった。。ll で救える命がある。
2016-06-19 05:21:15
kusanoさん@がんばらない
@kusano_k
#TopCoder Open 2016 Algorithm Round 2C o-- 123.64点 142位 1779→1815 PSVRの予約に行こうと思いEasyだけ解いて寝たけど、そこそこの順位。提出後にゆっくり確認しているつもりが提出していなくてひどかった(´Д｀； )
2016-06-19 08:34:13
kusanoさん@がんばらない
@kusano_k
a/bを既約分数に直すのは、gcd(a, b)で割れば良いので、O(log a)。昨日思い出すのに時間が掛かったので....〆(･ω･｀ )ﾒﾓﾒﾓ
2016-06-19 08:36:09
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoderOpen 2016 Round2C Easy BearBall - kmjp's blog kmjp.hatenablog.jp/entry/2016/06/…
2016-06-23 23:32:49
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoderOpen 2016 Round2C Medium BearGridRect - kmjp's blog kmjp.hatenablog.jp/entry/2016/06/…
2016-06-23 23:42:04