AT_maximum_2013_e Alicia's Rare card Challenge

[problemUrl]: https://atcoder.jp/contests/maximum-cup-2013/tasks/maximum_2013_e ♪「ガラガラガラ～、レアカード来い！」 俺は今、巷で人気のソーシャルカードゲームにはまっている。 このゲームは「カードローダー」という名のガチャシステムで カードを増やし、カード合成でデッキ(手札)を強化して コンピュータや他のプレーヤーと対戦するといったゲームである。 巷によくあるゲーム形式で、課金しないとなかなか楽しめないと いうところも定番通りである。 たった今カードローダーで 引いたカード「のろのろウサギ\*(N)」(名前の後ろの括弧は希少価値を表す) は戦闘力最弱の屑カードである。 いつになったら 目的のレアカードが出現してくれるのだろうか。 俺は貧乏ゲーマーなので課金はしたくない。 しかし、 ゲームヒロイン「アリシア」のレアカードが欲しくてたまらない。 そこで俺は友達に協力を依頼してカードローダーについて調査を行った。 残念なことに、カードローダーで得られるカードは10枚目ごとにかつそのときに限り必ず「のろのろウサギ\*(N)」であることしか分からなかった。 そうこうしている内にゲーム主催者の方から特別なイベントの告知が行われた。 イベントは数種類あるカードローダーで入手可能なカードの種類と 入手確率が公開されるというもので、 「プレーヤーの皆様の日頃のご愛顧に感謝し、レアカードを椀飯振舞することに いたしました。奮ってご参加ください。」とのことだ。 イベント詳細を詳しく見ると、今までとカードローダーの仕組みは変わらず、 入手できるカードの入れ替えと入手確率を変更し、 いつもよりレアカードが入手しやすくなっているらしい。 いてもたってもいられず、いざカードローダーと思ったとき、ふと思った。 「いくらいつもより確率が良くても、いったい何回カードローダーを動かせば アリシアちゃんのカードが入手できるのだろう」と。 俺は金がない代わりにゲームする時間はある、けれどこの手のゲームの定番で 課金しない状況では続けて何回も動かすことはできない。 何回動かせば入手できるか知ることが出来れば、実際いつ頃入手できるか 推測がたつ。 もし、来週の今頃であるなら、今週はとてもウキウキした 一週間になるに違いない。 もし、1ヶ月先であるならば、 カードを入手する前にイベントが終了しているかもしれない。 「あ～、神よ。俺にレアカードをお恵くださいorz」 あなたの仕事はカードの入手確率とカードローダーの動作回数をもとに「俺」が入手できるアリシアのレアカードの枚数の期待値を求めることである。 ここでいうレアカードとは、N(ノーマル), R(レア), S(スーパーレア), H(ハイパーレア)の 4種類の希少価値がある中で、R,S,Hの3種類いずれかの希少価値をもつカードを指す。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ card\_name_1 $ $ rarity_1 $ $ rate_1 $ : $ card\_name_N $ $ rarity_N $ $ rate_N $ 1. 1行目には整数 $ N $, $ T $ が与えられます。 - $ N $ は出現率について得られた情報の数を表します。 - $ 1\ ≦\ N\ ≦\ 10,000 $ であることは保証されています。 - $ T $は試行回数を表します。 - $ 0\ ≦\ T\ ≦\ 100,000,000 $ であることは保証されています。 2. 2 行目から $ N\ +\ 1 $ 行目までの $ N $ 行では、カード名称、希少価値および出現頻度がそれぞれ半角スペース区切りで与えられます。 - $ card\_name_i $ は $ i $ 枚目のカード名称を表します。 - $ card\_name_i $ は半角英数字の他に `[`, `]`, `&`, `!`, `?`, `+`, `-`, `_`, `/` によって構成されます。 - $ card\_name_i $ は 1 文字以上 20 文字以下であることが保証されています。 - アリシアのカードである場合、$ card\_name_i $ に “Alicia” の文字列を含みます。例えば「アリシア\[ひとやすみ\]」は「Alicia\[hitoyasumi\]」となります。 - $ rarity_i $ は $ i $ 枚目のカードの希少価値を表します。 - $ rarity_i $ は `N`, `R`, `S`, `H` のいずれかであることが保証されています。 - $ rate_i $ は出現頻度を表します。 - $ 1\ ≦\ rate_i\ ≦\ 100,000 $ であることは保証されています。 - カードローダーは指定された確率を用いるとき、 $ rate_i\ /\ (rate_1\ +\ …\ +\ rate_N) $ の確率で $ i $ 番目のカードを生成します。 アリシアのレアカードの入手枚数の期待値を 1 行に出力せよ。 出力は $ 10^{-6} $ 未満の誤差を含んでも良い。 ``` 3 3 Alicia[Normal] N 40 Superheroine_Alicia R 9 Secret_of_Alicia H 1 ``` ``` 0.6 ```

N/A

N/A