Topcoder Marathon Match 99 最終結果
作成日：2018.03.28
カテゴリー：競プロ 参戦記録
目次
最終結果
$816,134.72$点で順位はシステムテスト前から$12$下げて$46$位。
解法
全体の$1/3$の時間やコインで、slot1つ当たり何回notePlayができるかを求める。
この回数が$4$以下であったら何もしない。
そうでない時、最大$22$回ずつまでnotePlayを繰り返し、出たsymbolをそのままwheelとみなして期待値を計算する。
期待値が$1.0$以上のスロットたちに対して、exp(([期待値]$-1.0$)$\times 15.0$)に比例する確率でquickPlayを行い続ける。
ソースコード
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
typedef int_fast64_t LL;
inline unsigned int xor128(){
static unsigned int x=987654301,y=362436069,z=521288629,w=88675123;
unsigned int t = (x^(x<<11));
x=y;y=z;z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
inline double rnd(){
return xor128() / 4294967296.0;
}
constexpr int MC = 32;
constexpr int WS = 10 , WL = 30;
constexpr int MS = 7;
constexpr int G[] = {1000,200,100,50,20,10,5};
constexpr double P[] = {2.0/38.0,4.0/38.0,5.0/38.0,6.0/38.0,6.0/38.0,7.0/38.0,8.0/38.0};
#define check_char(a,b) (a==b||a=='*'?1:0)
#define check_str(a,b,c) (check_char(b[c],a[0]) && check_char(b[c+1],a[1]) && check_char(b[c+2],a[2]))
class BrokenSlotMachines{
vector<string> V[MC];
vector<pair<double,int>> ave;
public:
int playSlots(int coins, int maxTime, int noteTime, int numMachines){
int timeleft = maxTime;
int rep_t = min(22,max(1,min(timeleft/3/noteTime,coins/3)/numMachines));
if(rep_t < 5){
return 0;
}
ave.resize(numMachines);
for(int i = 0 ; i < numMachines ; ++i){
ave[i] = make_pair(0.0,i);
int symbol[3][MS] = {};
for(int t = 0 ; t < rep_t ; ++t){
auto z = PlaySlots::notePlay(i,1);
coins += atoi(z[0].c_str()) - 1;
timeleft -= noteTime;
for(int j = 0 ; j < 3 ; ++j){
V[i*3+j].push_back("");
for(int k = 0 ; k < 3 ; ++k){
*V[i*3+j].rbegin() += z[1][k*3+j];
++symbol[j][z[1][k*3+j]-'A'];
}
}
}
for(int k = 0 ; k < MS ; ++k){
ave[i].first += 1. * symbol[0][k] * symbol[1][k] * symbol[2][k] * G[k];
}
ave[i].first /= pow(3*rep_t,3);
}
sort(ave.begin(),ave.end(),greater<pair<double,int>>());
vector<double> acc_rate;
double rate_sum = 0.0;
for(int i = 0 ; i < numMachines ; ++i){
if(ave[i].first <= 1.0) break;
double tmp = exp((ave[i].first-1.0)*15.0);
acc_rate.push_back(tmp);
rate_sum += tmp;
}
if((int)acc_rate.size() == 0) return 0;
for(auto &x : acc_rate) x /= rate_sum;
while(coins > 0 && timeleft > 0){
double r = rnd();
for(int i = 0 ; i < (int)acc_rate.size() ; ++i){
if(r < acc_rate[i]){
coins += PlaySlots::quickPlay(ave[i].second,1) - 1;
break;
}
r -= acc_rate[i];
}
--timeleft;
}
return 0;
}
};
反省
コインがゼロになったテストケースが$41$個存在した。
コインの数が少なかったら何もしないというようにした方が良かったのだろうか。
ローカルでのスコアの取り方が良くなかった可能性がある。
初めのコインとの比を持っていたが、上位$10\%$は無視していた。
これによって上位の結果が反映されず、悪くなりにくいが良くもなりにくいものを採択してしまった可能性はある。
他の人が導入していたスコアの取り方である期待値が最大のslotを回し続けて得られるコインとの比の方が良かっただろう。
途中から導入して確率的な挙動をし始めてから計算しなくなってしまった、最良のslotの期待値と選んだslotの期待値の比(正確性)でも良かったであろう。
また、バンディットアルゴリズムを知らなかったことで相当不利になった。
すなわち「車輪の再発明」をしようとして時間を使い切ってしまったということである。
簡潔な問題である上、現実にもありそうな問題であったから、検索してみるべきであった。
そもそも検索してみるという発想がなかったのも敗因の一つである。
＜(古い記事) Topcoder Marathon Match 99
関連
(新しい記事)＞
＜(古い記事) Topcoder Marathon Match 99
Google Code Jam 2018 Round 1A (新しい記事)＞