AtCoder Beginner Contest 159 感想

https://atcoder.jp/contests/abc159

F 問題。$F_i=1+x^{A_i}$ とする。多項式 $G_i$ を次のように定める。

\begin{align}
G_i = (F_i) + (F_i \times F_{i-1}) + (F_i \times F_{i-1} \times F_{i-2}) + \cdots + (F_i \times \cdots \times F_1) = \sum_{j=1}^i \left( \prod_{k=j}^{i} F_k \right)
\end{align}

右端が $i$ のときは $G_i$ の $x^S$ の係数が答え。$G_{i+1} = (G_i + 1) F_{i+1}$ である。$S$ 次式と $1$ 次式の掛け算は $O(S)$ で計算できる。$S$ 次を超えた項は切り捨ててよい。よって全体の計算量は $O(SN)$。

C 問題は L/3 って書いて切り捨てられてしまった。最初、体積が与えられて辺の長さの和を最大化しろだと思ってて、立方体が答えだと一瞬思ってしまった。冷静になると違う。

B 問題は前半が回文、後半が回文は確かめたんだけど、全体が回文になるときを忘れてた。