ろい

競プロ/KO/AtCoderアルゴ水色(Highest:1584)/AtCoderヒュ青色(1905)

[ツカモ @tsukammo]

AHCでMLしようの記事、ありがたやありがたや。最後の強化学習で勝ちたい、全人類思ってそう。 https://t.co/CO0yg7d2As

[エチレン @ethylene_66]

AHC061お疲れ様です。暫定1位です。
解法は強化学習です。
学習に用いたコードと振り返り記事です。
https://t.co/lR1z5B99vP

[ろい @Roy_R_]

#AHC048
お疲れ様です。
4*4パレットをいくつも作って「新しい絵の具と混ぜるか、そのまま出すか、隣のパレットと混ぜるか」の貪欲をしました。300位以内くらい。
上位解法に面白いのが多くて、もっと時間とって考えたかったな。

[数ごり @MathGorilla_cp]

#AHC048 暫定4位
左側に20本のタンク、右1列にインク合成場を用意。
タンクの仕切り(縦線)2本を動かすことで、合成場にインクを送る操作ができるので、h毎に「各タンクの仕切りの動かす量 & インクkを追加するか」を焼きなまし。

差分更新可能なので、毎ターン10^5回程度回りました。

[ぴぃいいいい @AcPiiiii]

#AHC048 暫定2位!!!!!!!
お疲れさまでした!!

K本の通路に各色を置いておいて、通路を開け閉めしながら適当な4色を任意の量取り出して混ぜ合わせました

[よすぽ @yosupot]

#AHC048
T large
- 熱烈ペンシルパズルを行い、強力な盤面を作る(K=7 / 長さすべて57 / 平面グラフが最大辺数 / 各隣接パスの端点で隣接)
- ある点 + 隣接3点の三角錐マージ(謎用語)で幅100ぐらいのビームサーチすると大事故を避けまくるようになり、seedによっては3桁点とかになる

[ymatsux @ymatsux_ac]

遷移1：隣り合う二つのクラスタをマージし、その頂点に対して MST を求め、そこから一つの辺を除くことで二つのクラスタに再分割する遷移（できない場合もあるがその場合は棄却）

[ymatsux @ymatsux_ac]

#AHC045 暫定3位解法
- 頂点集合 A についてクエリしたとき、2頂点 (u, v) ∈ A について、(u, v) が MST に含まれないならば、MST での (u, v) パス上にあるどの辺よりも長いという情報が得られる。このような不等式を得たら、それに整合するように反復法で座標を更新する

[ろい @Roy_R_]

#AHC045
暫定74位。
やったこと:「推定」と「構築」
推定:適当なクエリを送り、現在の位置推定との差で更新。
構築:優先度付きのBFSで構築して、適当に山登り。長い辺ほど優先して選択。

推定について、3頂点の場合だけ、確定頂点2点で未確定頂点の位置を厳密に推定。

[ゆうき🌙🌙🌙🪼☁🦁😈👾❤️‍🩹😈🫐🗼🎠🫧🏴‍☠️ @yuuki_n_n]

え、今日ってあのヒューリスティクスと機械学習を融合させた独自文化で、不動産管理プラットフォーム業界で確固たる地位を築きつつあるTHIRDのAHCじゃん！
しかもwriterはAHC常連で数々の高成績を誇るShun_PIさんだ！
懇親会もあるとかアツすぎ！これは参加するしか！
https://t.co/ISmI7cC9Qf
#AHC045

[さはら @shr_pc]

AHC043 参加記 & 1位解法解説 - おいもログ
https://t.co/AHs0sPkGJa

最終1位解法と延長戦1位解法（※投稿時点）の解説を書きました！
#AHC043 #rcl_procon

[ろい @Roy_R_]

2000！　キリがいい入黄！　ギリギリ滑り込み！

AHC043での成績：175位
パフォーマンス：1853相当
レーティング：1972→2000 (+28) :)
Highestを更新し、初段になりました！
#AtCoder #RECRUIT日本橋ハーフマラソン2025冬
https://t.co/NJmX8GNhHj

[tomerun @tomerun]

@MathGorilla_cp fast-clearing array と呼ばれることがあるようです
https://t.co/ixUhED59GF

[数ごり @MathGorilla_cp]

ほとんどの長期コンでこれを使って数倍の高速化してるんだけど、何か名称無いんかな？
BFS以外の色んな場面で使える汎用性あるから、オブジェクトプーリング、ダブルバッファくらいの偉大さを感じてる。

https://t.co/722AQkJwOS

[きり @kiri8128]

#AHC043

最初の2駅を決めたあと、順に駅を決めていく貪欲。
線路は陽に持たず長方形領域を占有することにして、領域内に新しい駅を追加する場合は長方形を更新する。
（これで厳密にスコアが再現できる。）

長方形領域の交差判定は Disjoint Sparse Table で O(1) でできるから高速化してビムサす

[さはら @shr_pc]

49,27B で暫定 2 位でした
前半で駅を置くビームサーチ（1000-1500 ms）、後半で焼きなましをしました
どちらも差分計算を滅茶苦茶頑張って高速化します
焼きなましの遷移は駅の順番入れ替え、移動、親の付け替え、追加と挿入、削除、貪欲改善
↓ は seed=1 の様子 #AHC043

[ymatsux @ymatsux_ac]

#AHC043 暫定17位解法

最終解法はビームサーチでした。評価関数をがんばったので、貪欲でも40B程度はあると思います。

評価関数は
・基本は現在の資金と収入からわかるゲーム終了時のスコア
・片側だけカバーしているものを0.x倍の収入としてカウント（以下詳述）

Seed 0: 713603

[ろい @Roy_R_]

#AHC043
お疲れ様です。暫定172位。
基本的に貪欲法だけ。ビームサーチに改良しようとしたが、実装しきれず……。
BFS毎ターンは流石に重いが、何か差分とかで高速化できる方法あるのかな。

[TERRY @terry_u16]

AHCのテストケース実行ツール、pahcer v0.2.0をリリースしました！

mac版にて途中でテストケースが止まってしまう問題等が修正されています。
また、AHC042などで平均スコアの変化が分かりづらかったことを受け、小数点以下まで表示されるようになりました。

是非ご活用ください！