ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

HACK TO THE FUTURE 2019 本選オープン 参加記録

HACK TO THE FUTURE 2019 本選オープン - AtCoder

オープンコンテスト3位!

f:id:betrue12:20181202000519p:plain

解説というほどのものは書けないので、「こんな感じのことをしました」というのをつらつら書いていく感じになります。

最初に考えたこと

  • 中盤まではスキルに投資することが重要だが、終盤は無駄なのでひたすら仕事をしたい。
  • スキルは高レベルほど上げにくくなるので、特化するより均等に上げたほうが費用対効果は高そう。
  • 依頼は期間終了ターンもしくはその少し前で受けることを考えたい。依頼がいっぱいあるので、極論「そのターンに終了する依頼」だけを見てもよさそう。
  • 面倒なことは考えたくないので、依頼の要求スキルレベルや期間の傾向を解析したりするのはとりあえずやらない。

ということで、こんな感じのものを書きました。

  • 事前準備
    • 依頼を終了ターンで分類しておく。
    • 目標スキルレベルを決める。
  • ~900ターン目
    • 一番低いスキルレベルで一番若い番号のものをスキルアップ候補とする。そのスキルのレベルが目標レベル未満で、かつトレーニングをするお金があるならトレーニングをする。
    • レーニングをしない場合、そのターン~10ターン後までに終わる依頼の報酬を全部計算し、一番高いものを受ける。(これはバグって機能していなかった)
  • 901ターン目~
    • そのターン~10ターン後までに終わる依頼の報酬を全部計算し、一番高いものを受ける。(これはバグって以下略)

この提出がこれ(2.96億点)。10ターン後と10ターン前を間違えて、結局そのターンに終わる依頼しか受けられないようになってました。ひどいですね。

これを書いて試してみたところ、

  • 目標スキルレベルは高ければ高いだけ結果がよくなる
  • スキルレベルが全て10になるのがだいたい600ターンくらいで、かなり余裕がある

ことが分かりました。そのため以降はスキルレベルを10まで上げきることを前提に考えました。

スキル上げフェーズとひたすら稼ぎフェーズ

ということで、フェーズを2つに分けてみます。

  • スキルレベルがオール10になるまで
    • なるべく早くスキルレベルをオール10にすることを考える。
    • スキルを上げられる場合、必ず上げる。対象スキルの選択は前と同様。
    • スキルを上げられない場合、そのターン~  k ターン後に終了する依頼から最も良いものを受ける。
  • スキルレベルがオール10になった後
    • もうお金を稼ぐだけなので、後ろから順番に受ける依頼を決めていく。

 k は適当に試して決めます。 k が大きいと候補が広がる反面、美味しい依頼を早く取ってしまい損をする可能性があります。このときは  k=20 くらいになりましたが、後々の改善をした後だと  k =0 が一番良くなりました。

スキルレベルがMAXになった後は、後ろから「最も報酬の高い依頼」を選んでいきます。本番中はこれが厳密に最適だと信じて疑いませんでしたが違いますね…ただ、美味しい依頼を最終日に選択できる可能性はとても高くなり、なかなか良い結果になったとは思います。

このアルゴリズムを書いてそこそこパラメータ調整したのがこれ。3.19億点まで伸びました。

所用のためここで少し離脱。

美味しい依頼はスキルよりも優先

用事を終わらせてPCの前に戻れたので、頭の中で考えていたことを試していきました。

まずスキル上げフェーズにおいて、トレーニングできるお金があるときはトレーニングをしていましたが、美味しい依頼があるときはそっちを受けてもよいのでは?という案。

「美味しい依頼」の基準は、最終的には「いままでの依頼の最大報酬×  k 以上の依頼であれば優先」という感じになりました。 k は1.3くらい。

実装はこれ、結構伸びがよくて3.40億点。この提出ではいままでの最大報酬ではなく1つ前の依頼の報酬を使っています。

スキル上げ順番の操作

次に、今まで避けていた依頼の傾向解析。あまり複雑なことはしたくなかったので楽そうなものを選びました。それはスキル上げ順番の操作です。

スキルを上げる時、均等に上げていくのは変えません。ですが例えばスキルレベルが 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 という状態から、どのスキルを真っ先に上げるべきでしょうか?

すごく感覚的に言うと、「スキルレベルがだいたい2~3くらいになっているであろうターン」において、「要求最大スキルレベルが3である、高報酬の依頼」があるとき、そのレベル3が要求されているスキルを優先的に上げるのがよさそうです。

これを実装に落とすと、

  • 各スキルレベルごとに、「だいたいスキルレベルが  (k-1) k であるようなターンの範囲」を、サンプル1の実行経過などを見て決める。
  • 依頼ごとに、もし「要求最大スキルレベル」と「依頼終了ターンが上記範囲内にあるようなスキルレベル」が一致していれば、そのレベルにおいてそのスキルを早く上げることは重要とみなし、その依頼の基本報酬額を評価に加算する。
  • レーニングの時には、各スキルレベルごとに評価が高いスキルから優先的にトレーニングをしていく。

という風になります。これ もかなり伸びがよくて3.56億まで上がりました。これが実質的には最後の有意な改善でした。

その後、上記「ターンの範囲」をテストケースごとに決めるような処理を入れてみましたが、結果は微増。残り時間がなかったので場当たり的にコードを書き直して実装がぐちゃぐちゃになりました。このスコアでコンテストを終えました。

振り返り

重い実装をするとバグるので予選の反省としてあまり凝ったことをせずシンプルに考えるのがよいということを学んだので、難しそうなものはどんどん後回しにしてシンプルな解法を心がけました。

スキルレベルを最大まで上げてよい、2フェーズ化、後半は後ろから貪欲という主要な知見を早めに確立できたのはとても良かったと思います。

そこからの改善はわりと場当たり的で、結構運良く思いつきが当たっていったなという印象です。

反省点としては、実行時間がダダ余りになって有効に使えなかったこと。予選のように試行回数で稼ぐことは頭をよぎりましたが、何をパラメータとして回せばよいかのイメージが持てなくて実装に落とせませんでした。

あと後ろから貪欲が最適とは限らないことに気づけなかったのはアルゴやってきた競プロerとして普通にダメですね。実際ここで大量の報酬を稼いでいるので、改善効果は高そうです。

さいごに

まさにゲームのAI(機械学習とかそんなんじゃなくて、いわゆるコンピュータ側の行動プログラム)を組んでいるみたいでとても面白い問題でした。シミュレーションゲームの敵側の行動なんかは、こんなことを考えながら組んでるのかなと少し思ったり。

成績としてはかなり良かったですが、「なぜ良かったのか」がいまいち分からず…運が良かったんですかね。マラソンに慣れてくるとこのあたりの感覚が鍛えられて、効果的に復習できるようになるのでしょうか。もう少し場数を踏む必要がありそうです。