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

#総合結果
* [Score] 1500 pts
* [Time] 36:32 + <font color="red"> 05:00 $\times$ 0 </font> = 36:32
* [Ranking] 126 th [Rated内: 34 th]
* [Performance] <font color=#FF8000> 2400　</font>
* [Rating] <font color=#0000FF> 1849 </font> → <font color=#0000FF> 1918 </font> (+69) <b>Highest!!</b>

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:00|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc193/submissions/20517428)||
|<font color=#808080> B問題 </font>|200 pts|04:05|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc193/submissions/20522388)||
|<font color=#808080> C問題 </font>|300 pts|06:27|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc193/submissions/20524907)<br>($a$ を固定)|[■](https://atcoder.jp/contests/abc193/submissions/20557899)<br>($b$ を固定)|
|<font color=#008000> D問題 </font>|400 pts|17:29|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc193/submissions/20531917)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>36:32</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc193/submissions/20538026)|[■](https://atcoder.jp/contests/abc193/submissions/20559796)<br>(高速化1)|
|<font color=#FF8000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<b>Total</b>|<b>1500 pts</b>|<b>36:32</b>||||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 9) </font> [Discount](https://atcoder.jp/contests/abc193/tasks/abc193_a)
定価 $A$ 円の商品が $B$ 円で売られている時, 定価から見た割引率は $\dfrac{A-B}{A}$ である. ここで, 要求されているのは百分率であることから, 出力しなければならない値は $100 \times \dfrac{A-B}{A}$ である.

##<font color=#808080> B問題 (200pts, diff: 37) </font> [Play Snuke](https://atcoder.jp/contests/abc193/tasks/abc193_b)
店 $i$ について, 高橋くんが到着するまでに, $0.5=1-0.5, 1.5=2-0.5, \dots, A_i-0.5$ 分後に在庫が1個減る可能性があり, これは $A_i$ 回ある. よって, 高橋くんが店 $i$ でスヌケマシンを買うことができるためには, $A_i<X_i$ を満たさなくてはならない.

答えは, このような $i$ が1つでも存在すれば,
$$\min_{\substack{i=1, \dots, N \\\\ A_i<X_i}} P_i$$
であり, 上を満たす $i$ が一つも存在しなければ, スヌケマシンを買うことはできない.

##<font color=#808080> C問題 (300pts, diff: 379) </font> [Unexpressed](https://atcoder.jp/contests/abc193/tasks/abc193_c)
まず, $2$ 以上の整数 $a,b$ を用いて, $x=a^b$ と表わせるような正の整数 $x$ は疎[^c1]であることに気が付かなければならない.

$2$ 以上の整数 $\alpha$ に対して, $a=\alpha$ と固定する. このとき, $b$ に関する列 $(\alpha^b)_{b=2}^\infty$ は単調増加列であることから, $X$ を2以上の整数全体の集合として,
$$\exists \beta\_\alpha \in X {\rm ~s.t.~} \forall k \in X;~ k \leq \beta\_\alpha \iff \alpha^k \leq N$$
となる. $\alpha=2, \dots, \lfloor \sqrt{N} \rfloor$ それぞれに対して, $\beta\_\alpha$ は愚直に求めることができる.

集合 $S$ を
$$S:=\bigcup_{\alpha=2}^{\lfloor \sqrt{N} \rfloor} \left\\{\alpha^k \in X|2 \leq k \leq \beta\_\alpha \right \\}$$
とすると, $S$ は$2$ 以上の整数 $a,b$ を用いて, $x=a^b$ と表わせるような $1$ 以上 $N$ 以下の整数全体の集合であるから, $S^c$ が求めるべき集合である. よって, 求めるべき値は
$$|S^c|=|\\{1, \dots, N \\}|-|S|=N-|S|$$
である.

計算量は $O(\sqrt{N} \log N)$ である. また, この解説では $a=\alpha$ と固定したが, $b=\beta$ と固定することによっても一応解くことはできるが, $a$ を固定したほうが累乗の結果を再利用できる.

[^c1]: 砕けた言い方をすると, レアであるという意味である.

##<font color=#008000> D問題 (400pts, diff: 866) </font> [Poker](https://atcoder.jp/contests/abc193/tasks/abc193_d)
カードは$9$ 種類しかないことから, 4枚目まで確定している状況で, 2人の5枚目のシナリオは高々 $9^2=81$ 通りである.

4枚目まで決定した状況下における各 $i$ のカードの残り枚数を $R_i$ とする. ここで,
$$\sum_{i=1}^9 R_i=9K-8$$
であることに注意する.

以下, 高橋くん, 青木くんの5枚目が $(a,b)$ であるときのシナリオについて考える. まず, このようなシナリオが発生する確率 $P_{a,b}$ は場合の数における考え方から,
$$P\_{a,b}=\left(\begin{cases} C_a (C_a-1) & (a=b) \\\\ C_a C_b & (a \neq b) \end{cases} \right) \times \dfrac{1}{(9K-8)(9K-9)}$$
である.

ここで, $(a,b)$ というシナリオにおける勝敗は $O(1)$ で判定できることに注意すると, 求めるべき確率は高橋くんが勝つシナリオ全体の集合 $\mathcal{S}$ とすると, $(a,b) \neq (a',b')$ ならば, $(a,b), (a',b')$ のシナリオは同時に起こらないことから, 
$$\sum_{(a,b) \in \mathcal{S}} P_{a,b}$$
である. [^d1] なお, 計算量は $K$ に影響しないことから, $O(1)$ である.

[^d1]: $\mathcal{S}$ について, 本来ならば, 起こり得ない場合(例えば残り1枚で $a=b$ のとき) を考慮しなければならないが, このような $(a,b)$ についてはうまいこと $P_{a,b}=0$ となる.

##<font color=#0000FF> E問題 (500pts, diff: 1948) </font> [Oversleeping](https://atcoder.jp/contests/abc193/tasks/abc193_e)
非負整数 $a,b$ に対して, $[a,b)$ で $a$ 以上 $b$ 未満整数全体の集合とする.

$S_n:=[(2X+2Y)n+X,(2X+2Y)n+X+Y), T_m:=[(P+Q)m+P,(P+Q)(m+1))$ とすると, $S_n$ は $n+1$ 回目に電車が街Bに止まっている時刻全体の集合, $T_m$ は $m+1$ 回目に高橋くんが起きている時刻全体の集合である. この $S_n, T_m$ を用いて, 問題は
$$\min \left(\left(\bigcup_{n=0}^\infty S_n \right) \cap \left(\bigcup_{m=0}^\infty T_m \right) \right)$$
を求めよという問題に帰着できる.

以下, 正整数 $p$ と $a<p$ なる非負整数 $a$ に対して, $[a]_p$ で $p$ で割った余りが $a$ である非負整数全体の集合とする. また, 簡単のために, $Z=X+Y, R=P+Q$ とする.

$\mathbb{S}=\displaystyle \left(\bigcup_{n=0}^\infty S_n \right)$ について, 電車の状態は $2Z$ -周期であることから, $\mathbb{S}$ について,
$$\mathbb{S}=\bigcup_{a=0}^{Y-1} [X+a]_{2Z}$$
が成り立つ.

同様の議論で, $\mathbb{T}=\displaystyle \left(\bigcup_{m=0}^\infty T_m \right)$ として,
$$\mathbb{T}=\bigcup_{b=0}^{Q-1} [P+b]_R$$
が成り立つ.

よって,

```math
\begin{align*}
\mathbb{S} \cap \mathbb{T}
&=\left(\bigcup_{a=0}^{Y-1} [X+a]_{2Z} \right) \cap \left(\bigcup_{m=0}^{Q-1} [P+b]_{R} \right) \\\\
&=\bigcup_{\substack{0 \leq a <Y \\\\ 0 \leq b <Q}} ([X+a]_{2Z} \cap [P+b]_R)
\end{align*}
```

となる. ここで, 一般的に $[s]_x \cap [t]_y$ については1次不定方程式を解くことによって, 以下の場合のどちらか一方が成立する.

* $[s]_x \cap [t]_y=\emptyset$
* $[s]_x \cap [t]_y=[r]_z$ となる正の整数 $z$ と非負整数 $r~(0 \leq r<z)$ が存在する.

以上のことから,
$$\mathbb{S} \cap \mathbb{T}=\bigcup_{i=1}^K [r_i]_{z_i}$$
となる. ここで, $K=0$ ならば, $\mathbb{S} \cap \mathbb{T}=\emptyset$ なので, 高橋くんが街Bで電車を降りることはできず, 答えは $\infty$ である.

以下, $K \geq 1$ とする. $[r_i]\_{z_i}$ について, 非負整数 $k$ を用いて, $r_i+k z_i$ と表わせる時刻には必ず高橋くんが街Bで電車を降りることができる. $\min [r_i]\_{z_i}=r_i$ であることに注意すると, 求めるべき答えは
$$\min_{i=1, \dots, K} r_i$$
である.

計算量は 各 $a,b$ について, $[X+a]_{2Z} \cap [Y+b]_R$ の検証で拡張ユークリッドを用いることによって, 計算量 $O(\log (2Z+R))=O(\log (X+Y+P+Q))$ ででき, $a=0, \dots, Y-1, b=0, \dots, Q-1$ の全てを走ることから, 1テストケース当たり $O(YQ \log (X+Y+P+Q))$ で求めることができた.

なお, 工夫によって, 計算量を $O((Y+Q) \log (X+Y+P+Q))$ や, $O(Y+Q+\log(X+Y+P+Q))$  にすることもできる.

###高速化1
(2021/02/28 加筆)
最小値を取る $a,b$ について, $a=0$ または $b=0$ が成り立っていることがわかる. 実際, 最小値 $r$ を $a,b>0$ のときにとるとすると, $a-1, b-1$ のときにも高橋くんは街Bで降りることができるが, このときは $r-1$ となり, 最小値に矛盾する. よって, $a=0$ のときと $b=0$ のときを調べれば, 計算量を $O((Y+Q) \log (X+Y+P+Q))$ に削減することができる.



##<font color=#FF8000> F問題 (600pts, diff: 2475) </font> [Zebraness](https://atcoder.jp/contests/abc193/tasks/abc193_f)
(正解でき次第更新 (keyword: 燃やす埋める問題))
#感想

##総評
今回のコンテストは<font color=#00C0C0>水</font>diffの問題が出ず, <font color=#0000FF>E問題</font>のdiffも2000近いことから, 黄色を目指すならば<font color=#0000FF>E問題</font>が解けるかどうかが今回の鬼門となった.

##良かった点
* <font color=#0000FF> E問題 </font> を高速に解くことができ, 2度目の<font color=#FF8000>橙</font> Performanceを達成できた. (<font color=#FF8000>橙</font> Performance のボーダーは 1500 pts, 42:46)

##反省点
* ただ, <font color=#0000FF>E問題</font> は1次不定方程式に関する問題だったので, もう少し速くてもよかった (実装面で).