「RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜」参加記

September 19, 2021

ヒューリスティックの一週間コンテスト「RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜」参加しました。

問題概要

${\rm X}$ は $16 \times 16$ マスからなる農場を所持している。この農場には 0 日目から 1000 日目にかけて様々な種類の野菜が生え、枯れる。野菜 $i$ は、 $S_i$ 日目の開始時に区画 $(R_i,C_i)$ に生え、 $E_i$ 日目の終わりに枯れる。また、野菜 $i$ は価値 $V_i$ を持つ。

この農場には各区画に一つまで収穫機を設置することができる。野菜 $i$ が生えている場所に収穫機が設置されている場合、以下の式に基づき、お金を得ることができる。

$V_i \times$ $i$ を収穫した収穫機を始点に上下左右に隣接する収穫機を辿って到達できる区画の数

お金を得た後、野菜は消滅する。

${\rm X}$ は最初お金を 1 持っている。 ${\rm X}$ はお金を使って収穫機を購入できる。収穫機の値段は以下の通り。

$(すでに持っている収穫機の数+1)^3$

${\rm X}$ は毎日、以下の行動のうち一つを行うことができる。

お金を消費し、任意の区画に新しい収穫機を設置する。
すでに配置されている収穫機の一つを任意の区画に移動する。
何もしない。

1000 日終了時点の ${\rm X}$ の所持金がなるべく多くなるように、 ${\rm X}$ の行動を決定せよ。

自分の解法

3,924,868,328 点で、110/519 でした。1 位は 5,651,440,905 点だったので、1 位の 70%くらいのスコアです。

問題を見て重要そうだと思ったのは以下のような点です。

収穫機が一つだけの場合、収穫機を最も価値が高い野菜の場所に移すのが最適解
収穫機が連結していると獲得金が跳ね上がる
パスはなるべくしないほうがいい

上記を踏まえ、以下のような方針を考えました。

収穫機を 2 つのグループに分ける。一方は収穫機 1 つのみからなるグループ(以降自由移動グループと呼ぶ)で、このグループに属する収穫機は自由に任意の区間に移動できる。もう一方のグループはそれ以外の収穫機からなるグループ(以降連結グループと呼ぶ)で、移動時は必ず連結を保つ必要がある。
最初の収穫機を自由移動グループとする。それ以降で購入した収穫機は連結グループとし、連結した収穫機のエリアを広げてコンボを狙う。
収穫機の購入は適当なターン数以降、行わないようにする。

基本的にはこの方針をベースにした貪欲法を実装し、それをどんどん改善していきました。

なお、本筋から外れますが、rust の場合解を以下のようにパラメータ付きの列挙型の配列として扱うことができるため、かなり取り回しが良かったです。

enum ACT {
    BUY(usize, usize),
    MOVE((usize, usize), (usize, usize)),
    SKIP,
}

let mut best_activities:Vec<ACT> = vec![];

ここからは、アルゴリズムの改善の時系列を書いていきます。

〜1.02 億点

まず、連結グループの収穫機を移動させない方針で考えました。連結グループの最初の収穫機(2 台目の収穫機)は最終日までに獲得できる野菜の価値の総和が最大となるマスに置くことにし、それ以降は収穫機が買える金額が貯まり次第、連結グループの最初の収穫機と同じ基準で最も良いマスを連結グループの隣接マスから選択しました。

「野菜の価値の総和が最大となるマス」の計算は、各マスごとに出現する野菜の価値の累積和をとっておき、

cum_sum[map_index(y,x)][1000]-cum_sum[map_index(y,x)][t]

のような形で $O(1)$ で計算するようにしました。

〜1.41 億点

上記の解法は 30ms 程度で終了してしまうので、時間を活用するために連結グループの最初のマスを「最終日までに獲得できる野菜の価値の総和が大きい」順で時間がくるまで試すことにしました。また、収穫機配置時にどれだけ未来まで見るかを、「最大まで」「20 日後まで」「収穫機の台数分まで(収穫機が多いほど長期的な視点で配置する)」の 3 つで試すようにしました。

この結果、1.4 億までスコアが伸びました。

~1.72 億

ここまで、自由移動グループの収穫機しか移動していませんでしたが、収穫機が 30 個以上になったら、連結グループも移動させるようにしました。移動方針は以下のようにしています。

その収穫機を無くしても連結が保たれるもののみ移動可能とする。
上記で移動可能となったもののうち、「未来の獲得野菜の価値の総和が最も低いマス」を移動対象とする。
連結グループに隣接するマスのうち、「未来の獲得野菜の価値の総和が最も高いマス」を移動先のマスとする。

上記の連結グループの移動を、自由移動グループの移動と比較し、より獲得金が高い方を移動として採用するようにしました。

また、収穫機の台数を最大 48 台に制限するようにしました。

収穫機を除いた場合の連結の判定は DFS でやりましたが、LowLink という高速なアルゴリズムが存在するようです。

~1.84 　億

「収穫機が 30 個以上」という縛りを消しました。また、評価関数としてみる未来を「最大まで」「20 日後まで」「収穫機の台数分まで(収穫機が多いほど長期的な視点で配置する)」の 3 つにしていましたが、「20 日後まで」が目に見えてスコアが良かったのでこれで固定させました。

また、ビジュアライザで確認した時、近くにある明らかに価値の高い野菜を取れていなかったので、 1 つのマスの評価を行う際に上下左右に隣接するマス＋そのマスの平均値を使って評価するようにしました。この時、すでに収穫機のあるマスは平均値の算出に含めないようにしたところ、大きくスコアが改善しました。

~1.95 　億

「野菜の価値の総和が最大となるマス」の算出時、

cum_sum[map_index(y,x)][1000]-cum_sum[map_index(y,x)][t]

では、過去に出現して未収穫の野菜を考慮できていなかったので、収穫に失敗した野菜の価値の総和と、収穫に成功した野菜の価値の総和を記録しておき、以下のように計算するようにしました。

cum_sum[map_index(y,x)][1000]- capture_values[map_index(y, x)] - miss_values[map_index(y, x)]

これでより正確に各マスの価値を算出できるようになり、スコアもはっきりと改善しました。

もっとできたと思ったこと

コンテストが終了し、たくさんの方が解法を公開しましたが、基本的には連結を保ったまま移動する方針が高得点をとっていました。これらの解法と比べると、自分の解法ではかなりの確率で自由移動が発生しており、例えばあと 2 手で連結グループで野菜を収穫できるという状況でも自由移動の収穫機で収穫してしまっていました。収穫期が一定数以上になったら自由移動を封印するようにしても良かったかもしれません。

また、連結判定のコストがまあまあ高くなっていたので、これは UnionFind などで高速化したかったです。

感想

今回のコンテストは点数が爆発的に増加する面白いスコアで、順位を上げるよりもむしろ 1 億点、2 億点などのキリのいいスコアを越えたい、といったモチベーションで頑張ることができました。単純にビジュアライザで見ているのも面白く、今までで一番楽しいヒューリスティックコンテストでした。