Codeforces Round #702 (Div. 3)のきろく

参加はしていないですが、全問解いたので書いていきます。問題文和訳はこちら

A. Dense Array / Плотный массив
B. Balanced Remainders / Сбалансированные остатки
C. Sum of Cubes / Сумма кубов
D. Permutation Transformation / Трансформация перестановки
E. Accidental Victory / Случайная победа
F. Equalize the Array / Уравняй массив
G. Old Floppy Drive / Старый дисковод
結果、感想

A. Dense Array / Плотный массив

各 $i$ に対して $a_i$ と $a_{i+1}$ の間に $2^1 \min\{a_i,\,a_{i+1}\},$ $2^2 \min\{a_i,\,a_{i+1}\},$ $\dots$ を挿入することで密な配列を作ることができます。挿入する数を $m_i$ とすると $$2^{m_i} \min\{a_i,\,a_{i+1}\} \lt \max\{a_i,\,a_{i+1}\} \leq 2^{m_i+1} \min\{a_i,\,a_{i+1}\}$$

であり、 $m_i$ が整数であることから $m_i = \displaystyle\left\lceil \log_2\left(\frac{\max\{a_i,\,a_{i+1}\}}{\min\{a_i,\,a_{i+1}\}}\right) \right\rceil - 1$ で、答えはこれの和となりますが、 $\log$ の値を直接計算すると誤差が出てくる可能性があるためお勧めしません。最悪ケース $(a = [1,\,50,\,1,\,50,\,\dots])$ の場合でも $m_i = 5$ であるため、実際に挿入する数を計算しても十分間に合うため、そちらで実装する方が良いでしょう。

B. Balanced Remainders / Сбалансированные остатки

$a_i$ を $1$ 増やすという操作は、 $c_{i \bmod 3}$ を $1$ 減らし $c_{(i+1) \bmod 3}$ を $1$ 増やすという操作と等価です。
$c_0 = c_1 = c_2$ となるとき $c_0 = c_1 = c_2 = \displaystyle\frac{n}{3}$ です。そうではない場合、 $c_i \gt \displaystyle\frac{n}{3}$ となる $i$ が存在します。そのような $i$ について過剰分を $(i + 1) \bmod 3$ に移してやるという操作を繰り返すことで、 $c_0 = c_1 = c_2$ にすることができます。

C. Sum of Cubes / Сумма кубов

$a = \sqrt[3]{a^3} \lt \sqrt[3]{a^3 + b^3} = \sqrt[3]{x}$ となるので、 $a$ について $1$ から $\sqrt[3]{x}$ 内の範囲で全探索します。 $b = \sqrt[3]{b^3} = \sqrt[3]{x - a^3}$ については $x - a^3$ が立方数であるかを確かめなければなりませんが、 $a \geq b$ としても一般性を失わず、各 $a$ について $a^3$ の値をstd::setやstd::unordered_set等に記憶させておけば簡単に調べることができます。

D. Permutation Transformation / Трансформация перестановки

$[l, r[$ の部分列から根の深さ $D$ の部分木を構成するとき、 $a_m = \displaystyle\max_{i = l}^{r-1}a_i$ とすると $d_m = D$ であり、 $[l, m[$ と $[m+1, r[$ の部分木から根の深さ $D+1$ の部分木をそれぞれ構成させるので、再帰関数によって実際に1つずつ求めてやることによって答えを作ることができます。

再帰関数の引数としては部分列の左端 $l$ 、右端のインデックス $r$ *1や元の配列 $a$ 、答えの保存用の配列 $d$ 、現在の深さ $D$ が必要です*2。

E. Accidental Victory / Случайная победа

$a$ をソートした列を $b$ とすると、 $\displaystyle\sum_{j = 1}^{i}\,b_j \geq b_{i+1}$ のとき $b_i$ に対応する選手はそれより少ない選手全員と対戦した後にそれよりも $b_{i + 1}$ に対応する選手には勝つことができます。このとき $b_{i + 1}$ に対応する選手が優勝可能性がある場合、 $b_i$ に対応する選手も優勝する可能性があることが分かります。よって、トークンが少ない方から累積和をとって次の選手を倒すことができるかを保存していき、トークンが多い方から優勝可能性があるかを調べていくことで答えが求まります。優勝可能性のある選手の番号を出力する必要があるのでソートする際はstd::pairなどで選手の番号も保存するようにしましょう。

F. Equalize the Array / Уравняй массив

$a$ 内で $x$ が登場する回数を $c_x$ と書くことにし、 $S = \{0\} \cup \{c_x \mid x \in a\}$ とします。 $S$ 内の要素を小さい順に $s_1,\,s_2,\,\dots$ とします。 $C$ の値を1つ決めたとき答えは $$\displaystyle\sum_{c_x \lt C}\, c_x + \sum_{c_x \geq C}\, (c_x - C)$$ となります。これを $v_C$ とします。

$C \notin S$ のときは最小値を与えません。というのも、 $C \gt \max S$ のときは $v_C = v_{\max S} + \max S$ となりますし、 $s_i \lt C \lt s_{i + 1}$ のときは $v_C \gt v_{s_{i + 1}}$ となるからです。

さて $C$ が $S$ の要素を小さい順に遷移していくときの状態遷移を見ていきましょう。 $C = s_i$ から $C = s_{i + 1}$ に移るとします。 $m_i = \#\{ x \mid c_x = s_i\}$ とします。このとき $\displaystyle\sum_{c_x \lt C}\, c_x$ は $m_i\,s_i$ だけ増え、 $\displaystyle\sum_{c_x \geq C} (c_x - C)$ は $\displaystyle(s_{i + 1} - s_{i}) \sum_{j = i}^{\# S}\, m_j$ だけ減ります。依って $m_i$ の和を利用することに依って $v_0 = n$ から各 $v_C$ を求めればいいと分かります。

また、解説のコードは $$\displaystyle\sum_{c_x \lt C}\, c_x + \sum_{c_x \geq C}\, (c_x - C) = \sum_{c_x \lt C}\, c_x + \sum_{c_x \geq C}\, c_x - C \sum_{c_x \geq C}\, 1$$ より $\displaystyle\sum_{c_x \lt C}\, c_x,$ $\displaystyle\sum_{c_x \geq C} c_x,$ $\displaystyle\sum_{c_x \geq C}\, 1$ を遷移させているようです。

G. Old Floppy Drive / Старый дисковод

$s_i = \displaystyle\sum_{j = 1}^i\, a_j,$ $m = \displaystyle\max_{i}\, s_i$ とします。
$s_n \geq 0 \land x \gt m$ のとき、和は $x$ に達することなく1周しますが、そのとき初期状態よりも減った状態で和を再び取り始めるので $x$ 以上になることはなく、永遠に動き続きます。
そうでないとき、フロッピーディスクはいつかは止まります。
$0 \lt x \leq m$ のとき、 $t_1 =s_1 = a_1,$ $t_i = \max\{t_{i-1},\,s_i\}$ となるような $t$ を用意しておくことで $s$ 内の $x$ 以上となる1番左の要素を $t$ 内での二分探索で探すことができます。そのような要素のインデックスから $1$ 引いた値*3が答えです。
$m \lt x$ のとき $s_n \lt 0$ となり、一周するごとに初期和が $s_n$ 増えていくので、 $x - bs_n \leq m$ が成立する最小の $b$ 即ち、 $\displaystyle\left\lceil \frac{x-m}{s_n} \right\rceil$ 回廻した時上の、 $0 \lt x \leq m$ の場合に帰着させることができます。