TCO Announcement Fun Round - WaterfallFishingの反省

2017年5月の、ちょっと古いマラソンマッチですが、忘れないようにするために、書きました。

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16930&pm=14615

川の幅 W （2≦W≦200）
川の長さ L （5≦L≦100）
川には、岩がある。（5≦岩の数≦W*L/10）。ただし、岩の場所は、分からない。

まず、D日間連続で、魚が上流から下ってくる（4≦D≦20）。

5≦魚の数≦100
魚は、魚群の中心の位置M・標準偏差Sの正規分布で、まず上流に配置される。（0≦M≦W-1, 2≦S≦W/4）。M,Sも分からない。
魚はまっすぐ下るが、岩にぶつかると50%の確率で左に1マス、50%の確率で右に1マスずれて落ちる。
魚が、下流に下ってきた魚の数は、場所ごとに分かる。

f:id:shindannin:20180103184334p:plain

（範囲になっている変数は、テストケースごとに、ランダムに均一に選ばれる）

D日間分の下流に下ってきた魚の数の情報を用いて、D+1日目に落ちてくる魚の場所を予測し、罠をしかけて、できるだけ多く捕れ。スコアは、（捕まえた魚の数）/（罠を仕掛けた数）で決まる。与えられた計算時間は60秒間。

方針

機械学習で予測した。ただ、この問題、データが足りなすぎる、かつ、あまり当てにならない。魚群の位置M,Sは毎日変わるので、ここの予想が外れると、ほぼ魚を捕れない。そういうわけで、機械学習は避けて、確率の知識などで解答した人が多かったっぽい。
ただ、自分は機械学習でごり押しした。データ不足を補うために、自前でデータを生成した。やり方は以下の通り。

(1) 「岩配置」と「下流に下ってきた魚の数のデータ」のペアを、問題と同じ方法で200種類生成。
(2) 「岩配置」から、下流に下ってきた魚の数の期待値を場所ごとに求める。上流の魚の確率分布は、1000万回シミュレーションして求めた（数学強い方なら解析的に求められる）。上流での魚の確率分布と岩の配置を用いれば、簡単な期待値DPで、下流に下ってきた魚の数の期待値を求められる。これを機械学習の目的変数（予測したい値）として使用。
(3) 「下流に下ってきた魚の数のデータ」は、機械学習の説明変数（特徴量）の生成のために使用。最終的には以下を説明変数として用いた。