HTTF2019本選:モンスターテイマー
オープン位だったので記念に投稿。本選の人と合わせると位かな?
(:億点が出たので追記しました)
正の得点を得る
この問題では,正の得点を得るのは容易だ。高橋君も討伐依頼も無視し,ひたすらアルバイトする。
Submission #3692024 - HACK TO THE FUTURE 2019 本選オープン
レベル上げは重い...?
問題文をぱっと見ると,レベル上げのコストがかなり重そうに見えた。そこでとりあえず,討伐依頼のうち,必要なスキルレベルの最大値がであるもののみを相手にすることにしてみる。最初はすべてのスキルのレベルをにすることを目指し,その後はひたすら討伐する。テストケースの作り方より,相手にする討伐依頼は個くらいだろう。
提出してみると点で思ったより良かった。
Submission #3692352 - HACK TO THE FUTURE 2019 本選オープン
それでもレベルは上げたほうがいい
この時点ですでに億点に乗せている人がいたため,何かを勘違いしているのだろうと察する。どうやら,レベルは上げてしまった方がいいらしい。簡単に見積もってみる。すべてのスキルのレベルをにするのに必要な金額は
やはり重いように見えるが,ここですべてのスキルを上げたときに,討伐によってどれくらいの報酬が見込めるかを考えてみる。それは,テストケースの作り方から見積もれる。まず,ターンにたいして依頼は個あるから,各ターンに個はそのターンが締め切り日であるような依頼があると考えてよい。また,個もあれば,つくらいは必要スキルの総和がくらいのものがあることを期待することにする(そんなに変な期待ではないはず...)(レベルmaxなので,各ターンで報酬が最大のものを取るのが基本になることに注意,もちろん実際に見るのはの値だが)。さらに,スキルボーナスも必ず獲得できる。そうすると,討伐によって見込める利益は
であり,たった1回の討伐で元が取れそうとわかる。(ちなみに実際に平均を取ってみるとくらいでした,すいません。一応元は取れていますが。)
要は,
- 前半はできるだけ早くすべてのスキルをmaxにする
- 後半は討伐内容をうまく選んで,報酬を最大化する
という問題にしてしまった方が,後半でがっぽり稼げるので最終的にもスコアが高くなるのである(基本はそうというだけで、実際は後述するようにレベルを上げながら何をするかということも重要になってくる)。すぐには確信できない部分はあったが,時間はあるので物は試しという気持ちでとりあえず実装する。もう少し詳しく書くと
- 討伐依頼のリストは締め切り時刻ごとに管理する。
- トレーニングするお金がないとき:その時点で報酬が最も高い討伐をするか,アルバイト
- トレーニングするお金があるとき:トレーニングする。すべてのスキルをレベルに→すべてのスキルをレベルに→...→すべてのスキルをレベルに となるようにトレーニングする。スキルから順番にレベルを上げる。
- すべてのスキルレベルがになったら,そこからは各ターンで最も高い報酬の得られる討伐を行う。
これを実装して提出するとなんと億点!ナイーブな発想だが,これがちゃんとできるかが一つの山だったようである。
Submission #3693049 - HACK TO THE FUTURE 2019 本選オープン
地道な工夫
ここからはろくなことができなかったので,実際にやった地道な工夫を紹介。
- レベル上げの途中にも,おいしい討伐依頼が転がっている可能性がある。そのため,報酬がある閾値を超えるような討伐依頼は受けるということをする。計算時間が余っていたので,このは適当そうな範囲を探索した。
- レベル上げが終わってからは,受ける討伐依頼を前から決めるより,後ろから決めた方がスコアがよかったのでそうした。この貪欲も厳密ではない(短期間の依頼は報酬の落ち方が激しいため,その分損をする可能性がある)。
- 全く本質的ではないが,スキル上げの順番を通り(だけ)試していい方を選んだら少し上がった。
というわけで,最終結果となった提出がこれだった。
Submission #3694390 - HACK TO THE FUTURE 2019 本選オープン
反省と感想
- レベル上げの順番を焼きなましやら山登りやらするといいらしい。試してみていい結果がでたら加筆します。
- レベル上げの途中にどの討伐依頼を受けるかというところでも工夫の余地がある。
- 後ろから貪欲に加えてつ前のターンとの差分を考えるとうまくいくらしい。
- 楽しかった。来年は新卒枠なので賞金を狙えるくらいになりたい...。
追記():山を登る
山登り法を試したところ効果があったので,その詳細を述べる。
レベル上げの順番を最適化することを考える。レベル上げの順番は,からのスキルの番号を個ずつ持つ大きさの配列で管理する。例えば,配列のという部分は,「スキルのレベルを上げる→スキルのレベルを上げる→スキルのレベルを上げる→スキルのレベルを上げる」ということを意味する。の初期値をてきとーに設定し,そこからつの要素をswapした配列に対しターン分のスコアを計算し,良くなれば採用,ということを制限時間いっぱいまで繰り返す。
山登り法では,できるだけシミュレーション回数を増やしたいため,サボれるところはサボることを考える。レベル上げ終了後は,レベルをどういう順番で上げたかということに依存せずに行動を決定できる。今回は,レベル上げ終了後は「ターンの遅い順に討伐する依頼を決定する」という方針を引継ぐことにする。山登りを始める前に,ターンからレベル上げ後の行動に移るときの報酬の総和と行動を事前に求めておけば,だいたいターン分くらいはサボれることになる。
ここまでやったのが以下。億点で,やはり「レベル上げの間でも取るべき報酬は取る」ということが必要そうだ(とはいっても,レベル上げの順番を考えないよりははるかに高いスコアだ)。
Submission #3707961 - HACK TO THE FUTURE 2019 本選オープン
では,レベル上げの間に取るべき報酬をどう決めるかということを考える。なぜわざわざレベル上げの途中に報酬を貰いに行くかというと,その報酬がレベル上げ後に取る報酬といい勝負だからであろう。よって,レベル上げ後に取る報酬を用いてこの基準を定める。具体的にどう決めるかはいろいろあるが,
「(今からストレートでレベル上げが終わるターンターン)後に得る報酬」
以上の報酬であれば,取りに行くことにした。や「ターン」という謎の数字はエスパーで決めた。
これを提出すると,運が少し良いと億に乗る(だめでも億はある)。安定してより高いスコアを出すにはさらなる工夫が必要そう...。
Submission #3708880 - HACK TO THE FUTURE 2019 本選オープン
追記(12/07):焼きなまし法を試したら4.13億に到達。パラメータ調整が難しすぎる。今は温度を減らしていない(は?)のでまだいけるかも?
Submission #3730828 - HACK TO THE FUTURE 2019 本選オープン
おまけ
ビジュアライザでは種類の高橋君が登場するらしいのでコンプした。うち種類は上に挙げたので省略。