さはら

貪欲から逃げない / heuristic competitive programming, AtCoder highest 3350+ / main: @shr_id / ex-{rogy, traP}

[さはら @shr_pc]

超僅差 (+1) で世界一になってた！！！
ちょっとプラチナ冠借りていきますね

saharanさんのHACK TO THE FUTURE 2026 （AtCoder Heuristic Contest 056）での成績：1位
パフォーマンス：3623相当
レーティング：3254→3367 (+113) :)
Highestを更新しました！
#AHC056 #HTTF https://t.co/qNxaG0AbZX

[さはら @shr_pc]

はい最強

[あしぃ @asi1024]

勝ちました

[よーちゃん @yochan_tech]

参考までに、実行時間1000倍で解いたseed=3(score=23)です！ #AHC064

[さはら @shr_pc]

nested beam search の発想はなかった

[Rafbill_pc @Rafbill_pc]

For a given state, children states are generated by an inner beam search: for every (i,j), keep the best W states whose last moves involved upper track i and lower track j.

[さはら @shr_pc]

最初1行ずつ揃えようとしたけど、
・揃えたブロックは消えたと見なせる
・1行分揃えれば10個消えたことになる
というところから
・連続した数字を作るのはもっと簡単にできて、1つ数字を繋げられればブロックが1つ減ったと見なせる
→ 1行ずつ揃えるより絶対お得
と軌道修正できたとこだけは偉かった

[さはら @shr_pc]

有を取得 (GP30 +0.5)

[さはら @shr_pc]

やばすぎ

[chokudai(高橋 直大)@AtCoder @chokudai]

#AHC064 1位！グッと睨んで貪欲を書いたら平均50手くらいだったので、ビムサにしました。seed0: 31手
以下AI解説。

1/ 評価関数 (核)
連続 ID ペア (10r+c, 10r+c+1) 90 組と、各線の先頭 (10r が dep[r][0] にあるべき) 10 個に対してペナルティ加算。0 が完成。

ペアの基本ペナルティ:
- 隣接連結済み: 0
- 即連結可能 (a が出発線末尾 + b が待避線先頭): 800 (REACH)
- 片端だけ露出: 1400 (ONE_SIDE_EXPOSED)
- どちらも未露出: 1500 (UNCONNECTED)

ペアの縦方向加算 (vertical):
- 同線・同種・正順非隣接: +60 (間に車両が挟まってる、退避必要)
- 同線・同種・逆順: +800 (めちゃ重い罰)
- それ以外 (別線/異種): +30

ペアの横方向加算:
- 線番号差 × 3

先頭 (Top) ペナルティ:
- ベースは同じ (REACH 800 / ONE_SIDE 1400 / UNCONNECTED 1500)
- vertical: 車両が出発線にいる → +60、待避線にいる → +100
- horizontal: 同じく線番号差 × 3

2/ 1 ターンの手の選び方 (DP)
ターン内では、(出発線, 待避線) のペアが昇順に揃ってないと交差してダメ。なので候補手のうち以下の制約で gain 最大化:
- 出発線 i は各 1 回だけ使える
- 待避線 j は昇順 (i 昇順 ⇒ j 昇順)

候補手 (i, j, k, type) のうち各 (i, j) で gain 最大の手を 1 つ取り、dp[i][last_j] で「i 本目まで処理済み・最後に使った待避線が
last_j」の状態を更新。最大 10 件まで同時実行可能な組み合わせを構成。

3/ 探索 = ビームサーチ + ランダム倍率
シンプルな貪欲だと局所解で止まる。各親ノードから候補手の評価値に 0.3〜1.0 のランダム倍率 を掛けて DP に流し、15
通りの「同時実行可能な手集合」を生成 (=15 子展開)、上位 W=200 状態を残す。多様性を強制注入。
初手だけ 100 通りに広げて初期分岐を増やす。

4/ 重複除去 (Zobrist)
別経路で同じ状態に着地する beam state を排除。ハッシュは O(1) 差分更新。

5/ 高速化
- 各候補の評価値計算を「現状からの差分」で O(1)
- 「k 個運ぶ」を「k+1 個運ぶ」に拡張する増分計算 (差分の差分)
- 状態は固定サイズ struct で memcpy snapshot

6/ 結果
平均スコア 4,968.84 / 5,000 (T=31 前後)。

[さはら @shr_pc]

切る→繋ぐで塊を大きくしていくビームサーチです
細かいところが詰められなかった…

[さはら @shr_pc]

うーーーん……
seed=0, turns=46, score=4954
#AHC064

[さはら @shr_pc]

排中律

[さはら @shr_pc]

これ散々回したんですが出ないので、思い違いだった可能性が高いです……（誰か出たら教えてください）

[さはら @shr_pc]

seed0、めっちゃ回したら51が出た記憶がある（時間10倍とか）

[さはら @shr_pc]

あれ、これそもそもパリティ的に51ってあり得る…？　もしかしたら記憶違いかも（回し直したら全然出ない）

[さはら @shr_pc]

いや一応あり得るか

[through @through__TH__]

#AHC063 暫定6位 49.38B で初 1 ページ目！
方針 :
・次の目標色を取りに行く
・短手数で自分の体を食べる
・頭に最も近い誤った箇所付近を食べる
・ランダムに散歩する
の4遷移によるビームサーチ

評価関数はシンプルで、目標を満たす prefix 長 * A + 盤面端にある餌のペナルティ * B

Seed 2 : 624

[さはら @shr_pc]

カーブが少ないといいの、距離系スコア使ってないからなのかな

[bowwowforeach @bowwowforeach]

目的の餌までの経路探索して移動、みたいなのもうまくいかなかった。
愚直に1マスずつ移動で、距離系の評価も使わず、ハッシュによる重複除去で遠くまで移動する候補を出した。BFSで経路探索してるみたいなイメージ。

[さはら @shr_pc]

これこれこれ

[数ごり @MathGorilla_cp]

体のカーブ数が少ない方が良い←非自明