ABC_382_E"E - Expansion Packs"をRubyで解く
水に戻れない……(資格の勉強ばっかやってて全然精進できてないから当たり前)。
今回の問題はこちら。
自力正解できなかったので、今回はhmmnrstさんの解法を参考にしました。
考え方
まず1パックあたりにレアカードが何枚入っている確率はそれぞれいくら?
求めるのはパック数の期待値であり枚数の期待値ではありません。一枚ごとのレアカードの確率を知っていてもしょうがないので、これを1パックあたりのレアカード枚数の確率に置き換えます。
これは愚直DP(緑コーダーからすると凄いワードだ...)してください。例えばパックのレア確率が20 30の場合、
- 初期状態はレアカードの枚数0の確率が1なので
[1] - 一枚目のレア確率が0.2なので、一枚目をめくった時点でレア0枚の確率が0.8、レア1枚の確率が0.2なので
[0.8, 0.2] - 二枚目のレア確率が0.3なので、一枚目の時点でレア0枚、二枚目をめくってもレア0枚の確率は0.56、一枚目の時点でレア0枚、二枚目をめくったらレア1枚の確率は0.24、一枚目の時点でレア1枚、二枚目をめくってもレア1枚の確率は0.14、一枚目の時点でレア1枚、二枚目をめくったらレア2枚の確率は0.06。合計して
[0.56, 0.38, 0.06]
となります。類題はこちら。
これにより、パックの一枚ごとの確率を考えるのではなく、「1パック開けるごとに偏りのあるルーレットを一回回して、出た目の枚数だけレアカードが出る」みたいな感じに見なす事ができます。
では、何パック開けた時に残り何枚の確率がそれぞれいくらか?
ルーレットの目の確率がわかったので、あとは何回ルーレットを回せばいいかです。
一見「ルーレットに0の目があるんだから無限回回しても計算が終わらないのではないか」と思いますが、実は式変形して移項する事で0の目が出る確率を潰す事ができます。これとか以前に記事にしました。
今見返してみると野生の勘とエスパーだけで解いてますね……。アナダパンチさんの解説が論理的なのでこちらを参照してください。
一回回して1回のdp遷移ではなく、0の確率の分を割り増した回数だけ回したらdp遷移します。
これで0の確率を潰すと、1回の遷移で絶対に1枚以上レアが出ると見なす事ができ、X回遷移すれば絶対X枚レアカードが出て遷移が終わります。
これは年一回くらい出る奴なので、こちらの類題で復習しておくと後悔しないと思います。
この２要素を融合する
つまりこの問題はEDPC_IとABC_350_Eの複合問題だったわけです。
コードはこちら。
ここまでルーレットで説明してきましたが、rouletteとスペルする時間がもったいなかったのでdiceでコーディングしています。
またコンテスト中は「i回目の遷移でレアカードがj枚出た状態から配るDP」で解こうとしましたが、これは「iをX-1から0までステップダウンし、レアカードの不足分が残りi枚になるための貰うDP」を使って解いています。
高速化
見ての通り、Rubyではこの解き方だとTLEします。Rubyは配列が遅いからです。
そこで使うのがNumo::NArrayです。
本来は行列式の計算のためのクラスらしいですが、数値の型と配列の長さが固定される代わりに高速な配列としても利用できます。
今回はrecast_dice_dpとrare_card_shortage_dpをFloat64としてNArrayにします。これにより全要素にNOT_ZERO_EXPECTEDを掛けたり、#mulsumを使ってa_1 * b_1 + a_2 * b_2 + ...を高速に計算できます。
ACコード
疲労困憊したので擬似コードは書きません。コメントを読んで下さい。
Discussion