AHC記録

手法

貪欲、ビムサ

盤面評価値が作れる

強い貪欲がある

解の一部を変化させると解が崩れるときに使う

(ビムサ)高速な盤面評価値が最強

貪欲系だとわかったら盤面評価値を考えておく

工夫

理論値が取れると信じてどうすればそれに近づけられるか考える

天才貪欲はシンプルなものが多い→最初から複雑に考察しようとしない

山登り→焼きなまし

解の一部を変化させても大丈夫な時に使う

高速な近傍、スコア計算が最強

序盤に勝手な判断で探索空間を狭めるのはダメ

工夫(焼き方がわからないとき)

ルール違反をペナルティ付きで許容する

自主制約をつける

巨大な近傍(部分破壊再構築)なら焼けるか？

原則としてスコア上限の高そうなものから考える

原則　焼きなまし＞ビムサ

モンテカルロ

インタラクティブの時

全体の学び

探索は強い

評価関数は基本的にゴミ

種類を増やしすぎると爆発する

アルゴリズムの高速化技術を制約から連想して応用すると高速化ができる

未来は大事

AHC 59

初期解の作成を再構築と同じ方法で行う

初期解を作成した後で、部分破壊から再構築をしていく

再構築を貪欲で行うことで高速にできる

それぞれの行動を数列にした順列を作成する

初期解の作成

順列の中に新しい操作を挿入していく

挿入位置を全探索し、もっとも良かったところに入れる

破壊再構築

長さ15程度の部分を選択し、その部分を削除、それぞれを貪欲で挿入し直す

AHC 58

貪欲の評価を行動をとった結果のスコアに対して行うのではなく、行動をとった結果のスコアの増加に対して行うといい

初期解の作成

貪欲で行動する

優先して強化するIDを全探索してみて一番良かったものを初期解として採用する

焼きなまし

普通の焼きなまし

AHC 57

距離が2000以下になったもの同士をくっつけていき最後にグループ数がちょうどよくなるようにくっつける

AHC 55

評価値をいい感じにした貪欲

それぞれのターンで使える武器のうちもっともダメージを与えられるものを使えばいいのだがそれを全体に占める割合にすることで他の武器では全然ダメージを与えられないような箱に対しても有効な攻撃ができる

ビジュアライザを見て上手くいっていない部分にどんな傾向があるのかを分析する

AHC 53

使うカードを大きいカードと小さいカードの二種類にわけて作る

フェーズ1で大きいカードを割り当て、フェーズ2で小さいカードを割り当てる

初期解を作成した後それぞれの山とフェーズをランダムで選択し、そのフェーズのカードの残りカードを半分全列挙によって探索をし、最適化をする

あまりカードの数が少ないことに注目すれば半分全列挙ができることがわかる