3.979G点で 106位/519人 でした。
最終解法の内容や考察内容とかを書いていこうと思います。
ざっくりの問題説明
二次元グリッド上で収穫機を使って野菜を収穫して、規定の日数の間でできるだけ多くのお金を稼ぐことを目指します。
野菜はそれぞれ所定の期間中セル上に現れ、その期間内に収穫期を野菜と同一の位置に置くことで収穫できます。
野菜ごとに異なる価値が割り当てられており、収穫することで (価値)*(そのマスに連結した収穫機数) のお金を得られます。
プレイヤーは1日に一回、以下のいずれかの操作ができます。
- 収穫機の購入・設置（購入費は
(購入台数)^3） - 収穫機を、他の収穫機と被らない任意の位置に移動
- 何もしない
(詳細なルールは他にもあるので、問題原文を参照してください。)
問題のポイントだと思ってるところ
- スコア計算式的に、収穫機は連結しておくのが基本強いはず*1
- ターン数1,000、盤面サイズ256、野菜数5,000、とコアな要素のサイズが大きく、実行時間の制約が中々厳しい
- 野菜の価値が取り得る値は、最小値は一定で最大値はターン経過に応じて指数的に伸びる。かつ、基数は固定で指数部が一定範囲の数値から一様ランダムに選ばれるため、価値の大きい野菜ほど出現率が低い。
最終提出解法の説明
コードはこちら https://atcoder.jp/contests/rcl-contest-2021-long/submissions/25807010
前半と後半でロジックを変えています。後半部分がメインのつもりです。
前後半共通でやっていること
- 収穫機は連結を保つ
- 野菜は10日先んじて出現させる(収穫はS_iを迎えるまでできない)
- 収穫機の購入は825日目までで、買える場合必ず買う
- 野菜の内、価値がその日にあり得る最大価値の
に満たないものは事前に削除しておく
- 価値の大きい野菜ほど出現率が低いため、野菜数的には
個くらい消せる。
- 価値の大きい野菜ほど出現率が低いため、野菜数的には
0~399日のロジック
ビームサーチをしました。
ビーム幅20で、収穫機連結成分の隣接マス達の内、以下の条件を満たすものを遷移対象ノードとして選択しています。
- 野菜が存在する
- 隣接マスのいずれかに、収穫機が無いかつ野菜が設置されているものがある
遷移に使うコマンドは、購入できる時は購入を選び、そうでない時は移動を選びます。 移動元の収穫機は、連結を崩さずに外せる収穫機の内「向こう10日間で設置予定の野菜が無いマス」にある収穫機達の中からランダムに１つ選んでいます。
評価関数は、「総獲得金額*2 + (現設置マスと重なっている先んじて設置された野菜の価値)*0.5」としました。
400日~ゲーム終了までのロジック
貪欲法です。
収穫機が連結した状態を保ちながら、(価値) / (連結成分との最短距離) が最大の野菜に伸ばす、を繰り返す感じでした。
移動元の収穫機の選び方は、399日までと同様、連結を崩さずに外せる収穫機の内「向こう10日間で設置予定の野菜が無いマス」にある収穫機達の中からランダムに１つ選ぶ、としています。
なぜこのようにしたか
元々は、前半戦に使用してるビームサーチを全ターンで使用していたのですが、スコアが伸びず*3、ビーム幅も4しか出せずで困っていました。
ただ、ローカルでビーム幅を100まで広げる*4と 1.75倍近いスコアを出せていたので、ビジュアライザを見ながらここの違いが何によって生じているのかを考えて、中距離にある価値が大きい野菜を拾えていないところが不味そうと当たりをつけました*5。
その考察が良さそうかを調べるために、とりあえずで (価値) / (連結成分との最短距離) が最大の野菜に伸ばす、という雑な貪欲を試してみたのですが、これが思いのほか上手くいったのでそのまま後半戦のロジックとして採用しました。
前半戦部分は、野菜の最大価値と最小価値との差が小さいので遠くの野菜を取りに行くメリットはあまり無さそうに感じたので、引き続きビームサーチ解を使用しました。 実際入力50ケースで試した平均値を比べてみると、こちらの方がスコアが若干良かったです。
問題に対する所感
今回はアプローチの選択肢が多いように感じて、その辺りが楽しくもあり難しくもありって感じでした。 ゲームモデルはどう作るのが良いんでしょうね。特に野菜の持ち方が時系列の問題とかも絡んで来て悩みどころでした。
焼きなましは今回どうなんでしょうね。取る野菜とその順番 とかでなんとかならないもんかな、とかを考えたりもしたんですが自分は詰め切れずでした。上位に焼きなまし解があったら見てみたいな。
その他余談
ビームサーチ解を追ってた時に、今回初めてプロファイラ(cargo-profiler)を導入してみました。Macで使うには一準備必要だったので、この辺も簡単に記事にまとめてみたいなとか思ってます。*6
感想
当たり方針を掴めたのが終了2.5時間前とかだったので、そこから詰める時間が取れずに終わってしまったのは残念でした。掴んだ方針を元に、例えば「価値が高めの野菜への連結」を遷移にする、とかでビームサーチのパターンを色々試してみたかったんですが・・。
とはいえ一方で、諦めずに検証を繰り返して当たり解法に辿り着けたのは、達成感と成長を感じられて嬉しかったです。長期AHCの中で過去最高順位取れましたし。
