HACK TO THE FUTURE 2019予選
Updated:
Source codes
Solutions
A - ばらばらロボット
問題文には「できるだけ高い点数を得るボードを構築してください。」とあるが、これを完全に無視して 正の最低点を狙う ことにした(関係者の皆様がご不快に思われたら申し訳ありません)。そして 3 点を獲得した。しかし最低点は 1 点だったようで、私は負けた。
メソッド
中央から十字形に . を配置し、それ以外は壁にする。だんだんマス目を増やしていき、最終的に $n = 9$ マスを十字に . とした場合に 3 点を獲得することができた。以下がその出力である。
#############################
#############################
#############################
#############################
#############################
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
#####...................#####
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
##############.##############
#############################
#############################
#############################
#############################
#############################
正の点が獲得できる大雑把な理由
$n \leq 8$ では 0 点で、 $n = 9$ では 3 点であった。この結果について大雑把な考察を与える。
まず $n$ マスの . を配置した場合、盤面には $4n + 1$ マスの空白が生じる。今回はロボットへの操作を与える文字列が与えられており、それらは全て問題文に明記されている乱数で生成されている。であるから本来はそれらを用いて各マスにたどり着く正確な確率がもとまるのであるが、その計算は面倒なのでしない。大雑把に考察するために、 盤面の $4n + 1$ マスにロボットは一様に分布する ものとする。マスの個数 $4n + 1$ が十分小さく( $n = 9$ で $37$ 個)で、文字列が十分長い( $L = 300$ )ので、この近似は酷くはないだろう。
この状態で正の得点を取る計算をするわけであるが、ここでも近似を用いる。あるマスに $3$ 個以下のロボットが止まる(「停止カウント」が $3$ 以下である)ことが正の得点をとるための条件である。
$p _n = $ あるマスに $3$ 個以下のロボットが止まる(「停止カウント」が $3$ 以下である)確率
とし、正の得点を取る確率を $q _n = (4n + 1) p _n$ と近似する。これは何の近似になっているかというと、停止カウントが $3$ 以下になるマスが $2$ つ以上ある確率を $0$ と近似している。後述する通り、 $p _n$ は非常に小さい。停止カウントが $3$ 以下になるマスが $k$ 個ある確率は $p _n ^k$ に $(4n + 1)^k$ 程度の係数をかけた値となる。 $k \geq 2$ は全て無視しても十分近似されるだろう。そして実際の採点結果が $3$ 点であるから、停止カウントが $3$ 以下になるマスが $2$ 個以上あるケースはなかったと思われる。
さて $p _n$ を求めることに帰着されるのであるが、これは二項分布を用いれば容易に計算結果が得られる。
- $n = 8$ の場合： $p _n = 0.00016023202704 \dots$ 、 $q _n = (4n + 1) p _n = 0.00528765689 \dots$ 。よって $30$ 個のテストケースで正の得点を獲得できる確率は $1 - (1 - q _n)^{30} = 0.1470467851 \dots$ 。約 $14.7 \%$ であると言える。
- $n = 9$ の場合： $p _n = 0.00062327916451 \dots$ 、 $q _n = (4n + 1) p _n = 0.02306132908 \dots$ 。よって $30$ 個のテストケースで正の得点を獲得できる確率は $1 - (1 - q _n)^{30} = 0.50338591972 \dots$ 。約 $50.3 \%$ であると言える。
今回はこの $14.7 \%$ には引っかからず $50.3 \%$ の方に引っかかったので、 $n = 9$ で正の点数を獲得することができたと結論づけられる。
敗因
確率が跳ね上がる $n \approx 8, 9$ 付近でもう少し丁寧に(非対称に)マスを絞れば 1 点は狙えたかもしれないけど、 5 分に 1 回しか提出できないし、休日の時間を研究のために有意義に使うためには、ここにこれ以上こだわっても仕方ないので、まぁこれでいいかなと。負けてしまったのは残念ですが。
余談
後半の計算は、ソシャゲでガチャを引く前にいつも経験していることである。ガチャを引くゲームをやる方はこのような計算に感覚的に慣れておくと計画的に課金できるかもしれない(爆死しても私は責任は取れません)。
1 点を取った方の解法
1 点取る方法は全く発想が違っていた。サンプル 1 が見えていることを利用していた。サンプル 1 で 1 点を取り、残りを 0 点にしようという発想であった。私は確率論的に発想したんだが、全部が見えていないなら有効かもしれない。
Others
解説放送をだらだら見ていた。予選のレベルが上がっているように感じた。
まず ., L, R のみで構成するのが適切であり、 . が 8 - 9 割程度あると良いとのことであった。これに加えて山登り法が 12 万点くらいで、予選通過にはそれ以上のレベルが必要だったそうだ。
シミュレートする回数を減らした後の高速化のテクニックも使うとさらにうまくいくそうである。どれだけシミュレーションをするかを愚直に書くと 1000 回くらいで、そうでなければ 30000 回くらいまで伸びるとのことだった。すると焼きなまし法が使える。
また、最終的にどのマスでどのくらいの点数の上乗せが期待できるかを予め計算すると良いそうである。ルートを変更するロボットが 40 個を超えるようなマスは変更しないという枝狩りも有効である。