HTTF2019本選:モンスターテイマー

オープン $4$ 位だったので記念に投稿。本選の人と合わせると $14$ 位かな？
( $12/03$ : $4$ 億点が出たので追記しました)

問題

　モンスターの高橋君(?)を育てながら，野良モンスターを討伐し，所持金を増やすという問題。

f:id:sigma1113:20181201233818p:plain:w300 — 初期状態の高橋君

正の得点を得る

　この問題では，正の得点を得るのは容易だ。高橋君も討伐依頼も無視し，ひたすらアルバイトする。
Submission #3692024 - HACK TO THE FUTURE 2019 本選オープン

レベル上げは重い...?

　問題文をぱっと見ると，レベル上げのコストがかなり重そうに見えた。そこでとりあえず，討伐依頼のうち，必要なスキルレベルの最大値が $1$ であるもののみを相手にすることにしてみる。最初はすべてのスキルのレベルを $1$ にすることを目指し，その後はひたすら討伐する。テストケースの作り方より，相手にする討伐依頼は $30000\times 0.1=3000$ 個くらいだろう。
　提出してみると $14509$ 点で思ったより良かった。
Submission #3692352 - HACK TO THE FUTURE 2019 本選オープン

それでもレベルは上げたほうがいい

　この時点ですでに $2$ 億点に乗せている人がいたため，何かを勘違いしているのだろうと察する。どうやら，レベルは上げてしまった方がいいらしい。簡単に見積もってみる。すべてのスキルのレベルを $10$ にするのに必要な金額は
$10\sum_{k=1}^{10}k\cdot 2^k = 1.8434\times 10^9$
やはり重いように見えるが，ここですべてのスキルを上げたときに，討伐によってどれくらいの報酬が見込めるかを考えてみる。それは，テストケースの作り方から見積もれる。まず， $1000$ ターンにたいして依頼は $30000$ 個あるから，各ターンに $30$ 個はそのターンが締め切り日であるような依頼があると考えてよい。また， $30$ 個もあれば， $1$ つくらいは必要スキルの総和が $50$ くらいのものがあることを期待することにする(そんなに変な期待ではないはず...)(レベルmaxなので，各ターンで報酬が最大のものを取るのが基本になることに注意，もちろん実際に見るのは $C_i$ の値だが)。さらに，スキルボーナスも必ず獲得できる。そうすると，討伐によって見込める利益は
$(1.3^{50}\times 1000) \times 10 \times 10 \approx 4.9\times 10^{10}$
であり，たった1回の討伐で元が取れそうとわかる。(ちなみに実際に平均を取ってみると $3.0\times 10^9$ くらいでした，すいません。一応元は取れていますが。)
要は，

前半はできるだけ早くすべてのスキルをmaxにする
後半は討伐内容をうまく選んで，報酬を最大化する

という問題にしてしまった方が，後半でがっぽり稼げるので最終的にもスコアが高くなるのである(基本はそうというだけで、実際は後述するようにレベルを上げながら何をするかということも重要になってくる)。すぐには確信できない部分はあったが，時間はあるので物は試しという気持ちでとりあえず実装する。もう少し詳しく書くと

討伐依頼のリストは締め切り時刻ごとに管理する。
トレーニングするお金がないとき:その時点で報酬が最も高い討伐をするか，アルバイト
トレーニングするお金があるとき:トレーニングする。すべてのスキルをレベル $1$ に→すべてのスキルをレベル $2$ に→...→すべてのスキルをレベル $10$ にとなるようにトレーニングする。スキル $1$ から順番にレベルを上げる。
すべてのスキルレベルが $10$ になったら，そこからは各ターンで最も高い報酬の得られる討伐を行う。

これを実装して提出するとなんと $2.9$ 億点！ナイーブな発想だが，これがちゃんとできるかが一つの山だったようである。
Submission #3693049 - HACK TO THE FUTURE 2019 本選オープン

f:id:sigma1113:20181202160326p:plain:w300 — レベル $10$ の高橋君

地道な工夫

　ここからはろくなことができなかったので，実際にやった地道な工夫を紹介。

レベル上げの途中にも，おいしい討伐依頼が転がっている可能性がある。そのため，報酬がある閾値 $s$ を超えるような討伐依頼は受けるということをする。計算時間が余っていたので，この $s$ は適当そうな範囲を探索した。
レベル上げが終わってからは，受ける討伐依頼を前から決めるより，後ろから決めた方がスコアがよかったのでそうした。この貪欲も厳密ではない(短期間の依頼は報酬の落ち方が激しいため，その分損をする可能性がある)。
全く本質的ではないが，スキル上げの順番を $2$ 通り(だけ)試していい方を選んだら少し上がった。

というわけで，最終結果となった提出がこれだった。
Submission #3694390 - HACK TO THE FUTURE 2019 本選オープン

反省と感想

レベル上げの順番を焼きなましやら山登りやらするといいらしい。試してみていい結果がでたら加筆します。
レベル上げの途中にどの討伐依頼を受けるかというところでも工夫の余地がある。
後ろから貪欲に加えて $1$ つ前のターンとの差分を考えるとうまくいくらしい。
楽しかった。来年は新卒枠なので賞金を狙えるくらいになりたい...。

追記( $12/03$ ):山を登る

　山登り法を試したところ効果があったので，その詳細を述べる。
レベル上げの順番を最適化することを考える。レベル上げの順番は， $1$ から $10$ のスキルの番号を $10$ 個ずつ持つ大きさ $100$ の配列 $p$ で管理する。例えば，配列の $\{\dots,1,3,10,1,\dots\}$ という部分は，「スキル $1$ のレベルを $1$ 上げる→スキル $3$ のレベルを $1$ 上げる→スキル $10$ のレベルを $1$ 上げる→スキル $1$ のレベルを $1$ 上げる」ということを意味する。 $p$ の初期値をてきとーに設定し，そこから $2$ つの要素をswapした配列に対し $1000$ ターン分のスコアを計算し，良くなれば採用，ということを制限時間いっぱいまで繰り返す。
　山登り法では，できるだけシミュレーション回数を増やしたいため，サボれるところはサボることを考える。レベル上げ終了後は，レベルをどういう順番で上げたかということに依存せずに行動を決定できる。今回は，レベル上げ終了後は「ターンの遅い順に討伐する依頼を決定する」という方針を引継ぐことにする。山登りを始める前に， $t$ ターンからレベル上げ後の行動に移るときの報酬の総和と行動を事前に求めておけば，だいたい $350\sim 400$ ターン分くらいはサボれることになる。
　ここまでやったのが以下。 $3.3$ 億点で，やはり「レベル上げの間でも取るべき報酬は取る」ということが必要そうだ(とはいっても，レベル上げの順番を考えないよりははるかに高いスコアだ)。
Submission #3707961 - HACK TO THE FUTURE 2019 本選オープン

　では，レベル上げの間に取るべき報酬をどう決めるかということを考える。なぜわざわざレベル上げの途中に報酬を貰いに行くかというと，その報酬がレベル上げ後に取る報酬といい勝負だからであろう。よって，レベル上げ後に取る報酬を用いてこの基準を定める。具体的にどう決めるかはいろいろあるが，
$0.55\times$ 「(今からストレートでレベル上げが終わるターン $+10$ ターン)後に得る報酬」
以上の報酬であれば，取りに行くことにした。 $0.55$ や「 $10$ ターン」という謎の数字はエスパーで決めた。
　これを提出すると，運が少し良いと $4$ 億に乗る(だめでも $3.8$ 億はある)。安定してより高いスコアを出すにはさらなる工夫が必要そう...。
Submission #3708880 - HACK TO THE FUTURE 2019 本選オープン