![C問題 解説 部分点E
? 具体例
– 全てのカードが揃っている場合
? 期待値は0
– カードが4枚あり、カードAだけ存在しない場合
? 期待値は、「カードAを引くまでに必要な回数の期待
値」＊「カードの枚数」
– カードが4枚あり、カードA,Bが存在しない場合
? カードAが引ける確率をa,カードbを引ける確率をbとす
る。
? 期待値は、(金額/(a-b)) + [カードAだけ存在しない場合
の期待値]*b/(a+b)+[カードBだけ存在しない場合の期待
値]*a/(a+b)
? このような感じでbitDPをしてあげれば良い。](https://image.slidesharecdn.com/arc016-131104073019-phpapp01/85/AtCoder-Regular-Contest-016-15-320.jpg)
AtCoder Regular Contest 016 解説
- 1. AtCoder Regular Contest 016 解説 AtCoder株式会社 代表取締役 高橋直大
- 2. A問題 問題概要 ? クイズゲームの選択肢の種類と、正解番 号が与えられる ? 不正解のものを１つ消したいので、１つ 選んで出力しなさい。
- 3. A問題 解説 ? 与えられた整数を2つ、標準入力から読み 取る – わからない場合は標準入力について勉強！ ? その整数2つから、不正解の番号を１つ ピックアップする – やり方は色々！ ? 出てきた答えを出力する – わからない場合は標準出力について勉強！
- 4. A問題 解説 ? 数字の選び方いろいろ – 1つ上の数字を選択する ? 1なら2,2なら3のような感じ ? 最大の数の時は1を出力する – 答えが1の時だけ2,それ以外は1を出力する – Forループなどで、全てのパターンを確認する – 正解でない数字になるまでランダムで選び続 ける
- 5. B問題 問題概要 ? 音楽ゲームの譜面が与えられる ? ボタンを押す回数を求めなさい
- 6. B問題 解き方 ? １行ずつ文字列を読み込む – 配列に入れておくと良い ? １行目は、oまたはxの数をカウントする。 ? ２行目以降は、 – xがあった場合、1つカウントする。 – oがあった場合、1つ上の行を確認し、oでな ければ1つカウントする ? カウントした答えを出力する
- 7. B問題 ちょっと特殊な解き方 ? 縦横を入れ替えて、文字列”oo”を”o”に置 換できなくなるまで置換した後、oとxを 数える。 – 普通に解いた方が多分楽です。
- 8. C問題 問題概要 ? くじが複数与えられる。 ? 事前に出現するカードとその確率、及び 値段が与えられている。 – 外れは存在しない。 ? 全てのカードを集めるのに必要な金額の 期待値を出力せよ。 ? カードNは10種類以下。くじMは4種類以 下
- 9. C問題 部分点 ? 部分点A N=1かつM=1 – カード１枚、くじも１つ ? 部分点B N=1 – カード１枚、くじは複数 ? 部分点C C_i = 1 – カードもくじは複数だが、1つのくじから出るカード は1種類だけ。 ? 部分点D N<=2 – カードが２種類まで ? 部分点E M=1 – くじが１種類だけ
- 10. C問題 解説 部分点A ? くじを１回引けば必ず目的のカードが引 ける。 ? くじの金額を出力すれば良いだけ。
- 11. C問題 解説 部分点B ? くじは複数与えられるが、カードは1枚し か存在しない。 ? 一番安いくじを引けば良い。
- 12. C問題 解説 部分点C ? 1つのくじから1種類のカードしか出現し ない。 ? それぞれのカードについて、一番安いく じを引けば良い。
- 13. C問題 解説 部分点D ? 2種類のカードが与えられる。 ? カードAを引くために必要な金額の期待値 と、カードBを引くために必要な金額の期待 値をあらかじめ求めておく。 – c円のくじで、カードAが確率pで現れる時、引く 回数の期待値は1/p個。 ? よって、C/p円が期待値となる。 ? これの最小値を求めれば良い。 ? それぞれのくじについて、カードAを引いた 場合と、カードBを引いた場合のそれぞれに ついて、期待値を求めてあげれば良い。
- 14. C問題 解説 部分点E ? いわゆる「コンプガチャ問題」 ? 部分点Dと同じように、「この先からいく らかかるか」をメモしてあげれば良い。 ? 持っているカードの状態ごとに、それぞ れbitDPで期待値を求めてあげれば良い。
- 15. C問題 解説 部分点E ? 具体例 – 全てのカードが揃っている場合 ? 期待値は0 – カードが4枚あり、カードAだけ存在しない場合 ? 期待値は、「カードAを引くまでに必要な回数の期待 値」＊「カードの枚数」 – カードが4枚あり、カードA,Bが存在しない場合 ? カードAが引ける確率をa,カードbを引ける確率をbとす る。 ? 期待値は、(金額/(a-b)) + [カードAだけ存在しない場合 の期待値]*b/(a+b)+[カードBだけ存在しない場合の期待 値]*a/(a+b) ? このような感じでbitDPをしてあげれば良い。
- 16. bitDPって？ ? 持っているカードの種類を、2進数で表す。 ? 3枚のカードがあるなら、0～7で表せる。 – A,B,Cのカードがあるなら、7 (２進数で111) – A,Bのカードがあるなら、3(２進数で011) – B,Cのカードがあるなら、6(２進数で110) ? これを利用して、状態ごとの期待値を簡 単に配列に収めることが出来る。
- 17. C問題 満点解法 ? 部分点Eに対し、各カードの状態に対して、 くじを全て試し、最小値を求めてあげれ ば良い。 – 直前のあたりはずれに関係なく、揃えている カードの状態にのみしか、引くべきくじに影 響を与えないことに注意
- 18. D問題 問題概要 ? DAGが与えられる ? 体力が設定されており、各頂点対して、減少する 体力が設定されている。 ? 頂点1からスタートし、体力1以上で頂点Nに移動 するまでの期待値を求める。 ? プレイヤーは、以下の２つの行動をとることが出 来る。 – 今まで受けたダメージ分だけ時間を消費し、頂点1に 戻る。 – 時間1を消費し、次の頂点に移動する。なお、この際 に選択される頂点は、接続されている頂点の中から 等確率でランダムに選ばれる。 ? 体力0になる可能性が少しでもあるような選択肢 は選ぶことが出来ない。
- 19. DAGって何？ ? Directed acyclic graphの略 ? 閉路のない有向グラフのこと。
- 20. D問題 問題解説 ? 今いる場所、今まで受けたダメージの2つ でDPを行う。 ? 始点に戻る、という選択肢があるため、 それだけを除くとDAGとなる。 – よって、「始点からの期待値」を固定できれ ば、DAG上のDPとなる。 – 始点からの期待値を二分探索してしまえば良 い。