-
threecourse
- 2834
- 0
- 0
- 0
-
- いいね！0
takumi152💉💉💉💉
@takumi152
#AHC003 やったこと (暫定24位(96.8G)) 焼きなましでテストケース生成に使われたパラメータを推測する。評価関数は、あるパスにおける推測値から求められた距離をa、実際に返ってきた値をbとして、1.0-(1.0-min(a,b)/max(a,b))^2を今までのクエリ全てに対して求め、その総和の最大化するもの。→
2021-05-30 20:04:51
kens
@kens_kyopro
#AHC003 解法(95.1G) (1) D,δ,γは無視. HとVを推定する. (M = 2 を考慮するため全てxi , yi = 15として考える. 異なる辺は116本. 最初は全て5000に設定) (2) 最短路は単純にDijkstra法で計算. クエリごとに与えられる長さと使った辺から一次方程式が作れ, 連立一次方程式を立てる.
2021-05-30 20:05:01
olphe
@_olphe
各辺の重さの推測を頑張る。 全ての辺について推測コストを持っておいて、返ってきたコストに近づけるように各辺のコストを修正する。あんまり選ばれていないものはより大きく動かすようにした。 同じ行、列の辺はコストが近いことが多いので、推測に利用した。
2021-05-30 20:05:12
Toy
@mdstoy
#AHC003 お疲れ様でした 93.3Gで暫定168位 参戦記はだいたいかけているのだけど、公開はシステス後にするか 今からABCとこどふぉもあるし
2021-05-30 20:05:19
にゃにゃん(運用終了しました)
@Nyanyan_Cube
#AHC003 暫定66位でフィニッシュ。114ターン目までは各列/行のコストを同一視した推定コストと各列/行の訪問回数でダイクストラ、その後焼きなましで各道のコストを推定して、その後は8クエリごとに山登り。画像はseed=17で98.2点 pic.twitter.com/zzdd7RfMlS
2021-05-30 20:05:27
拡大
ふくちゃん
@fkyrz_0111
AHC003 プレテスト179/1000位でした ダイクストラしながら長さを調整しつつ、道ごとに短い道長い道があるからそこも調整していくっていう方針でやりました M = 1のときはこれでいいけど、M = 2の道の途中で長さが極端に変わる場合どう対処していいかわからず点数が伸び悩みました pic.twitter.com/6KR98Hhdyy
2021-05-30 20:05:33
拡大
そすうぽよ
@_primenumber
AHC003お疲れ様でした #AHC003 基本方針 経路長は辺の重みの(線型)和なので、min||Ax-b||_L2を解きます これはA^tAx=A^Tbを解けばよく、CGLS法とかを使うと爆速です 辺の重みの生成ルールより、同じ行/列の辺の重みはかなり近いので、隣り合った辺の重みの差もAに入れて最小化するとよいです (続く)
2021-05-30 20:05:37
かつっぱ@ 競プロYouTuber
@catupper
AHC003: 93.8G M=1を仮定して、HとVを線形回帰してグラフを作りなおす。を毎回やった #AHC003
2021-05-30 20:05:48
そすうぽよ
@_primenumber
(続き) 大きすぎる/小さすぎる重みの辺を抑制するために、辺の重みの平均-5000も最小化対象に入れます 同じ行の辺同士の重みの差をさらに近くするため、辺の重みの差ペナルティを同じ行の両端に対しても掛ける ただ、M=2だと逆効果なので、lossを見てM=2っぽかったら無効化します #AHC003 (続く)
2021-05-30 20:05:52
甲斐性なし
@YamagenSakam
#AHC003 お疲れさまでした。96.7Gで暫定28位でした。 段階的に推定単位を細かくしていくMAP推定をしました（推定に逆行列はシャーマン・モリソン公式を使って逐次的に計算）。
2021-05-30 20:05:56
ろい
@Roy_R_
#AHC003 基本はダイクストラ法。辺の長さの推定は、各クエリごとに推定値との差で更新と、100回ごとに全体を焼き鈍し。 焼き鈍しは各辺を直接推定ではなくて、入力生成方式におけるHとxの推定をした。評価関数は、今までのクエリで与えられたデータとの合致具合。
2021-05-30 20:05:57
toast-uz
@ToastUz
タグ付けセルフリツイート #AtCoder #AHC003 最後伸びなくなったので記事書いていました😎 twitter.com/ToastUz/status…
2021-05-30 20:06:15
toast-uz
@ToastUz
Python+Optunaで952億点 AHC003を深層学習で攻略 on #Qiita qiita.com/toast-uz/items…
2021-05-30 20:01:31
そすうぽよ
@_primenumber
(続き) 経路長に関する最小化では、経路の辺の数で正規化したほうが、辺の数が多い物を重視しすぎないので良い MやDの値によって、辺の重みの差のペナルティの重みを変えるため、lossに応じてスケールさせる #AHC003 (続く)
2021-05-30 20:06:17
kibuna
@kibuna41
#AHC003 お疲れさまでした。 すべて正規分布でH, V, delta, gammaに事前分布を与え、(mean-分布幅)のucb的な距離を各辺に与えてdijkstraで最短経路を計算、ベイズ更新的に事後周辺分布を計算していました
2021-05-30 20:06:17
ヘクト🐬
@osrehun
250ターン, 300ターン, 350ターン,400ターン でかつM = 2 の時にパラメータを改善する．こんなことをして，95.8G になりました．暫定のテストケースは M = 2 のケースが多い気がした． #AHC003
2021-05-30 20:06:23
やまけー
@yamake_cpp
お疲れさまでした〜 毎ターンダイクストラで経路を出して、フィードバックとダイクストラての経路長の差分/100を加える 200ターンに一度盤面破棄して作り直し&山登りをしました #AHC003
2021-05-30 20:06:34
そすうぽよ
@_primenumber
(続き) M=2の時が依然として厳しいので、M=2っぽいなら行の中央付近では辺の重みの差のペナルティを減らす さらに、中盤あたりでx_i, y_iを推定してそこのペナルティーを減らす #AHC003 (続く)
2021-05-30 20:06:41
かつっぱ@ 競プロYouTuber
@catupper
M=2の場合はちょうど真ん中で切りかわると仮定してやればちょっとはましになるはずで、実際ローカル環境だと点数が1Gくらい増えたんだけど、提出したら点数が減った たぶんＭ＝２のケースの個数がローカルと本番で違ったんでしょう
2021-05-30 20:06:59
そすうぽよ
@_primenumber
(続き) optunaでハイパーパラメータチューニングをした 自宅の計算機5台計48コアで大量のケースをぶん回した(最終的には7680ケース) #AHC003
2021-05-30 20:07:00
US_cube
@US_kyopro
AHC003 やったこと ・マンハッタン距離で愚直に進む -> 63179310956点 ・通ったところの辺にスコアを追加して、ダイクストラ -> 87975428893点 ・最後に、辺にスコアを割り振るときの値などを調節 -> 88650688338点 これ以上は思いつきませんでした
2021-05-30 20:07:02
kuuso
@kuuso1
AHCお疲れ様でした．マジで何もわからないので毎回ダイクストラして正答との差分の1歩当たりの平均で重みを更新して～みたいなのを出したけど71Gしか出ませんでした．．
2021-05-30 20:07:03