simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Marathon Match 134 ShearTheSheep 参加記

問題

www.topcoder.com

戦略

  • どの農家がどの羊を追いかけるかの割当を最小費用流問題として解く
  • 対象への最良経路を探索
  • 羊毛のバケツリレーを行う

農家と羊の割当

どの農家がどの羊を追いかけるのかを最小費用流問題として解きます。辺の張り方としては「農家」→「羊」となるようにし、フローの量は「農家の数」とします。

f:id:simanman:20220324211559p:plain:w480

辺のコスト

S →「農家」は 0、「羊」→ T は 0、「農家」→「羊」についてはそれぞれコストを計算するための関数を使って定義を行います。また、各辺のキャパシティは 1 で定義します。

コスト計算では以下の要素を考慮します。

  • 対象との距離
  • 対象の羊毛の量
  • 周辺の羊毛の量
  • 納屋までの距離

対象との距離

対象までの距離をダイクストラ法で求めます。

距離が 4以下の「羊」については「壁」「木」と同様に通れないオブジェクトとして扱い、それ以上の距離にいる「羊」については距離に応じたペナルティを与えます。(ペナルティの係数は optuna で調整)、「農家」ついては交差したとしても羊毛を受け渡しが可能なので特にペナルティ無しで通過出来るようにしています。

羊毛の量

羊毛の量が MAX の時に成長のタイミングが来ると狩れるはずだったの毛の成長が行われないので実質スコアの減少となります。そのため、羊毛の量が MAX の状態の羊を優先的に狩るようにしました。

周辺の羊毛の量

保持できる羊毛の量 C が多い場合は連続で毛を狩るようにしておくと得点効率が良いので、対象の羊毛の量だけではなく周辺の羊毛の量も調べてそれも評価します。

納屋までの距離

ある程度羊毛を集めると納屋に戻って収める必要があるので、納屋までの距離も評価します。(この評価値はある程度羊毛を集めた農家だけに適用)

「農家」→「納屋」の辺を追加

ある一定量の羊毛を集めた農家に対しては「納屋」への辺の追加を行います。「納屋」→ T のコストは 0、 キャパシティは無限(農家の数より大きな値であれば何でも良いです)で定義し、「農家」→「納屋」のコストについてはダイクストラで計算した値に設定します。

f:id:simanman:20220324215816p:plain:w480

対象への最良経路を探索

目的への経路をダイクストラ法で探索します。「羊」との距離を詰める場合は、羊側の行動によって距離が短くなる候補が多くなるように行動します。(基本的にはY軸とX軸の長い方を短くするような動きになります)

羊毛のバケツリレー

納屋の数が少ないケース等では羊毛を収めに来た農家が詰まってしまうので、詰まった状態でも羊毛を納屋に収めれるようにします。

f:id:simanman:20220324235644p:plain:w320

f:id:simanman:20220324235723p:plain:w320

f:id:simanman:20220324235835p:plain:w320

f:id:simanman:20220324235902p:plain:w320

農家の行動順を入れ替えて納屋までの羊毛の受け渡しを 1ターンで終了させるようにすることで詰まること無く羊毛を収めることが出来るようになります。意図的にリレーを行うというよりかは詰まった時にこの機能が無いと不便だよねという感じです。

感想

2次元グリッドベース + マルチエージェント系の問題。スコア計算が線形的なとの「これをやれば爆発的にスコアが伸びる」みたいなのも特に無かったので、基本的な実装は前半で終わってしまって、後半は地味なチューニング作業が多くなってしまった。焼鈍系の問題が減った代わりにオンライン系の問題が増えてきた印象がある。いい感じの評価値もといコスト計算を行う方法が全然わからないので、機械学習でその辺りを改善できるなら実装していきたい気持ちがある。

optuna 今までは Best parameters しか見てなかったけど、今回は Visualization 機能でパラメータとスコアの関係を俯瞰的に見れて便利だったので今後も機会があれば使っていきたい。(本音はチューニングじゃなくて方針で差がつく問題をやりたい)

Seed  1: 251
Seed  2: 6048
Seed  3: 4250
Seed  4: 403
Seed  5: 1179
Seed  6: 187
Seed  7: 1997
Seed  8: 639
Seed  9: 1406
Seed 10: 382