コンテストページ:
コンテスト中AC: A〜E

D - Factorial and Multiple

制約上、 $O(\sqrt{K})$ くらいの解法、すなわち素因数分解や約数を利用した解法を疑います。今回は素因数分解で解けました。

$K$ が素因数 $p$ を1つだけ持つとします。 $N!$ は $K$ の素因数を全て含む必要がありますが、 $p$ は合成数ではないので、2つ以上の正整数の積で表すことができません。従って、少なくとも $p!$ は必要であり、 $N\geq p$ であることが確定します。

$p$ が2個含まれる場合を考えると、 $p!$ の次に $p$ が現れるのは $2p!$ なので、 $N\geq 2p$ が確定します。

一般化すると以下が言えそうですが、これは誤りです。

$K$ に素因数 $p$ が $e$ 個含まれる時、 $N\geq ep$ が成り立つ

反例として、 $K=8$ があります。
2が3個含まれるので、 $N\geq 6$ が必要かといえば、そうではなく、 $N\geq 4$ で達成できます。
これは $p$ の倍数に $p$ が2個以上含まれることによって発生しています。

そこで、以下は成り立つと言えます。

$K$ に素因数 $p$ が $e$ 個含まれるとする。 $p,2p,\cdots ep$ の順に探索し、 $p$ の数が $e$ 個以上に初めてなるものを $kp$ とするとき、 $N\geq kp$ が成り立つ

これを $K$ に含まれる素因数全てについて求めていきます。
$K=p_1^{e_1}\times p_2^{e_2} \times \cdots \times p_m^{e_m}$ と素因数分解されたとすれば、各素因数について前述の値を求め、それらを $x_1,x_2,\cdots ,x_m$ とすると、

$N\geq max\{x_1,x_2,\cdots x_m\}$

が成り立つ必要があるので、 $N$ としてとりうる最小値は $max\{x_1,x_2,\cdots x_m\}$ であり、これが答えです。

かなり大雑把に計算量を見積もります(間違っていたらすみません)。
素因数は2以上なので、素因数の個数の和は $logK$ 個以下です。よって、各素因数について各倍数を調べる部分は合計 $logK$ 回以下です。また、各倍数に含まれる素因数の個数も $logK$ を超えないはずなので、かなり大雑把に見積もっても $O(log^2 K)$ で済みます。

そのため、おそらく素因数分解の計算量がボトルネックとなります。
素因数分解はあまり効率的ではない試し割りであっても、 $O(\sqrt{K} + logK)$ くらいかと思います。(素因数の個数が合計で $logK$ 個以下なので、同じ素因数で複数回割る部分を考慮して $logK$ をつけましたが、不要かもしれません)

提出コード: Submission #36979663 - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

E - Critical Hit

期待値DPの典型的な考え方で解けます。

状態 $u$ が遷移元でその期待値を $E_u$ とする。
状態 $v_1,v_2,\cdots v_m$ に遷移し、
遷移先の期待値が $E_{v_1},E_{v_2},\cdots E_{v_m}$ で、
遷移する確率が $p_{v_1},p_{v_2},\cdots p_{v_m}$ で、
遷移にかかる操作回数が $w_{v_1},w_{v_2},\cdots w_{v_m}$ の時、
$E_u = p_{v_1}(E_{v_1} + w_{v_1}) + p_{v_2}(E_{v_2} + w_{v_2})+\cdots + p_{v_m}(E_{v_m} + w_{v_m})$