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

レート冷えてしまった... 問題文和訳はこちら

A. Min Or Sum / Минимальная OR сумма (500点)
B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)
C. Differential Sorting / Дифференциальная сортировка (1500点)
D. Infinite Set / Бесконечный набор (2250点)
E. Cars / Автомобили (2550点): 未提出
F. Closest Pair / Ближайшая пара (3000点): 未提出
結果、感想

A. Min Or Sum / Минимальная OR сумма (500点)

どのように操作しても $\displaystyle \operatorname*{OR}_{i=1}^{n} a_i$ は変化せず、和の値はbitORの値以上です。
$1 \leq i < n$ について順に $a_{i+1} \leftarrow a_i \operatorname{OR} a_{i+1}$ という操作を行うことで $a_n = \displaystyle \operatorname*{OR}_{i=1}^{n} a_i$ とすることができ、また、これを用いて $1 \leq < n$ について $a_i = 0$ にすることができ、 $\displaystyle \sum_{i = 1}^{n} = \operatorname*{OR}_{i=1}^{n} a_i$ を実現することができます。
そのため、答えは $\displaystyle \operatorname*{OR}_{i=1}^{n} a_i$ となります。

B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)

$a_i$ が極大要素であるとき、 $a_{i+1}$ を $\displaystyle \max\{a_i,\,a_{i+2}\}$ ( $i = n-1$ の時は $a_i$ のみ)に置換することで最小回数を実現できます。

C. Differential Sorting / Дифференциальная сортировка (1500点)

時間内には通せなかった... 構築系は苦手だなぁ...
末尾の2要素は変えることができないので、 $a_{n-1} > a_n$ のときは達成不可能です。
$a_n \geq 0$ のときは $1 \leq i \leq n-2$ の各 $i$ に対して $(x,\,y,\,z) = (i,\,n-1,\,n)$ の操作を行うことで達成することができます。
そうでない場合、初期状態で達成していない限り、 $a_i > a_{i+1}$ を満たす最も右の $i$ について $a_i \leq a_{i+1}$ にすることができにないため、達成不可能です。

D. Infinite Set / Бесконечный набор (2250点)

桁DPです。

${\mathrm{dp}}_{i} = (\text{二進数表記で $i$ 桁であるような $S$ の要素の個数})$

としたとき ${\mathrm{dp}}_0 = 0$ で $i > 1$ について ${\mathrm{dp}}_i$ に ${\mathrm{dp}}_{i-2} + {\mathrm{dp}}_{i-1}$ を足すということを順に行うことで答えを求めることができます。
初期値としては $a_1,\,a_2,\,\dots,\,a_n$ についてそれぞれ対応する ${\mathrm{dp}}_i$ に $1$ を加算していけばいいですが、 $a_j$ から $a_k$ が作れる場合は、余計にカウントし、答えが大きくなってしまいますが、 $a_k$ についてはその処理を行うことはせずスキップすることで余計に数えてしまうことをなくすことができます。