AtCoder Beginner Contest 110 - 情報妖精の競プロ日記

AtCoder Beginner Contest 110 (ABC110) の解説です。
AtCoder Beginner Contest 110 旧版
 AtCoder Beginner Contest 110 beta版

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

要項

AtCoder Beginner Contest 110
rated 1200
9/23(日) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - Maximize the Formula

この操作を検討すると、変数 $X, Y, Z$ について $ZX+Y$ という形になります。
これは $10Z+X+Y$ という形になるので、要するに一つだけ10倍してから総和するということになります。
当然、最も大きい数を10倍するべきなので、答えは最も大きい数を10倍してから全部足した値です。

B - 1 Dimensional World's Tale

まず、 $X$ を $x_{N+1}$ 、 $Y$ を $y_{M+1}$ と考えても一般性を失いません。
この時、ある $Z$ について任意の $i, j$ において $x_i < Z \leq y_j$ が成り立てば良いことになります。
これは $A=\max(x_i), B=\max(y_i)$ を用いて $A < Z \leq B$ と表せるので、後は $A < B$ かどうかさえ判定すれば $Z = B$ にすれば成立します。

C - String Transformation

先に、条件を満たさない場合を考えます。
これは、ある $i \neq j$ であって $S_i = S_j$ かつ $T_i \neq T_j$ である時、またはその逆です。
これは、各アルファベットについてどれに対応させたかを覚えておき、矛盾が生じたらNoを返せば良いです。
矛盾が無ければYesです。

D - Factorization

$M=\prod_{i=1}^{x} p_i^{e_i}$ とします。 $p_i$ は素数とします。
つまり、 $M$ を素因数分解する訳ですね。
その時、数列 $a_i$ に各素因数を割り当てるとこれは条件を満たします。
逆に、そうではない場合はこのような数列は条件を満たしません。
よって、まず先に $a_i=1$ としておき、各素因数を割り当てるやり方が何通りあるか考えます。
まず、当たり前ですが $i \neq j$ において $p_i$ と $p_j$ は互いに素ですから、独立して計算することができます。
次に、ある $p_i^{e_i}$ について考えてみましょう。 $A^B$ として表します。
この時、 $B$ 個の $A$ を $N$ 個の数列に割り振る組み合わせなので、重複組み合わせを用いて ${}_NH_B={}_{N+B-1}C_{B}$ となります。
よって求める答えは $\prod_{i=1}^{x} {N+B-1}C_{e_i}$ となります。
ここで、注意点としてどうやって ${}_AC_B$ を求めるかを考えましょう。
まず、今回素因数分解という性質から $B \leq \log(M)$ となることが分かっています。
ということは、 $B$ は高々30で抑えられるので、 ${\rm O}(B)$ で求めるアルゴリズムを用いると良いです。
この時の計算量 ${\rm O}(\sqrt{M} + (\log(M))^2)$ となります。
ただし、逆元を求めて計算すると計算量 ${\rm O}(\sqrt{M} + \log(M))$ となります。

結果

oooo 4完(1000点) 1:37-6:29-21:49-72:24 / 72:24
132位

感想

おいB問題、問題バグでWA出たぞふざけんな
結論: これはunratedですね……。