RECRUIT 日本橋ハーフマラソン 2025秋(AHC055)
問題概要
- N(=200)個の宝箱があり、各宝箱の硬さはH_i、宝箱iには武器iが入っている
- 各宝箱は、硬さが0以下になると開く
- 各宝箱は「素手」か「武器」で攻撃ができる
- 素手で攻撃する場合は、攻撃した宝箱の硬さを1減らす
- 各武器は、耐久値C_i (=1〜6)があり、攻撃をした場合、耐久値が1減り、攻撃した宝箱の硬さはA_{ij}だけ減る
- できるだけ少ない回数ですべての宝箱を開ける攻撃手段を求めよ
時間
個人的メモ
武器の性質
攻撃力 A_{ij} の生成方法
- 武器の攻撃力Aの生成方法が以下のようになっているため、小さい値が多く、いくつか大きい値があるような感じになる
- A_{ij} = round( 500/rand_double(1,500) )
- 硬さH_iは最大でも500なので、武器での攻撃が、効率がよい
攻撃力が低い宝箱に武器を使わない
- 攻撃力が1桁しかでないような宝箱に武器を使うのはかなり効率が悪いため、ある程度大きな値になっているもの以外はできるだけ使いたくない
- あえてその武器を使わずに、素手や他の武器で攻撃して、効率の良い宝箱に使ったほうがよい可能性がある
オーバーキルがあり得る
- A_{ij} と H_j の間には制約条件がないため、A_{ij} > H_j になる可能性がある
- 硬さ200の宝箱に対して500で攻撃できる武器がありえる
- 2つ以上の武器が使えるときなどに、一番攻撃力のある武器を使わないほうがよい場合がありえる
その他の重要な性質
最初に開ける宝箱
- 最初に開ける宝箱は、武器を持たないため、素手で開ける必要がある
武器の汎用性
- 残っている宝箱について、「複数の宝箱に強い攻撃力を持つ武器」と「特定の宝箱にだけ強い攻撃力を持つ武器」を持っていた場合、攻撃力というより、後者の割当方のほうが重要になる可能性がある
- (解説放送)
- 武器の強さを攻撃力ではなく、各宝箱に何%の攻撃ができるか、とその総和を評価値とするなどができる
1つの宝箱にのみ攻撃するのがよい?
- 細かい部分は無視して、各宝箱について、攻撃できる最大攻撃力を出力して見てみると、30%ぐらいは1回攻撃で宝箱を開けられるが、残りの70%ぐらいは複数回攻撃が必要な模様
- また、次点の攻撃力が最大攻撃力より結構下がってしまうものも多いため、できるだけ同じ武器で同じ宝箱に攻撃するのが効率がよいみたい
- 複数の宝箱に攻撃するような状態はグラフ構造が複雑で、近傍への遷移時にサイクルなどができやすくなって、遷移しにくくなるなどの可能性も？
できるだけ早く武器を集める
- 武器をできるだけ使いたいので、早く武器を集める方針が考えられる
- 開けやすい宝箱に対して優先度などを評価値として考慮するなど考えられる
アプローチ
貪欲
- (解説放送)
- 手持ちの武器で一番攻撃力のある宝箱に対して攻撃する、を繰り返す、などいくつか貪欲が考えられる
- しかし、途中状態での評価が難しく、最後の方で素手中心の攻撃になるとひどいスコアになり得る
- が、貪欲で上位に入っている人もいた模様
- 解説放送では貪欲解での強い方法が紹介されている
訪問順を焼きなまし
- 宝箱の訪問順を状態として持って、その順番に宝箱を手持ちの武器で攻撃する
- 訪問順を1点move,2点swapなどの近傍で変化させる
- スコアは、実際にシミュレーションして計算できる
- やってみると、制限時間2秒だと十分な探索ができていないようで、時間を伸ばすとスコアが伸びることがわかる
攻撃先(DAG)を焼きなまし
- 各武器でどの宝箱を攻撃するか？を考えると、DAGならば(サイクルがないならば)、トポロジカルソートして訪問順が決まる
- この場合、スコアの計算は、攻撃先の変化した宝箱だけを見て差分計算できるため、O(1)で行える
- DAGかの判定にはO(N)かかるが、DAGかの判定を受理判定後に行うことで、判定回数を減らせるため、探索回数が稼げる
- (受理判定の部分は、状態に更新がなかった場合なども区別してちゃんと更新があった場合のみ判定する)
- また、各武器で攻撃力が高い宝箱の上位何件かから選ぶようにしたり、同じ武器で同じ宝箱を何度も攻撃しやすくする、などの工夫をいれるとかなりスコアが伸びる
- (細かいメモ)
- 自分自身は攻撃先に選ばないようにする
- DAGかの判定は、1点更新の場合は、その頂点からサイクルができているかチェックするだけでよい(グラフ全体をチェックしなくてよい)
- 本番では「訪問順＆攻撃先を状態に持って焼きなまし」でやったが、そこから攻撃の仕方の方向ではなく、訪問順が不要＆差分更新、の方向に行ければよかった
その他
元ネタ
解説
Links