HTTF2019 🏆優勝🎖 そして解説
HACK TO THE FUTURE 2019 本選beta.atcoder.jp
5じ起床、空港へ
会場に到着。インスタ映えをした。
10:30 本選開始
まず問題を読んで、大体の方針を決める。
とりあえず、すべての依頼は基本的に最終日にこなすことを考えて、状況次第でずらすことにする。
そのために、各日について、20日まで先読みして、後ろから貪欲で今日やる依頼を決めた。
スキル上げはお金が余っているならやるが、ただし稼ぐ平均の1.5倍を超えるような依頼なら依頼を優先した。
スキルのあげ方は番号ごとに微妙に差をつけた。一番上と下では3Lvぐらい差がある?
シミュレーターや、後ろから貪欲を実装して、submit。3M点。(1M=1million=100万です、今後もこのような表記を使います。)バグっていたので、デバッグ。
12:30 で、186M点だった。とりあえず考えていたことができたのでお昼ごはん。豪華な中華弁当。
食べ終わった後、ビジュアライザを見たらお金が余りまくっていることに気づく。
なので、依頼を優先する基準を、(1.2一日に稼ぐ平均+0.2所持金)にしたら、14:08で、322M点だった。
後4時間半ある。とりあえずビジュアライザを確認すると、ものすごく稼ぐ依頼があることに気づく。
そこでデバッガから、何億円の層の依頼をいくつ達成したか、を見えるようにする。
結果、ケースにとてもよるが、依頼の上位20個ぐらいで、全体の半分を稼いでいることに気づいた。
そこで高額依頼を達成するために、スキルを上げている途中の高額依頼に対して、今までは「偶然取れたらとる」だったが、それを「高額依頼が取れるように、スキル上げ順序を調整する」感じにした。
具体的に言うと、あるスキルレベルのsetに達するためには、「30+トレーニング回数*1.1」ターン必要だとして、依頼の要求がそれに間に合ううち、645ターンまで(645には全部maxだろうから) の依頼を列挙、その中で報酬が大きい方から31個の依頼に対して、狙うかどうかをbitDPした。
231だと間に合わないが、適当に枝がりすると間に合います。もっと枝刈りをすれば当然ぼっと大量の依頼を考慮できるけど、31個ぐらい見れば残りは安いのしかないので、それで十分だった。
それを実装して、16:26で、392M点だった。暫定一位!w
あとは、狙いには含まれないスキルも(maxスキル-1)/2までは上げるようにしたり、適当に決めていたパラメーターを細かく調整した。
結局18:10の 431M点が最大だった。 うれしい。
スキルレベルmaxに到達するのは大体610ターンですが、実際にはほぼmaxなら依頼を実行するのが増えるので、実質的にはそんなに遅くない。
本選終了
maroonさんやyosupoさんやsugimさんとたくさん話した。
chokudaiさんが想定解法みたいなのを言っていた。とても楽しかった。
会話にとても夢中になっていたら、表彰式が始まって、🏆一位🏆だった。やった!
そしてこの解法の解説をした。
2位のomiさんと比べて、僕のは序盤が適当(特に何も考えずに、すべてをまんべんなく上げています) な代わりに、中盤が強いので勝てた。良かった。
中盤にしっかり「狙う動き」をしたのはたぶん僕一人だった。
気が付いたらディナーがほぼなかった。
参加賞として、おしゃれなフライドポテト? をもらって帰った。 お土産達成!!!🐣
北九州空港に着いたら、24:25だった。よる遅すぎる...
マラソンマッチは楽しいのでぜひみんな来年も出ましょう! 問題もおもしろくて、食べ物も賞品も豪華で最高のコンテストでした。 本当にありがとうございました！
