M-SOLUTIONS プロコンオープン C Best-of-(2n-1)

問題はこちら

問題概要

高橋君と青木君がゲームをする時、高橋君は確率{ \displaystyle A}で勝ち、青木君は{ \displaystyle B}で勝ち、確率{ \displaystyle C}で引き分ける。どちらか片方が{ \displaystyle N}回勝つまでゲームをするとき、ゲームが行われる回数の期待値を求めよ。

考えたこと

期待値を求めると聞いて、{ \displaystyle E(x) = \Sigma^{\inf}_{k=0} kP(k)} という無限の計算ばかり考えていて解けなかった。 解説を自分なりにわかりやすく書き直してみる(記号を自分のわかりやすいように変更している)。

以下のように、ベイズっぽく考えるとわかりやすかった。

• (求める期待値 = 引き分けも起こり得る条件下でゲームが終わるまでの回数の期待値) = (引き分けが起こり得るとき、どちらかが{ \displaystyle 1}回勝つまでの回数の期待値) * (引き分けは起こらないという条件下でのゲームが終わるまでの回数の期待値)

{ \displaystyle P(M)} : 引き分けが起こらないとき、ゲームがちょうど{ \displaystyle M (N \leq M \leq 2N-1)}回行われる確率

とすると、引き分けが起こらないときに高橋君が勝つ確率は、{ \displaystyle \frac{A}{A+B}}、青木君も同様で、

[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) }]

となる。 引き分けが起こり得るとき、どちらかが合計で{ \displaystyle M}回勝つまでの期待値は、幾何分布の期待値に帰着され、

{ \displaystyle M \times \frac{100}{100-C}} となる。

よって、解説pdfの最後の数式が得られる。この数式の、{ \displaystyle \frac{A}{100}}などは、{ \displaystyle \frac{A}{A+B}}の誤りである。

AtCoder Regular Contest 075 E - Meaningful Mean

問題はこちら

問題概要

長さ{ \displaystyle N}の数列{ \displaystyle a_0, a_1, \cdots, a_{N-1}}が与えられたとき、平均が{ \displaystyle K}以上となる部分列の個数を求めよ。

公式解説概要

pdfはこちら

{ \displaystyle b_j = \sum_{i=0}^{j-1} a_i − jK (0 \leq j \leq N)}とおいて、{ \displaystyle b_r > b_l (r > l)}となる{ \displaystyle r, l}の組を求める。{ \displaystyle b_i}{ \displaystyle 0, 1, \cdots, N}の範囲の{ \displaystyle c_i}に変更し、{ \displaystyle 0, 1, \cdots, N}の値の出現回数をBITを用いて保持する。これにより、{ \displaystyle i = 0, 1, \cdots, N}のそれぞれに対し、{ \displaystyle c_0, c_1, \cdots, c_{i-1}}{ \displaystyle c_i}以下の値が何回出現したかをそれぞれ{ \displaystyle O(\log(N))}時間で計算することができる。

分からなかったこと

BITを使うと、なぜ各値の出現回数を保持できるのだろう、、、と思ったけど、indexに各値を、value{ \displaystyle 1}を代入して引数として関数に渡せばいいだけだった。各値以下の出現回数からBITを想起するにはまだまだ修行が必要そう。

AtCoder Beginners Contest 034 D - 食塩水

問題はこちら

問題概要

濃度{ \displaystyle p_i}と重量{ \displaystyle w_i}がわかっている { \displaystyle N}個の食塩水から{ \displaystyle K}個を選んで混ぜる時, 最大の濃度を求めよ。

考えたこと

二分探索を用いて最大濃度を計算するのはすぐわかったが, 以下のコードでのcheck関数をどう実装するか(どのようにその濃度の食塩水を作れるか否か判定するか)分からなかった。

lower = 0
upper = 100
while upper - lower > 10 ** (-5):
    half = (upper+lower) / 2
    if check(half):
        lower = half
    else:
        upper = half

print(lower)

色々実験したところ, 以下の結論に達した。そもそも, 濃度{ \displaystyle P}の食塩水が作れるとはどういうことか? 濃度が{ \displaystyle P}より大きい{ \displaystyle K}個の食塩水が集められれば, 確実に条件を達成できる。では, { \displaystyle K}個集められないときは? 濃度{ \displaystyle p_1(\leq P)}の食塩水{ \displaystyle 1}と, 濃度{ \displaystyle p_2(>P)}の食塩水{ \displaystyle 2}を混ぜるときのことを考えてみよう。それぞれの重さを{ \displaystyle w_1}, { \displaystyle w_2}として,

$$ 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 $$

が成立すれば, この{ \displaystyle 2}つの食塩水を混ぜることで, 濃度{ \displaystyle P}以上の食塩水を作ることができる。これを一般化することで, check関数が実装できる。 優先的に使う食塩水は, { \displaystyle (p_i - P) * w_i}について, 降順に並べることで得られる。

解答

自分が書いたコードは以下

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)