AHC 029 - Kiri8128の日記

AHC 029 でやったことと参加記です。

プレテストは 6.4B で暫定26位です。

最終提出の説明です。バグなどもありますがそのまま説明しています。細かいところは一部省略しています。

評価関数による貪欲です。将来ターンのシミュレーションは行っていません。

引くカードの評価をだいたい次の表のとおりとして、「（カードの評価）－（コスト）」が最大のものを選択する。

引くカードの種類	評価
通常労働カード	現在持っているプロジェクトに使ったときの評価の変動量の最大値
全力労働カード	現在持っているプロジェクトに使ったときの評価の変動量の合計
キャンセルカード	現在持っているプロジェクトのうち評価が最低のものの $-1$ 倍
業務転換カード	現在持っているプロジェクトの評価の合計の $-1$ 倍
増資カード	$600 \times 2^{L}$

ただし、プロジェクトの評価はだいたい次のとおりとした。

また増資カードは $\displaystyle t \times (1 + \frac{p}{m - p + 1} \cdot \frac{1}{L + 5}) \le 999$ のときに限り引くこととした。

ここで、 $t$ はその時点のターン数、 $m$ はその時点での所持金、 $p$ はカードの価格、 $L$ はそれまでの増資回数。

増資カードがあれば必ず使用する

そうでなければ「（お金の変動）＋（プロジェクトの評価の変動）－（カード評価）」が最大のものを使用した。

プロジェクトの評価は上と同じものを使用した。カードの評価はだいたい次のとおりとした。

$N$ が大きいときも、選んだ直後のカードをそのまま使っていることが多かった（将来使う予定のカードをもう少し効率よくストックできると良かった）
増資カードは $2$ 枚以上連続で買うと $2$ 枚目以降のコストが下げられることに気付いたが、うまく使えなかった
高い買い物をしたときに、所持金不足で一定期間（ほぼ）ゼロコストのカードしか取れないみたいな状況に陥ることがあった。うまく指標化して避けるようにしたかったができなかった
適当にシミュレーションすると上がりそうな気がしたけど、それ以前にいろいろバグってできなかった