AtCoder Beginner Contest 112

AtCoder Beginner Contest 112 (ABC112) の解説です。
AtCoder Beginner Contest 112 旧版
 AtCoder Beginner Contest 112 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 112
rated 1200
10/6(土) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

B - Time Limit Exceeded

求めるべきは $t_i \leq T$ を満たす $c_i$ の中で最小のものなので、minを用いて求めれば良いです。

${\rm O}(N)$ で求めることは可能そうですが、面倒です。
今回はABCであることを加味して、簡単に ${\rm O}(NXY) \leq 10000N$ で解く方法を説明します。
まず、答えの座標 $(C_X, C_Y)$ を決め打ってしまいます。
この時、各 $(x_i, y_i)$ に対して、答えの高さは $h_i=0$ ならば $H \leq h_i + |C_X - x_i| + |C_Y - y_i|$ の範囲に、そうでないならば $H = h_i + |C_X - x_i| + |C_Y - y_i|$ になります。
これを全ての座標に対して試し、矛盾なく一つの高さに定まったらそこを答えとすれば良いです。

D - Partition

まず、少なくとも一つの $a_i$ は $\lfloor \frac{M}{N} \rfloor$ 以下の大きさになるので、答えもそれ以下になります。
その中で最大の最大公約数とは何でしょうか？
まず、答えを $x$ としましょう。この時、全ての $a_i$ は $x$ の倍数です。
つまり、 $M$ は $x$ の倍数となるはずです。
言い換えれば、 $x$ は $M$ の約数の中で、最初に $\lfloor \frac{M}{N} \rfloor$ 以下になる値です。
ということは、約数を列挙して、その中で最初に $\lfloor \frac{M}{N} \rfloor$ 以下になる値を出力すれば良いことが分かります。
約数は $i(1 \leq i \leq \sqrt{M})$ を用いて $M$ が $i$ の倍数ならば $i$ と $\frac{M}{i}$ が約数としていけば列挙できます。
最終的に計算量は ${\rm O}(\sqrt{M})$ です。