AtCoder Beginner Contest 193のきろく - Flkanjin’s 競プロ録

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)に参加しました。2回目の黄色パフォで、久しぶりにレートが暖まり、Highest附近にまで恢復しました。

A - Discount (100点)
B - Play Snuke (200点)
C - Unexpressed (300点)
D - Poker (400点)
E - Oversleeping (500点)
F - Zebraness (600点): 未提出
結果、感想

A - Discount (100点)

割引金額は $A - B$ 円であるため、割引額は $\displaystyle \frac{A - B}{A}$ であり、答えはこれを百分率にしたものなので $\displaystyle 100 \times \frac{A - B}{A}$ となります。

B - Play Snuke (200点)

答えは $\displaystyle \min_{1 \leq i \leq N,\ A_i \lt X_i} P_i$ です。 $A_i \lt X_i$ となる $i \in [1,\,N]$ が存在しない場合はスヌケマシンを買うことができません。

$2$ 以上の整数 $a,\,b$ を用いて $a^b$ と表される数の方が探しやすいのでそちらを数えてその余事象として答えを求めるのが楽でしょう( $10^{10}$ なんて全探索できないし)。
$b \geq 2$ であるため、 $a^2 \gt N$ となる $a$ は探索しても意味がないので $2 \leq a \leq \displaystyle \left\lfloor \sqrt{N} \right\rfloor$ となります。各 $a$ について $2 \leq b \leq \displaystyle \left\lfloor \log_{a}{N} \right\rfloor$ より、 $a^b \leq N$ となる $(a,\,b)$ の組の個数は $\displaystyle \sum_{a = 2}^{\left\lfloor \sqrt{N} \right\rfloor} \left(\left\lfloor \log_{a}{N} \right\rfloor - 1\right) \leq \sum_{a = 2}^{\left\lfloor \sqrt{N} \right\rfloor} \left(\left\lfloor \log_{2}{N} \right\rfloor - 1\right) \lt 3\,200\,000$ となります(上界はかなり大雑把な計算で実際のところ上限は $102\,719$ になります)。
よってこの範囲で $a,\,b$ について全探索することで答えが求まりますが $2^4 = 4^2 = 16$ のように重複するものが存在するため、集合に入れて、あとで要素数をgetter(size())でとってくるようにしましょう。

D - Poker (400点)

表向きでない $9K - 8$ 枚のカードを全て区別するとき(例えば $5$ のカードを $5_1,$ $5_2,$ $\dots$ のように区別します)、高橋くんと青木くんの5枚目のカードについて全ての組み合わせが同様に確からしくなります。
$$(\text{高橋くんの勝つ確率}) =\displaystyle \frac{(\text{高橋くんの勝つ事象数})}{(\text{全事象の場合の数})}$$となるので、高橋くんと青木くんの5枚目のカードについてそれぞれ1から9の $81$ 通りについて、事象数とどちらが勝つかを計算していくことになります。
それぞれについてどちらが勝つかについては問題文中の $\displaystyle \sum_{i=1}^9 i \times 10^{c_i}$ をそのまま計算すればいいです。事象数は高橋くんの5枚目を $a$ 、青木くんの5枚目を $b$ とし、表になっていない $i$ の枚数を $\mathrm{cnt}_i$ とすると $\left\{ \begin{array}{ll} \mathrm{cnt}_a\, \mathrm{cnt}_b & (a \neq b)\\ \mathrm{cnt}_a(\mathrm{cnt}_a - 1) & (a = b) \end{array} \right.$ となり、これらについて総和をとることで必要な数値を計算することができます。
この事象数の計算の際、打ち間違いで少し時間を溶かしてしまいました...

E - Oversleeping (500点)

時刻 $t$ に電車が街 $B$ で停車している条件は $X \leq t \bmod (2X + 2Y) \lt X + Y$ であり、同時刻に高橋くんが起きている条件は $P \leq t \bmod (P + Q) \lt P + Q$ となります。この時 $Y$ と $Q$ の値が小さいことからこの範囲で $t \bmod (2X + 2Y)$ と $t \bmod (P + Q)$ を全探索することを思いつくことができます。
$$\left\{
\begin{array}{ll}
t \equiv a \pmod{(2X + 2Y)} & (X \leq a \lt X + Y)\\
t \equiv b \pmod{(P + Q)} & (P \leq b \lt P + Q)
\end{array}
\right.$$としたとき、この連立合同式は(解が存在する場合)中国剰余定理から求めることができます。中国剰余定理についてはこの記事参照。
AtCoderにおいては中国剰余定理は<atcoder/math>のatcoder::crtを用いることで実装を省くことができます(コンテスト中は忘れてました...)。