-
threecourse
- 2875
- 0
- 0
- 0
-
- いいね！0
ユピテル
@yupiteru_kun
@tsukammo 私がやっていたのは全ての辺に同じ値の固定値を加算して、その上で通常のダイクストラをやる感じのものでしたので、擬似的に「曲がるとペナ」みたいなことをイメージしたものの実際には通常のダイクストラと同じなので特別な考慮とかはしていませんでした。
2021-05-30 23:14:55
koyumeishi
@koyumeishi_
AHC003、推定系じゃなくて焼き鈍しでそれっぽい盤面を生成してる人がいるのか。しかもそこそこのスコア出ててですごい
2021-05-30 23:15:07
けせらせら
@keserasera_77
AHC003結果は92.8Gでした。 基本的にダイクストラ法で、返ってきたスコアを使い辺の重みを更新していく感じ。 辺の重みを変える規則は ・更新前の辺の重みと同じ比率でスコアを各辺に割り振る
2021-05-30 23:15:57
いなにわ
@inani_waon
はてなブログに投稿しました #はてなブログ AHC003 - Shortest Path Queries 参加記録 - inani_waonの日記 inaniwa.hatenablog.com/entry/2021/05/…
2021-05-30 23:25:07
btk
@btk15049
docker内で回している関係上、webサーバーとして立ち上がるoptuna-dashboardは相性が良すぎる、、 もっと早く知りたかった
2021-05-30 23:26:03
ヘクト🐬
@osrehun
@rian_tkb 疎行列の特性を生かす解法を考えるなら，遠回りするのは不利っぽいと思った．あと，パラメータ推定した結果の分散が大きくなりそう．
2021-05-30 23:26:41
マヨ子@秋篠宮popstar
@mayoko_
@btk15049 Yuki Yoshida さんのツイートはまさにその M=1 である確率を M=2 となる確率と比較してるっぽいんですけど, M=2 の方が複雑なモデルなので M=2 の方が有利なんじゃないかなと思うんですが M=1 になる事前確率と言う意味で言ってます？
2021-05-30 23:27:49
btk
@btk15049
@mayoko_ 事前確率というとそうかも M=1とM=2ではどこかしらの特徴に差が出るはずなので、閾値じゃないけど、何かしらの事前情報を使ってM＝1を出すのはできてもおかしくないなと思いました 純粋な推定に近い手法だとM=2に偏りそうなのはそうかもと思ったりしてます
2021-05-30 23:32:38
pop_left
@pop_left
進行方向を変えるダイクストラ法、この問題設定ならノードを(x座標, y座標, 直前のaction)とすれば良いだけな気がする。（計算時間の問題？） カーブ時にペナルティが発生する経路探索アルゴリズム～AHC003を添えて～ - tsukammoの収穫記 tsukammo.hatenablog.com/entry/2021/05/…
2021-05-31 01:07:18
kusanoさん@がんばらない
@kusano_k
#AHC003 AtCoder Heuristic Contest 003 - Qiita qiita.com/kusano_k/items…
2021-05-31 02:01:30
harurun🌹偶奇はmod2
@harurun_p
はてなブログに投稿しました #はてなブログ 儚い AHC003 参加記 - harurun競プロ harurunppp.hatenablog.com/entry/2021/05/…
2021-05-31 02:07:14
いんたく
@contramundum2
#AHC003 今回マラソンやっている人は焼き鈍し法と関係が深いMCMCで頑張ってくるのかなぁと思ってたが、どっちかというと(最小二乗法を含め)正規分布を仮定する手法を使う人が多くてそうなのか、という気持ちになった
2021-05-31 04:22:37
いんたく
@contramundum2
正規分布仮定する方法、M=2の時を捨てて一直線上の道は同じ長さと仮定するとか、M=1の時を捨てて一直線上の道の長さが一次式の関係になっていると仮定するとかは手っ取り早く点数を取れるしやる人多そうと思った(実際僕も最初の二回の提出はこの二つだった)が、1740変数持った人思ったより多いんだなぁ
2021-05-31 04:26:04
いんたく
@contramundum2
1740変数持つと逆行列求めるのが愚直では計算量が重いのでWoodburyの恒等式で逐次的更新を行う(それでもギリギリなので頑張って定数倍高速化をする)のが筋かなと思っていたが、GC法使っている人を複数人見てなるほどなぁと思った
2021-05-31 04:32:19
いんたく
@contramundum2
Sigmoidとか非線形なモデルを立ててフィットするのは単純にコンテスト中に思い至らなかったが、この方針で結構な点数を得ている人もそこそこいて感心した
2021-05-31 04:38:20
kimiyuki@うさぎ🐇
@kimiyuki_u
#AHC003 順位表上 96.1G で 60 位でした。D = 0 を仮定して M = 1 と M = 2 のモデルをそれぞれ焼き鈍して良い方を使うだけです。計算機科学なんもわからん github.com/kmyk/atcoder-h…
2021-05-31 08:15:28
そすうぽよ
@_primenumber
考慮はしたがやらなかったこと 非線形なモデルの使用 -M=2のときに使えそうだと思ったが、CG法が使えなくなるので、毎回回すには計算量的に厳しそうだと思った 適当なタイミングで1回だけ走らせるなら不可能でないのは確かに -線形で全然性能出なかったらやるつもりだったが、97G点乗っちゃったので…
2021-05-31 08:27:29
そすうぽよ
@_primenumber
Mの値によるモデルの切り替え -まあ実質近いこと（Mを推定してweightの再調整）をしていたんですが、もっとダイナミックにスイッチしてよかった -実行時間が1000ms超えてたので、モデルを2つ持つのは怖かったが、序盤でいらないほうを捨てればいいのは確かに
2021-05-31 08:30:55
そすうぽよ
@_primenumber
推定した辺の重みの可視化 -スコアとM,Dの関係をプロットした時点で問題点自体は把握できてたので、辺の重み推定まで見る必要はないかなと思った
2021-05-31 08:37:26