絶滅

どうでもいい

TopCoder Marathon Match 99

今回もやるぜマラソンマッチ

コンテストページはここ




問題概要

  • スロットをぶん回す










プレイヤーに開示される初期パラメータとして

  • coins (100 ~ 10000) : 最初の所持金
  • maxTime (100 ~ 10000) : 使える時間
  • noteTime (2 ~ 10) : メモを取るのに掛かる時間(後述)
  • numMachines (3 ~ 10) : スロットマシーンの台数

が乱数で与えられる.


隠れたパラメータとして

  • wheelSize[i] (10 ~ 30) : i 番目のマシーンのホイールサイズ(ホイールに書かれた文字の数)

があり,各ホイール上の文字は

  • wheelDistribution = "AABBBBCCCCCDDDDDDEEEEEEFFFFFFFGGGGGGGG"

に従って生成される (A はレアで G はいっぱいある).


ペイライン(スロットの真ん中の一列)に同じ文字が 3 個揃うと以下の報酬を得ることができる.

A A A : 1,000
B B B : 200
C C C : 100
D D D : 50
E E E : 20
F F F : 10
G G G : 5


スロットをプレイする方法は quickPlay と notePlay の二種類存在する.

  • quickPlay(i, n) : n の時間を消費して i 番目のスロットを n 回プレイする.
    当たった合計金額の情報のみ得られる.
  • notePlay(i, n) : n * noteTime の時間を消費して i 番目のスロットを n 回プレイする.
    当たった合計金額と,各プレイ結果におけるペイラインとその上下合わせて 3 列の情報が得られる.


最終的な所持コインをなるべく多くしたい.




やったこと


2018/03/15

今回はサンプルコードもビジュアライザも付いてない(らしい)のでまず入出力から分からない.

Example Test に以下のようなコードを投げたらとりあえず正の点数が出た.

class BrokenSlotMachines {
public:
    
    int playSlots(int coins, int maxTime, int noteTime, int numMachines) {
        PlaySlots::quickPlay(0, min(coins, maxTime));
    }

};


Available Libraries をローカルで実装しようとすると

静的でないメンバー参照は特定のオブジェクトを基準とする相対参照である必要があります

という怒られが発生した.ググると静的メンバにすれば OK らしいので,関数冒頭に static を付けたら黙った.(幼稚園児なのでそのあたりの知識がない)

class PlaySlots {
public:
    static int quickPlay(int machineNumber, int times) {
        /* hoge */
    }
    static int notePlay(int machineNumber, int times) {
        /* hoge */
    }
};

class BrokenSlotMachines {
public:
    
    int playSlots(int coins, int maxTime, int noteTime, int numMachines) {
        PlaySlots::quickPlay(0, min(coins, maxTime));
    }

};

土台はこんな感じだろう.
とりあえず第一投をぶん投げて退路を絶っておく.

f:id:my316g:20180315222758p:plain

意外とビリじゃなかった.




2018/03/16


深夜 ~ 朝

とりあえず環境を整えることに.


f:id:my316g:20180316072731p:plain

分割コンパイルに悪戦苦闘しながらもりもりローカルテスト用コードを書いていく.
作法など知らないので顰蹙を買うムーブを大量にしているかもしれない.


f:id:my316g:20180316072932p:plain

バージョン管理をそろそろしっかりしようということでここなどを参考に Visual Studio Team Services で開発環境を整えた.
エンジニア感が 2 くらい増えた気がする.


ローカルテスターも動くようになったところで,当面の得点基準となるコードを書く.

  • コイン切れ or 時間切れになるまで quickPlay(randomMachine, 1) を繰り返す


日も昇ってきたのでとりあえず第二投はこれを出しておく.

f:id:my316g:20180316074547p:plain

まあビリ周辺だよね



起きたら TopCoder が便秘を患っていた (Queue が詰まるの意)
土台はある程度出来上がったのでちゃちゃっと点数の上がりそうなコードを書いた

  • trial = min(coins, maxTime) / n (n ≧ numMachine) として各マシーンで trial 回 quickPlay
  • 最もコインを貰えたマシーンでコインか時間が尽きるまで粘着する

n = 20 が最もよさそうなのでそれで Submit

f:id:my316g:20180316233858j:plain:w300

まあまあやるじゃん



2018/03/17

プロファイラがくそ便利

f:id:my316g:20180317101818p:plain

ループをぶん回す下準備として Visual Studio のプロファイラ機能を使うとどこで時間を掛けているか一目瞭然となる.見た所期待値計算部分で 6 割以上使っている.

f:id:my316g:20180317102146p:plain

該当するコードはこれ.愚直に 3 重ループを回して文字が揃うか確認してるのでそりゃ遅いわ.O(wheelSize3) くらいある.ぐっと睨んで

f:id:my316g:20180317102404p:plain

組合せを考えることで O(wheelSize) まで落とした.

100000 テストケースで 30sec 掛かっていたのが約 1/3 の 10sec で終わるようになった.

f:id:my316g:20180317103318p:plain

あと時間掛かってるのはほぼ乱数生成部分 (xor128) なので,これの高速化を考えるのは最終手段でいいだろう.

いやープロファイラ便利.


夕方とか

本当は coins, maxTime, noteTime, numMachines の値を変えまくってデータ分析したりしたいけどそっち系まったく分からんので後回し

わざわざ notePlay なんてものがあるので使わなきゃ損なんだろう,ということで notePlay を使ったやつを実装した.

  • notePlay を残り時間が maxTime の 8 割になるまでランダムで実行する
  • スロットの盤面をすべて記録し,各マシンに対する期待値を推定する
  • 推定期待値最大のマシンに quickPlay で粘着する (推定期待値 1.2 以上のものがなければ終了)

f:id:my316g:20180318041106j:plain

800000 近くまで行った.いい感じじゃん


ARC で非業の死を遂げる

とりあえず直前の Submit ではパラメータ調整が甘かったので詰められるだけ詰めた

  • notePlay を残り時間が maxTime * 0.855 になるまでランダムで実行する
  • スロットの盤面をすべて記録し,各マシンに対する期待値を推定する
  • 推定期待値最大のマシンに quickPlay で粘着する (推定期待値 1.0 以上のものがなければ終了)

これがローカル 100000 TestCase の平均で最も良いスコアを出したので Submit

f:id:my316g:20180318041431j:plain

一桁順位が見えてきたか?でも 820k とか出している人間はもっとすごいことをやっているに違いない




2018/03/18


データを眺めていると最初の notePlay をランダム実行するフェーズにおいて一度も play されない台があることに気付く.

ランダム実行ではなく

int trial = min(0.6 * initialCoins / numMachines, maxTime * 0.166 / noteTime / numMachines);

で算出される trial 回各マシーンをプレイして統計情報を収集する.その中から

expectation ≧ 1.023

であるものの中で最大のマシーンに粘着する.

仮の理論値を計算できるようにしたので,それとの比較でもっとも良いスコアを叩き出したパラメータを使ってみた.

f:id:my316g:20180318075233p:plain

9 位
魔境のみなさんおはようございます よしなに




結局どれだけ早く当たり台を見つけて粘着できるかが勝負な気がしてきた
期待値最大のマシーンを選択できていない場合が多々あったので,とりあえず二段階選抜してみる

  • まず各マシーン trial1 回ずつプレイして暫定の期待値を出す
  • その中で期待値が閾値を超えるマシーンを全部選ぶ
  • よさそうなマシーンを各 trial2 回プレイしてさらに情報を集める
  • 最もいい期待値を出したマシーンに最後まで粘着

ローカルで理論値と比較すると 1 万点以上伸びそうな気がするしこれで上位に入ったかな?と期待を込めて Submit

点数が 1 万点以上下がる

なんでや




2018/03/19 ~ 没落まで

結局期待値を多段計算しても点数は下がる一方

貧弱すぎる Queue やぶっ壊れる Judge など各種イベントが発生したようだが,何も思いつかない状態だったのでそんなに被害はなかった

終了 2 日前とかになると各位がバンバン 840k とかを出しているのを横目に無為なパラメータ調整に明け暮れる

f:id:my316g:20180323011459p:plain

何か重要なことに気付いてない感をひしひしと感じながら,無為をやって数千点伸びたコードを適当に投げて今回はおわり.結局 30 位周辺まで落ち込んでしまった.

最初好調だっただけに少し悲しい気分に包まれているものの,Git とか使い始めて環境構築 2 くらいやったので成長はあったのかな.