AtCoder Beginner Contest 127

サーバーが大丈夫だったようでほっとしました
しかしこちらは冷えてしまいました

A - Ferris Wheel (100点)

問題: A - Ferris Wheel
問題文の通りに出力する。 $B$ が偶数なのでそのまま $2$ 割ってもOK。 $O(1)$ 。

拙解 (C++14): Submission #5591437 - AtCoder Beginner Contest 127

B - Algae (200点)

問題: B - Algae
問題文のとおりに愚直に10回やっても余裕で間に合ってAC。 $O(1)$ 。

拙解 (C++14): Submission #5586496 - AtCoder Beginner Contest 127

C - Prison (300点)

問題: C - Prison
区間 $[L_i, R_i]$ の積集合に含まれる整数の数を求めればいいので、
$\displaystyle \bigcap_{i=1}^N [L_i, R_i] = [\max_i \{L_i\}, \min_i \{R_i\}]$
より、 $\min_i \{R_i\} - \max_i \{L_i\} + 1$ と $0$ のうち小さくないほうを出力してAC。 $O(M)$ 。

拙解 (C++14): Submission #5589129 - AtCoder Beginner Contest 127

D - Integer Cards (400点)

問題: D - Integer Cards
書き換える前の差を考えると、なるべく小さい数字をなるべく大きい数字で書き換えるのが最適となる。よって、入力をソートして貪欲法で書き換えて全部足してAC。 $O(N\log N+M\log M)$ 。

拙解 (C++14): Submission #5597922 - AtCoder Beginner Contest 127

最初からあるカードを「 $1$ 枚の $A_i$ が書かれたカード」、書き換えを「 $B_j$ 枚の $C_j$ が書かれたカード」と考えて大きいほうから貪欲に $N$ 枚とる、という $O(N+M)\log (N+M)$ のきれいな解法もあったみたいです

拙解 (C++14、コンテスト終了後): Submission #5624761 - AtCoder Beginner Contest 127

E - Cell Distance (500点)

問題: E - Cell Distance
制約の $NM \le 2 \times {10}^5$ に注意して考察する。
まず、駒をすべて区別して考えて、 $t_1, t_2, \cdots, t_K$ とすると、 $t_1$ と $t_2$ の間にかかるコストを計算すればほかのすべての駒のペアに関しても同じことが成り立つ。なので $t_1, t_2$ の置き方全通りにおけるコストを二次元累積和を使って計算し（ $O(NM)$ ）、他の $K-2$ 個の駒が $NM-2$ 個のマスにおけるので ${}_{NM-2}P_{K-2}$ 通り存在し、ペアの選び方が ${}_K C_2$ 通り存在するため、これらをかける。最後に、もともとは駒を区別しないので $(K!)^{-1}$ をかけてAC。 $O(NM)$ 。