AtCoder Regular Contest 116のきろく - Flkanjin’s 競プロ録

A - Odd vs Even (300点)
B - Products of Min-Max (400点)
C - Multiple Sequences (500点)
- 0個目を考える
- 計算する(数学的帰納法)
D - I Wanna Win The Game (600点)
E - Spread of Information (800点、実行時間制限: 3 sec): 未提出
F - Deque Game (800点): 未提出
結果、感想

A - Odd vs Even (300点)

$N$ の素因数 $2$ の重複度( $2$ -進付値)を $e$ とし、 $N$ の約数で $2$ -進付値が $i$ であるような数の集合を $S_i$ とします。このとき $1 \leq i \leq e$ について $S_i = \{2d \mid d \in S_{i-1}\}$ であり、 $i \gt e$ について $S_i = \{\} = \emptyset$ です。

これらより $N$ の正の奇数の約数の個数は $\#S_0$ であり、正の偶数の約数の個数は $\displaystyle \sum_{i = 1}^{e} \#S_i = e\#S_0$ であるので、 $e=0$ のときは正の奇数の約数の方が多く、 $e=1$ のときは両者の数は等しく、 $e \geq 2$ のときは正の偶数の約数の方が多くなります。

B - Products of Min-Max (400点)

$A$ をソートすると $\max B \times \min B =\displaystyle \max_{i \in S} A_i \times \min_{i \in S} A_i$ の値は選んだ最大のインデックスと最小のインデックスで決まることになります。

最大のインデックスが $i,$ 最小のインデックスが $j$ である選び方について考えます。このとき $\max B = A_i,$ $\min B = A_j$ より $\max B \times \min B = A_iA_j$ です。 $i = j$ のときはこのような選び方は $1$ 通りです。 $i \neq j$ のとき $i \gt j$ であり、このような選び方は $j+1,$ $j+2,$ $\dots,$ $i-1$ の $i-j-1$ 個のインデックスをそれぞれ選ぶかどうかの $2^{i-j-1}$ 通りであるので、答えは $\displaystyle \sum_{i = 1}^{N} A_i \left( A_i + \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j \right)$ となります。

括弧の中の $\displaystyle \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j$ については $\displaystyle \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j = 2\sum_{j = 1}^{(i-1)-1} 2^{(i-1) - j - 1}A_j + A_{i-1}$ であるので累積和のような要領で $O(N)$ 求めていくことができ、全体で $O(N \log N)$ で解くことができます。
公式解説では上記の最大と最小を逆にした考えで答えを求めているようです。

C - Multiple Sequences (500点)

最初は $A_1$ の値で場合分けをしようとして時間を食ってしまいました。左側から倍数を考えていくのは数が多く、かつ $1 \leq A_i \leq M$ という条件を満たすと考えるのは非常に困難です。

今回は重複組み合わせ ${}_{n}\mathrm{H}\,{}_{r}$ を用います。これは $n$ 種類のものから重複を許して $r$ 個を選ぶ組み合わせの数で高校の数学Aでやるように ${}_{n}\mathrm{H}\,{}_{r} = {}_{n+r-1}\mathrm{C}\,{}_{r} = \displaystyle\binom{n+r-1}{r}$ となります。丸と仕切りを並べるやつです。

$A_N$ の値を固定したとき $A_1,\,A_2,\,\dots,\,A_{N-1}$ の選び方についてみていきます。 $A_N$ の各素因数 $p$ について重複度を $e_p$ とすると $A_1,\,A_2,\,\dots,\,A_{N-1}$ の素因数 $p$ の重複度は $0$ 以上 $e_p$ 以下の広義単調増加整数列となります。よって $A_1$ での素因数 $p$ の重複度との差を $r$ とすると重複度が増える箇所を $N-1$ 箇所の中から重複を許して $r$ 箇所選んだ時の場合の数となり(重複するときその箇所で $2$ 以上増加)、その場合の数は ${}_{N-1}\mathrm{H}\,{}_{r}$ となります。これは各素因数ごとに独立です。よって、整数 $n$ について素因数 $p$ の重複度を $e_{i,p}$ とすると答えは $\displaystyle \sum_{i = 1}^{M} \prod_{p;\ i の素因数}\hspace{5mm} \sum_{j = 0}^{e_{i,p}} {}_{N-1}\mathrm{H}\,{}_{j}$ となります。素因数も重複度も高々 $O(\log M)$ であるので、組み合わせが高速に求まるように前計算しておくことで $O(M(\log M)^2)$ で求めることができます。

また $\displaystyle \sum_{j = 0}^{e_{i,p}} {}_{N-1}\mathrm{H}\,{}_{j}$ の部分は次の2通りの考え方で高速化することができます。

0個目を考える

便宜上 $A_0 = 1$ というものを最初に追加することで重複度が増える箇所を $N-1$ 箇所の中から重複を許して $e_{i,p}$ 箇所選んだ時の場合の数に帰着することができるので ${}_{N}\mathrm{H}\,{}_{e_{i,p}}$ となります。

計算する(数学的帰納法)

$\displaystyle \sum_{j = 0}^{k} {}_{N-1}\mathrm{H}\,{}_{j} = {}_{N+k-1}\mathrm{C}\,{}_{k}$ となることを証明します。

I) $k = 0$ での成立
${}_{N-1}\mathrm{H}\,{}_{0} = {}_{N-2}\mathrm{C}\,{}_{0} = 1 = {}_{N-1}\mathrm{C}\,{}_{0}$ より成立します。

II) $k$ で成立 $\Longrightarrow$ $k+1$ で成立

$\begin{align} \sum_{j = 0}^{k+1} {}_{N-1}\mathrm{H}\,{}_{j} &= \sum_{j = 0}^{k} {}_{N-1}\mathrm{H}\,{}_{j} + {}_{N-1}\mathrm{H}\,{}_{k+1} = {}_{N+k-1}\mathrm{C}\,{}_{k} + {}_{N+k-1}\mathrm{C}\,{}_{k+1} \\ & = {}_{N+k}\mathrm{C}\,{}_{k+1} = {}_{N+(k+1) - 1}\mathrm{C}\,{}_{k+1} \end{align}$

より成立します。

故にI), II)より数学的帰納法により成立します。
この2つの考え方ですが、 ${}_{N}\mathrm{H}\,{}_{e_{i,p}} = {}_{N+e_{i,p}-1}\mathrm{C}\,{}_{e_{i,p}}$ より両者は同じです。

D - I Wanna Win The Game (600点)

3つ目の条件 $A_1\ \mathrm{xor}\ A_2\ \mathrm{xor}\ \cdots\ \mathrm{xor}\ A_N = 0$ と1つ目の条件 $0 \leq A_i$ より二進法での桁DPを考えます。2つ目の条件 $\displaystyle \sum_{i = 1}^{N} A_i = M$ より各 $A_i$ の桁数は $M$ の桁数以下であるので*1、 $\lfloor \log_2 M \rfloor + 1$ 桁だけ考えればいいことが分かります。 $M \leq 5000$ なので $\lfloor \log_2 M \rfloor + 1 \leq 13$ ですね。また、3つ目の条件より各桁について $A_i$ のその桁が $1$ となるような $i$ は偶数個でなければならないことが分かります。

$$ {\mathrm{dp}}_{i,j} = (\text{下から $i$ 桁を 3 つ目の条件を満たすように決めたときの和が $j$ となる場合の数}) $$ とし、このとき

${\mathrm{dp}}_{0,j} = \left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\text{otherwise}) \end{array} \right.$

であり、 $i \geq 1$ について$$ {\mathrm{dp}}_{i,j} = \sum_{k=0}^{\min\left\{ \left\lfloor \frac{N}{2} \right\rfloor ,\, \left\lfloor \frac{j}{2^i} \right\rfloor\right\}} {}_N \mathrm{C}_{2K}\, {\mathrm{dp}}_{i,j - 2k 2^{i-1}} = \sum_{k=0}^{\min\left\{ \left\lfloor \frac{N}{2} \right\rfloor ,\, \left\lfloor \frac{j}{2^i} \right\rfloor\right\}} {}_N \mathrm{C}_{2K}\, {\mathrm{dp}}_{i,j - 2^i k} $$ となります。総和の上限が少し複雑ですが、これは「配るDP」で書くことによって上限について考えずにコードを組むことができます。

E - Spread of Information (800点、実行時間制限: 3 sec): 未提出

グラフは木となるので葉から...みたいに考えましたが分かりませんでした...

F - Deque Game (800点): 未提出

ゲーム問題苦手...

結果、感想

f:id:Flkanjin:20210329165234p:plain
C問題で前計算の数が少なすぎて3WA出してしまい、それに思い至るまでに時間を食ってしまいました... D問題でも上の桁から考えていたのでそれで考えが少し複雑になってしまい、バグ取りに時間がとられてしまいました。もっと早く通せていれば黄色パフォだったかも...

*1:3つ目の条件より「以下」の部分は「未満」、すなわち同じになることがないことは分かりますが別にそこまで考える必要はないです