キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)解法メモ（全問題）

タイトルが長すぎる

リアルタイムで参加できなかったコンテストのブログが抜けてて気になったので、暇なときに解き直してブログを書くことにしました。

A - Discount

算数。割合の計算は比を使った式で書くとわかりやすいと個人的に思う。
$A:100 = B:x$
と考えてもいいし、
$A:B = 100:x$
と考えてもいい。どちらにせよ
$x = \dfrac{100B}{A}$
という式になる。比を使った式の好きなところはこういうところ。

何パーセント引きか聞かれているので、 $100 - \dfrac{100B}{A}$ が答え。計算量は $O(1)$ 。

B - Play Snuke

1軒しかお店が無いとする。このとき、 $A$ 分かけてお店に着いた時、スヌケマシンの在庫は $\max (X-A, 0)$ である。在庫が $1$ 以上のとき、つまり $X-A$ が $1$ 以上のときに限り $P$ 円でスヌケマシンを買うことができる。

お店が $N$ 軒に増えた場合でも各店舗での購入条件と購入金額はかわらない。また、どのお店を選んでも、その選択が影響することはないので、スヌケマシンを買うことができるお店のうち一番安く買えるお店での購入金額を求めればよい。計算量は $O(N)$ 。

C - Unexpressed

事象 $A$ とその余事象 $A^c$ の和は全事象 $\Omega$ である。
「 $a^b$ と表せないもの」＝「全体」 $-$ 「 $a^b$ と表せるもの」
なので、「 $a^b$ と表せるもの」の個数をカウントする。

「 $a^b$ と表せるもの」の個数を上から評価する（最大値を見積もる）。
$a$ を固定したとき、 $b$ を増やすと $a^b$ も増加する。よって、 $1 \le a^b \le N$ を満たす $b$ の個数は $b = \log_a N$ である。
$2 \le b$ に注意すると、 $a$ は最大で $\sqrt N$ 程度まで大きくなるので、全体の個数としては $\sqrt N \times \log_2 N$ 程度となる。（上から評価しているので、 $a=2$ として計算した。）
この値は $N=10^5$ のときでもおよそ $1.6 \times 10^6$ であるため、 $(a, b)$ の組を全探索しても実行時間制限に間に合うことがわかった。

カウントするときは重複やオーバーフローに注意して実装する。重複を避けるにはC++のsetなどを用いる。 $a=\lfloor N \rfloor$ で探索を打ち切る処理を忘れるとTLEするので注意。計算量は $O(\sqrt N \log N)$ 。

D - Poker

かなり考えることが多いので順を追って考察する。

まず、「高橋君の勝つ確率」は $\dfrac{高橋君が勝つパターンの数}{全てのパターンの数}$ で求められる。ここで言う「すべてのパターン」とは、すでに表向きになっていて裏向きのカードとして選ばれることのない $8$ 枚を除いた $9K-8$ 枚から $2$ 枚（高橋君の裏向きのカード $1$ 枚と青木君の裏向きのカード $1$ 枚）を選ぶ方法を指す。よって分母は ${}_{9K-8} \mathrm{ C }_2$ となる。

高橋君に配られた裏向きのカードを $x$ 、青木君に配られた裏向きのカードを $y$ と置く。高橋君が勝つパターンの数をカウントしたい。裏向きのカードが何の数かわかれば手札の点数を求めることができるが、ここで $9K-8$ 枚の中から $2$ 枚選ぶような全探索をすると $O(K^2)$ の計算量となってしまうので実行時間制限に間に合わない。しかし、 $(x, y)$ の組み合わせとしては $81$ 通りしかないので、 $x$ と $y$ を決めたとき $(x, y)$ が選ばれるのは何通りか求められれば、高橋君が勝つパターンの数も高速に求められる。

整数 $i$ が書かれたカードの残り枚数を $C_i$ とする。 $x=y$ なら、 $C_x$ 枚の中から $2$ 枚選ぶので ${}_{C_x} \mathrm{C}_2 = C_x(C_x - 1)$ 通りである。 $x\neq y$ なら、 $C_x$ 枚の中から $1$ 枚、 $C_y$ 枚の中から $1$ 枚それぞれ選ぶので $C_xC_y$ 通りである。高橋君の手札の点数が青木君の手札の点数より高い場合にこの通り数をそのままカウントに加えることで、確率を求めることができる。

計算量は、手札の枚数を $N$ 、カードに書かれた整数の種類数を $C$ として $O(N+C^3)$ 。この問題では $N=5, C=9$ であるため十分高速に動作する。

E - Oversleeping

電車の停止する区間は周期的に訪れ、 $\bmod (2X+2Y)$ 上で一定である。高橋君の起きる区間も同様に、 $\bmod (P+Q)$ 上で一定である。
ここで、中国剰余定理（CRT）を活用する。この定理は、
「 $a$ で割ると $p$ 余り、 $b$ で割ると $q$ 余る整数 $x$ は $\bmod (\mathrm{lcm}(a, b))$ 上にちょうど1つだけ存在する」
ということを言っている。さらに、この解となる整数 $x$ を構成する効率的なアルゴリズムが知られていて、 $O(\log(a+b+p+q))$ で動作する。実装には拡張ユークリッドの互除法を用いることが多いが、atcoder libraryに実装されているcrtをそのまま用いることもできる。

制約より、 $Y$ と $Q$ が小さいことがわかる。よって、電車が停止してから $i$ 秒後のタイミングと、高橋君が起きてから $j$ 秒後のタイミングが初めて一致するときがいくつか求め、 $(i, j)$ の組を全探索して最小値を求めればよい。具体的には、以下の2つの合同式を同時に満たす解 $x$ の最小値を、 $0\le i\lt Y, 0\le j\lt Q$ の範囲で全探索する。