はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける期待値問題

この前出たんで調べてまとめた。
結構やったので、大体わかってきたぞ
やり次第逐一更新する。

再帰関数系

Codeforces Beta Round #62 D. Half-decay tree

http://codeforces.com/contest/68/problem/D

クエリ系?

Good Bye 2014 D. New Year Santa Network

http://codeforces.com/contest/500/problem/D

未解決

http://agc007.contest.atcoder.jp/tasks/agc007_c
      • -

以下、個人的なメモ(解説含む)。

Codeforces Round #362 (Div. 2) D. Puzzle

http://codeforces.com/contest/697/problem/D
解いたことあって、解説まで書いたことある
ある2ノードについて注目した時にどちらかが先にあるかの確率は1/2であることを利用している。
上手いこと、期待値の式を変形して、独立なところを抜き出して解く感じ。
解説
https://kimiyuki.net/blog/2016/07/15/cf-697-d/
http://ei1333.hateblo.jp/entry/2016/07/15/193445
http://hamayanhamayan.hatenablog.jp/entry/2016/07/15/141709

Codeforces Beta Round #62 D. Half-decay tree

http://codeforces.com/contest/68/problem/D
流れ
1. DFSをして期待値を計算する愚直な再帰関数を書く
2. 枝刈りをすると全然間に合う
再帰関数で書ける表現は期待値問題でよく見る気がする。
再帰で愚直に書けないか、まず考えてみよう
解説
http://d.hatena.ne.jp/simezi_tan/20111129/1322492611

yukicoder No.76 回数の期待値で練習

http://yukicoder.me/problems/no/76
dp[i] = 出目の和がi以上となる場合の回数の期待値
dp[i] = 1 + sum(dp[i - 1]*p[1]~dp[i - 6]*p[6])
正直良くわからん。以上なのにこれで上手いこといくの?
解説
https://kimiyuki.net/blog/2016/09/15/yuki-76/
http://kmjp.hatenablog.jp/entry/2015/07/20/1000

yukicoder No.108 トリプルカードコンプ

http://yukicoder.me/problems/no/108
必要な考察・知識
1. 全てのカードの種類に差異は無いので、各足りない枚数分について種類だけ考えれば状態をすごくまとめることができる
dp[i][j][k] = 3枚2枚1枚足りない種類がそれぞれi個j個k個の時に必要な枚数の期待値
2. kmjp「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」
3. 有効なカードを引いたら、その場合に3通りのパターンが考えられる
dp[i][j][k] = n / (i+j+k) + dp[i - 1][j + 1][k] * i / (i+j+k) + dp[i][j - 1][k + 1] * j / (i+j+k) + dp[i][j][k - 1] * k / (i+j+k)
2は知らない知識だったので、身につけておきたい
解説
http://kmjp.hatenablog.jp/entry/2014/12/22/0900
https://kimiyuki.net/blog/2016/10/06/yuki-108/
うさぎ小屋のdpの更新式の第一項が分母分子逆なんで注意

ARC016 C - ソーシャルゲーム

http://arc016.contest.atcoder.jp/tasks/arc016_3
解説の数式をただ実装するだけ。
これまでの問題が解けるようになっていれば解けるような問題
解説
http://kagamiz.hatenablog.com/entry/2013/11/05/235712

Typical DP Contest J - ボール

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball
これも、これまでの問題が解けるようになっていれば解ける。
ソーシャルゲームと全く同じ要領

Good Bye 2014 D. New Year Santa Network

http://codeforces.com/contest/500/problem/D
独立な部分が無いか探した。
サンプルを考えていると答えが減らした数に応じて減っているように見えたので、そこから考えた。
あと、大学の先生が言っていた「頂点の問題を辺の問題にして考えると解けたりする」というのを実践して、
ある辺についてその辺が使われる組合せを全て考える事で答えを出した。