M-SOLUTIONS プロコンオープン C Best-of-(2n-1)
問題概要
高橋君と青木君がゲームをする時、高橋君は確率で勝ち、青木君はで勝ち、確率で引き分ける。どちらか片方が回勝つまでゲームをするとき、ゲームが行われる回数の期待値を求めよ。
考えたこと
期待値を求めると聞いて、 という無限の計算ばかり考えていて解けなかった。 解説を自分なりにわかりやすく書き直してみる(記号を自分のわかりやすいように変更している)。
以下のように、ベイズっぽく考えるとわかりやすかった。
• (求める期待値 = 引き分けも起こり得る条件下でゲームが終わるまでの回数の期待値) = (引き分けが起こり得るとき、どちらかが回勝つまでの回数の期待値) * (引き分けは起こらないという条件下でのゲームが終わるまでの回数の期待値)
• : 引き分けが起こらないとき、ゲームがちょうど回行われる確率
とすると、引き分けが起こらないときに高橋君が勝つ確率は、、青木君も同様で、
[tex:{ \displaystyle P(M) = \binom {M-1}{N-1} (\frac{A}{A+B})N (\frac{B}{A+B})^{M-N} + (\frac{A}{A+B})^{M-N} (\frac{B}{A+B})N) }]
となる。 引き分けが起こり得るとき、どちらかが合計で回勝つまでの期待値は、幾何分布の期待値に帰着され、
となる。
よって、解説pdfの最後の数式が得られる。この数式の、などは、の誤りである。
AtCoder Beginners Contest 034 D - 食塩水
問題概要
濃度と重量がわかっている 個の食塩水から個を選んで混ぜる時, 最大の濃度を求めよ。
考えたこと
二分探索を用いて最大濃度を計算するのはすぐわかったが, 以下のコードでのcheck関数をどう実装するか(どのようにその濃度の食塩水を作れるか否か判定するか)分からなかった。
lower = 0 upper = 100 while upper - lower > 10 ** (-5): half = (upper+lower) / 2 if check(half): lower = half else: upper = half print(lower)
色々実験したところ, 以下の結論に達した。そもそも, 濃度の食塩水が作れるとはどういうことか? 濃度がより大きい個の食塩水が集められれば, 確実に条件を達成できる。では, 個集められないときは? 濃度の食塩水と, 濃度の食塩水を混ぜるときのことを考えてみよう。それぞれの重さを, として,
$$ p_1 \times w_1 + p_2 \times w_2 - P * (w_1 + w_2) = \\ (p_1 - P) \times w_1 + (p_2 - P) \times w_2 \geq 0 $$
が成立すれば, このつの食塩水を混ぜることで, 濃度以上の食塩水を作ることができる。これを一般化することで, check関数が実装できる。 優先的に使う食塩水は, について, 降順に並べることで得られる。
解答
自分が書いたコードは以下
N, K = map(int, input().split()) WP = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[1], reverse=True) def check(half): cur = 0 salt = sorted(WP, key=lambda x: x[0]*(x[1]-half), reverse=True) for i in range(K): cur += salt[i][0] * (salt[i][1]-half) if cur >= 0: return True return False lower = 0 upper = 100 while upper - lower > 10 ** (-5): half = (upper+lower) / 2 if check(half): lower = half else: upper = half print(lower)