キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

F はすぐ解けたんだけど，E で詰まりに詰まった...

A - Discount

$\dfrac{100(A-B)}{A}$ が答え．

B - Play Snuke

$\displaystyle \min _ {\overset{\scriptstyle 1\leq i\leq N,}{A_i\lt X_i}}P _ i$ が答え．

1 行で書いてみた (Python)．

print(min(p for _, p, _ in L) if (L := [*filter(lambda t: t[0] < t[2], ([*map(int, input().split())] for _ in range(int(input()))))]) else -1)

C - Unexpressed

$b\geq 2$ より， $a ^ b\leq N$ を満たす $a$ は高々 $\lfloor\sqrt{N}\rfloor$ である．また， $a\geq 2$ を固定すると， $a ^ b\leq N$ を満たす $b$ は高々 $\lfloor\log _ a N\rfloor$ である．

従って， $a\geq 2$ , $b\geq 2$ , $a ^ b\leq N$ を満たす $a$ , $b$ の全探索は $O(\sqrt{N}\log N)$ 時間で可能である．

注意しないといけないのは $2 ^ 4 = 4 ^ 2$ のような重複を除く必要があるという点で，これは既に現れた値を集合型で管理すれば可能である．

D - Poker

スコア計算式はハリボテで，その実は # の中身を全通り試して確率を計算する問題．実装が面倒．

既に確認されている $8$ 枚のカードを除いた $9K-8$ 枚からランダムに残りの $2$ 枚を引くと考える． $9K-8$ 枚のカードのうち， $i$ が書かれたカードの枚数を $X_i$ とすると，高橋君が $i$ ，青木君が $j$ を引く確率 $p_{i, j}$ は次のように表される．

$p_{i,j} = \begin{cases} \dfrac{X_i\cdot X_j}{(9K-8)(9K-9)} & \text{(if $i\neq j$)}\\ \dfrac{X_i\cdot (X_i-1)}{(9K-8)(9K-9)} & \text{(if $i = j$)} \end{cases}$