Codeforces Round #774 (Div. 2)のきろく

Highest更新!! 問題文和訳はこちら

A. Square Counting / Сколько квадратов? (750点)
B. Quality vs Quantity / Качество против количества (1000点)
C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
D. Weight the Tree / Взвесьте дерево (2000点)
E. Power Board / Степенная таблица (2500点)
F. Playing Around the Table / Игра вокруг стола (3000点): 未提出
結果、感想

A. Square Counting / Сколько квадратов? (750点)

$n^2$ の個数が $k$ である時、 $kn^2$ から $kn^2 + (n+1-k)(n-1)$ までの整数を作ることができます。 $(n+1-k)(n-1) = n^2-1 + k - nk < n^2$ であるため、各 $k$ について作ることができる整数は互いに異なります。したがって、答えは $\displaystyle \left\lfloor \frac{s}{n^2}\right\rfloor$ となります。

B. Quality vs Quantity / Качество против количества (1000点)

赤の要素の和を大きく、青の要素の和を小さくしたいので、赤は大きい方から、青は小さい方から要素をとればいいことが分かります。

予め、大きい方に並べたときの累積和を計算しておくと、青の要素が $k$ 個であるとき、sumの条件を満たす赤の要素の最低個数を二分探索(std::upper_bound等)で調べることができ、その値を $m$ としたとき、 $k + m \leq n$ かつ $k \gt m$ を満たすような $k$ が存在するとき、その数列では条件を満たす彩色方法が存在します。

また、赤の要素数を $m$ としたとき、青が $m+1$ 個の要素で条件を満たせないとき、要素数を増やしても、条件は満たされないため、 $2m + 1 \leq n$ の条件で、大きい方からの $m$ 個の和と小さい方からの $m + 1$ 個の和の大小を比べることでも判別することができます。

C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)

二進数表記で $1$ である桁に対応して足し合わせることで、2の累乗の和として数を表現することができます。
そのため、用いる階乗の集合を定めた時、2の累乗の集合は簡単に求まります。そのため、用いる階乗の集合を全探索すれば良いことが分かります。使える階乗は最大でも $14! = 87\,178\,291\,200$ までであり、 $1! = 1$ と $2! = 2$ は2の累乗でもあるため、 $3!$ から $14!$ までの $12$ 通りです。そのため、それぞれ使う/使わないのbit全探索で間に合うことが分かります。

D. Weight the Tree / Взвесьте дерево (2000点)

この問題はコンテスト中には通せませんでした... 気付けてもよかったのに...
$n = 2$ の場合は、自明でしょう。

$n = 2$ の場合を除いて、隣接する頂点の両方を良い頂点にすることはできません。また、木全体の重みの和を小さく抑えたいので良い頂点の重さはその頂点の次数、そうでない頂点の重さは $1$ になります。
頂点 $1$ を根として次のような木DPを考えることができます。 ${\mathrm{dp}}_{i, j}$ は、 $1$ を根とした部分木で $i$ を良い頂点として( $j$ ? 選ぶ : 選ばない)ときの最適な(良い頂点の数, 重みの和)の組とします。但し、 $j = \mathrm{True}$ のとき、 $i$ の重みには元の木での $i$ の親頂点を考慮します。このときの遷移式は

${\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} \displaystyle \sum_{c \in C_i} {\mathrm{dp}}_{c,\mathrm{False}} + (1,\,d_i)& (j = \mathrm{True})\\ \displaystyle \sum_{c \in C_i} \operatorname{Opt}\{{\mathrm{dp}}_{c,\mathrm{True}},\,{\mathrm{dp}}_{c,\mathrm{False}} \} + (0,\,1)& (j = \mathrm{False}) \end{array} \right.$

となります。ここで $d_v$ は頂点 $v$ の次数を、 $C_v$ は頂点 $v$ の子頂点の集合を表します。また、 $(a,\,b) + (c,\,d) = (a+c,\,b+d)$ とし、 $\operatorname{Opt}$ は適当な状態( $\operatorname{Opt}( (a,\,b),\,(c,\,d)) = (a,\,b) \Leftrightarrow a \gt c \lor (a = c \land b \lt d) \lor (a,\,b) = (c,\,d)$ )を表します。
よって、 $(i,\,j) =$ $(1,\,\mathrm{True}),$ $(1,\,\mathrm{False})$ のそれぞれからDFSによって木DPを行い、 $\operatorname{Opt}\{{\mathrm{dp}}_{1,\mathrm{True}},\,{\mathrm{dp}}_{1,\mathrm{False}} \}$ が答えとなります。

各頂点の重みは経路復元によって求めますが、DFSの際、各 $(i,\,j)$ においての最適条件で、どの子頂点が良い頂点であるかを記憶しておくことで簡単に求めることができます。

E. Power Board / Степенная таблица (2500点)

ボード上の数の集合を $S$ とします。
$1$ 行目は $1$ のみが含まれます。

$2$ 行目以降について考えます。非累乗数 $x$ について $x$ の累乗である $S$ の要素の集合は $\{x^{ij}; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq \lfloor \log_x n \rfloor\}$ となり、その大きさは $\{ij; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq \lfloor \log_x n \rfloor\}$ と等しいです。これらは各 $x$ について互いに素(共通部分を持たない)であるため、上記の集合の要素数が分かればいいです。これは $T_{z} = \#\{ij; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq z\}$ を予め求めておくことで、高速で計算することができます。