KLab主催の天下一 Game Battle Contest 2021 Springで24位でした。 github.com
すべてのタスク2つ組について、共通なsuffix・prefixを削除して連結した文字列を考え、単位時間あたりの内部に含まれているタスクを考慮した合計得点が最大の連結タスクを全てのbotで行いました。
きれいなビジュアライザが用意されており楽しいコンテストでしたが、 考えをまとめられず、不完全燃焼感が残ります。
最序盤
- ルールを読みました。
- ゲーム中APIを叩き続けてもよいことを確認しました。
- サンプルコードを動かしました。
- ビジュアライザを見ました。
- 10人部屋なのに5人しか居ないな……などと思いながら、
- ルールを読みました。
- 得点計算の方法
- 1人5bot
- 開始50分以降に高得点のタスクが入ってくる
開始50分で高火力のbotを作るコンテストという風に考えました。
序盤
サンプルプログラムをベースに改修しました。
- タスクを所要時間あたりの重みが最大のものを使うようにしました。
- 同じ文字が連続していた場合に中央に戻らず、x+1を経由するようにしました。
- タスクを重みではなく、所要時間あたりの得点が最大のものを使うようにしました。
- 自分の他のbotが狙っている分を考慮に入れました。
def estimate_task_score(task: object) -> float:
before = task['weight'] * (task['count']+task['aim']) / max(task['total']+task['aim'], 0.001)
after = task['weight'] * (task['count']+task['aim']+1) / max(task['total']+task['aim']+1, 0.001)
return after-before
中盤
タスクの文字列は重なっても良いというルールに気が付きました。
combine(tasks[i]['s'], tasks[j]['s']) の中にどれだけのタスクが含まれているかを計算し、連結したタスクごとに移動時間あたりの得点が最大になる連結タスクを選びました。
def combine(s: str, t: str):
len_s = len(s)
len_t = len(t)
for k in range(min(len_s, len_t)-1, -1, -1):
if s[-k:] == t[:k]:
return s + t[k:]
return s+t
残り1時間時点で10位に入っていました。
終盤
- 特に改善が思いつかないため、うどんを食べに行きました。
結果
- 最終的に24位まで順位が下がりました。
