2021年8月2日

AtCoder Heuristic Contest 003(抽出版)

https://togetter.com/li/1720580 を基に抽出させていただきました
1
bitrate @Bitrate0

AHCお疲れさまでした 暫定91,027,078,969点でした。 まずkが196までは上下左右に距離が1だと仮定したときの最短路を出力して、得られたスコア/経路長を辺に割り振っていく。 それより大きいときはダイクストラをして、同じように辺に割り振っていく。 #AHC003

2021-05-30 20:01:11
toast-uz @ToastUz

Python+Optunaで952億点 AHC003を深層学習で攻略 on #Qiita qiita.com/toast-uz/items…

2021-05-30 20:01:31
TERRY @terry_u16

#AHC003 お疲れ様でした。97.0G点で暫定19位。 フィードバックされた各パスの実距離と予想距離とのRMSEが最小になるような盤面を焼きなましで求めてダイクストラしました。平均成分とその分割点、平均からのズレの3つの情報を持たせて、ズレ量はL2正則化っぽいものを入れて過学習を防ぎました。 pic.twitter.com/LpPAd3uds0

2021-05-30 20:01:34
拡大
mamekin @mamemame_fujita

やったのは線形回帰でコスト(H_i,pとV_j,p)を推定するだけ。 ただ、それだけだと120変数あってクエリごとに実行するにはちょっと処理が重いので、 40変数をランダムに選んで他の変数は固定して回帰してた。(たまに120変数の回帰も混ぜる) #AHC003

2021-05-30 20:01:46
いなにわ💉💉 @inani_waon

#AHC003 おつかれさまでした。 今回は雑参加で、列と行の期待値と確度を お気持ちヒューリスティックで求めました。

2021-05-30 20:02:05
tomerun @tomerun

うーん手元だと973出てるけどだいぶ過学習しちゃってるっぽいな…。m=1と2だとだいぶ違うし200件では足りなかったか #AHC003

2021-05-30 20:02:09
ふぁる @fal_rnd

"Python+Optunaで952億点 AHC003を深層学習で攻略" from toast-uz qiita.com/toast-uz/items… #Qiita [bot]

2021-05-30 20:02:09
mamekin @mamemame_fujita

本当は各行、各列の分割位置(x_i, y_i)も推定したかったがそこは間に合わなかった。 実装始めたのは昨日からであまり時間もなく、線形回帰で色々バグらせたりして無駄に時間使ってしまった。 #AHC003

2021-05-30 20:02:36
ymatsux @ymatsux_ac

#AHC003 お疲れ様でした!971.4億で暫定テストでは10位です pic.twitter.com/aL9rrNm5WR

2021-05-30 20:02:39
拡大
じろう @Jiro_tech15

M=2はある程度倒せたんですが、Dが大きいケースが無理でした。

2021-05-30 20:02:58
毎日卒論 @pu__Ne

#AHC003 お疲れ様でした システス前順位 58位,システス前スコア 96.2G システス後スコア(予測) 963.7G H_1C_{i, 1}x_i + H_2C_{i, 2}x_i + \delta_ix_iで1つの辺の重みを表して確率的勾配法で更新する 最初H_1C_ix_i + H_2(1 - C_i)x_i + \delta_ix_iだったけど,なぜか自由度増やしたほうが高かっt

2021-05-30 20:03:04
prd🦍 @prd_xxx

#AHC003 お疲れ様でした 94161824540 点でした システス前136位ぐらいで個人的に健闘しました! 画像はseed 0です 序盤200ターンは横→縦→横みたいに曲がる回数は高々2回 残り800ターンは毎ターンdijkstraしました 距離の予測に使うスコアは終盤ほど重みをつけました あとできっと参加記を書きます pic.twitter.com/bBMw91YEpi

2021-05-30 20:03:14
拡大
sash @sash277

AHC003お疲れさまでした。94.4G。「行と列毎に共通の長さを焼きなましで推定→推定値を使った最短路のルートを出力」しました。M = 1と2を区別して手法切り替えたかったけど区別する方法わからず

2021-05-30 20:03:17
phyllo(フィロ) @phyllo

hとvを間違ってたりindexがずれてたりしてめちゃくちゃなのに、中途半端にスコアがでてしまって時間を無駄にしてしまった、、、

2021-05-30 20:03:20
チョモノリス @chomonolis

AHC003お疲れ様でした。提出時92722376624でした 問題文理解するまで30分くらいかかった・・・辺が未知ってのにビックリしたし、こんな問題がまともに解けること自体にも驚いた

2021-05-30 20:03:23
iwashi31 @iwashi31

バンディット問題大好きマンなので問題読んでめちゃくちゃはしゃいでた

2021-05-30 20:03:41
4b @Shibungi_kyopro

ノイズは無視してHip,Vjp,xi,yjについて焼きなます、評価値は実際の距離とのズレ +ちょっとした工夫 で94G #AHC003

2021-05-30 20:04:03
ヘクト🐬 @osrehun

AHC 003 お疲れ様でした. まず,問題を逆問題と捉えてノイズ込みのパラメータ推定問題として解釈した. ベースは Givens 回転 によるQR分解を用いたリッジ回帰を書いて 94G 200ターン目で M = 1 or M = 2 の判定を行う. M = 2 はパラメータの境界を各行各列ごとに黄金分割探索で調整 #AHC003

2021-05-30 20:04:07
さはら @shr_pc

お疲れ様でした #AHC003 97.29G 暫定6位 M=1 用の推定モデルと M=2 用の推定モデルを個別に用意して M=2 用の推定モデルの状況から問題タイプを推定してパラメータを混ぜつつ計算するみたいなことをしました 暫定スコアのセットはかなり渋い傾向にあったのでシステスでは 97.38G くらいが出ると予想

2021-05-30 20:04:19
nico_shindannin(診断人) @nico_shindannin

AHC003 おつじゃ。最終日にてきと~な妥協(焼きなまし)書いて終わった… - 推定でうまい手法がありそうと思って時間費やしてしまった…。 - 距離*比*でスコア得点が入るので、序盤にめっちゃ長いパスで情報集めれるのに終了30分前に気づいた。妥協解を昨日から書き始めれば気づいたと思うのじゃが…

2021-05-30 20:04:41
@lgeuwce

#AHC003 おつかれさまでした、暫定12位 pic.twitter.com/wk5OUhAUQc

2021-05-30 20:04:41
拡大
もふとんらぼ@プロコン用 @MohutonLab_comp

・初期75回まで1回しか曲がらないやり方で各辺の重みの目安を計算しておく(M=1のケースについて勝ちやすくなる) ・以降は初期75回までで求められた辺の重みよりダイクストラにて計算する。ここで得られた辺の重みもフィードバックする。 上記で92.9Gでした。M=2の対策が全く分からず。。。 #AHC003

2021-05-30 20:04:42
TERRY @terry_u16

M=1とM=2のモデル両方持つことも考えたけど、仕切りの左右で同じ値を推定すればあんま変わらんか!wでサボりました……

2021-05-30 20:04:42
毎日卒論 @pu__Ne

130ターンまでは一度通った辺にペナルティをつけて一度も通ってない辺を探索するようにした かなりテキトー

2021-05-30 20:04:46
残りを読む(364)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?