TCO18 MM R3 InvestmentAdvice 参加記録
問題文：
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17203&compid=65421
順位表：
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17203
最終日のみの参加になってしまった
問題内容
概要
Ｎ個のファンドがあり、それぞれ異なるexpertにより運用されている。毎round、各expertは次roundまでにリターン可能であると予測される利益の投資額に対する比を提示する。どれにいくら投資するかを決めて、利益を最大化せよ。
制約、条件
1roundで1つのexpertに投資できる額の上限は400000である。また、投資額の合計が所持金額を超えてはならない。これらの条件を満たせば、投資額は毎roundごと自由に決められる。投資したお金は必ず次のroundには清算される。利益は、各ファンドごとに投資額×真の利益比（小数点以下切り下げ）によって計算される。この値は次のroundにおいて知ることができる。
・最初から持ってるお金=1000000
・ファンド数 N=nextInt(10,50)
・全round数 R=nextInt(10,100)
・各ファンドの真の利益の比=平均0、標準偏差0.1の正規分布に従う。
・expertの提示する値：
ここでA,Sはexpertごとに持つパラメータで、
A=nextDouble()
S=nextDouble()*0.2
として決定される。これはroundごとに変化しない。
やったこと
平均a、標準偏差s、の正規分布の確率密度関数をf(x,a,s)と書くことにします。
基本方針
まず、毎roundの利益の期待値を最大化するには、各ファンドごとに利益率の期待値を求め、大きいところから順に、期待値が正である間、また所持金が残っている間、上限額（400000）ずつ投資していけばよいです。
もし全く投資しない場合、そのファンドの真の利益率についての情報が得られません。よって、情報を得るために期待値が低いところに投資することも考える必要があります。情報を得たいファンドについては一定の額を投資することとし、それ以外についてはそのroundの利益の期待値を最大化することを考えることにします。
期待値の計算
ベイズの定理とかで確率計算します。以降一つのファンドに注目して考えることにします。
あるroundにおいて、真の利益率がactual、提示された値がreportであったとします。
expertのパラメータの確率分布は、
p(A,S | actual,report) ∝ p(A,S)×p(report | actual,A,S)×p(actual | A,S)
です。p(report | actual,A,S)は、問題の制約において、真の値から提示する値を決定する部分がそのまま使えます。
p(actual | A,S)はそもそもA,Sに依らないので無くて良いです。したがって、
p(A,S | actual,report) ∝ p(A,S)×{A×f(report,actual,S)+(1-A)×f(report,0,0.1)}
投資したファンドについては前roundのactualの情報が分かるので、これを用いて確率計算します。投資しなかったファンドについては、
p(A,S | report) ∝ p(A,S)×p(report | A,S)
=p(A,S)×{A×f(report,0,sqrt(0.01 + S*S))+(1-A)×f(report,0,0.1)}と計算できると思いましたが、やるとスコアが悪くなるのでやってません。なんで
続いて、利益の期待値を計算します。さっきまでのactual,reportは直前roundの情報でしたが、これからは現roundのactual,reportです。actualに関しては予測値ですので、区別するためにXと書きます。
p(X | report) ∝ p(report | X)×p(X)
=∬p(report | X,A,S)×p(X,A,S) dAdS
=p(X)×∬p(report | X,A,S) dAdS
=f(X,0,0.1)×∬{A×f(report,X,S)+(1-A)×f(report,0,0.1)}dAdS
後は期待値ですが、
∫X×p(X | report)dXを計算すればよいです。
これらの計算は解析的にはできそうにありません。A,S,予測actualに関して標本化して計算しました。
情報を得るための投資
投資した回数が一定回数以下のexpertには、必ず40だけ投資するようにしました。この値は大きすぎるとそのroundに得られる利益の期待値が低くなる損が大きくなり、小さすぎると得られる情報の正確さが落ちます。
「一定回数」の決め方ですが、全ファンド数と全round数のみに依るものとして考えました。あらかじめいくつかの｛全ファンド数、全round数｝に対して「一定回数」として最善の値を求めておき、間の値は補完することでテストケースごとの「一定回数」を求めました。
この辺は改善の余地が大いにあると思うのですが、時間がなくてやってません。
