東急の電車広告の問題を解いてみた

本記事は東急線の車内広告urbanhacksで出てくる広告の問題の解説を書いた記事である.
(問題添付については東急に許可をとりました)

コンプガチャ問題.

考察

まず,レア枠である5駅ぶんのキャラクターと普通の91駅のキャラクターを別々に考える.
次に今持っているキャラクターが(横浜駅,武蔵小杉駅,渋谷駅) の場合と,(渋谷駅,たまプラーザ駅,自由が丘駅)などの組を考えた際に,「レアキャラクターを3つ所持している」という情報は同一視できそう.
例えば,レアキャラクター3匹を所持しており,この状態から残りのレアキャラ2枠を手に入れるまでにガチャを回す期待値は等しい.

この考察から注目することは,
ある状態で(普通キャラクターとレアキャラクターのそれぞれについて)どれだけのキャラクターの種類数を所持しているかということが重要であることがわかる.

同一視できる部分をまとめることはDP(動的計画法)で頻繁に用いるテクニックである

状態の持ち方は
$dp[普通キャラクターのうち現在所持している種類数][レアキャラクターのうち現在所持している種類数]$
としよう.

方針

91種類の内の特定の1種類が出る確率を$\alpha$,
(i種類目が出る確率を$\alpha_{i}$ ($i=1,2,3..,91$)とすると $\alpha_{i}=\alpha$)

珍しい5種類の内の特定の1種類が出る確率をβとする.
(βi i=1,..5)
(i種類目が出る確率を$\beta_{i}$ ($i=1,2,3,4,5$)とすると $\beta_{i}=\beta$)

題意より
$\alpha=2\beta$

確率の定義より,全事象の起こる確率は当然1であるから

$\sum_{i=1}^{i=91}\alpha_{i} + \sum_{i=1}^{i=5}\beta_{i} = 1$　

この式から$91\alpha + 5\beta = 1$ となる

$\alpha$と$\beta$の連立方程式をとき
$\alpha=\frac{2}{187}$
$\beta=\frac{1}{187}$

次にDPの遷移を考えよう.
いま,普通キャラクターを$x$個.レアキャラクターを$y$個所持しており,
ガチャを1度回すことで　未所持の普通キャラクターが出てくる確率は$(91-x)\alpha$
未所持のレアキャラクターが出てくる確率は$(5-y)\beta$
すでに所持しているキャラクターが出てくる確率は$(x\alpha + y\beta)$

(x,y)の状態から遷移する際に試行回数が増えるため,(遷移先+1)される

式で表すと
$dp[x][y] = (91-x)\alpha (dp[x+1][y]+1) + (5-y)\beta (dp[x][y+1]+1) + (x\alpha + y\beta) (dp[x][y] + 1)$

途中で関係式
$91\alpha + 5\beta = 1$
を用いると

$dp[x][y] = (91-x)\alpha dp[x+1][y] + (5-y)\beta dp[x][y+1] + (x\alpha + y\beta)dp[x][y] +1$
右辺と左辺に $dp[x][y]$があるため,左辺に $dp[x][y]$をまとめる

$dp[x][y] = ((91-x)\alpha dp[x+1][y] + (5-y)\beta dp[x][y+1] + 1)/ (1- (x\alpha + y\beta))$

$dp[x][y]$を求めるには$dp[x+1][y]$,$dp[x][y+1]$がわかっていなければならない. このような遷移は再帰との相性が良い. このような問題では最終状態がわかる値で初期値となる場合が多く,そこから遷移する.

初期値はすべてのキャラクター(普通枠を91種類,レア枠を5種類)を所持している場合はガチャを回さなくてよいので回数は0 ,つまり$dp[91][5]=0$
今回のDPの値がわかる部分はすべて所持している最終状態に該当する.

求めたいものは普通枠0種類,レア枠5種類所持の状態からはじめるため,$dp[0][0]$
の値となる.

以下はC++でのソースコード

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<deque>
#include<bitset>
#include<stack>
using namespace std;
typedef long long ll;
const int INF=1<<30;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD = 998244353;


const int A=91;//普通のキャラ91匹
const int B=5;//珍しいキャラ5匹

const double alpha=2.0/187.0;
const double beta=1.0/187.0;
/*
今現在,91種類のうちのx個.5種類の内のy個を集めている状態を
dp[x][y]とする
*/
map<P,double> memo;

double dp(int x,int y){
    if(x==A && y==B) return 0.0;
    //すべてコンプしたのでこれ以上ガチャを引く必要がないので0回


    if(memo.count(P{x,y})) return memo[P{x,y}];

    double denom=1.0-(x*alpha+y*beta);//分母
    
    double ret=0;
    if(x+1<=A){
        ret+=(A-x)*alpha*dp(x+1,y);
    }   
    if(y+1<=B){
        ret+=(B-y)*beta*dp(x,y+1);
    }

    ret+=1.0;

    ret/=denom;

    return memo[P{x,y}]=ret;

}

int main(){

    double ans=dp(0,0);//最初は91種類のうちの0個,5種類の内の0個
    printf("%.10f\n",ans);
}

実行結果

553.47ぐらいになりました.