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

インタラクティブ問題があったため、当日は参加していませんが、環境を整えた後、問題を何問か通しました。
問題文和訳はこちら

A. Shifting Stacks / Сдвигая стопки (500点、実行時間制限: 1 sec)
B. Eastern Exhibition / Восточная выставка (1000点、実行時間制限: 1 sec)
C1. Guessing the Greatest (easy version) / Найти наибольшее (простая версия) (750点、実行時間制限: 1 sec) C2. Guessing the Greatest (hard version) / Найти наибольшее (сложная версия) (750点、実行時間制限: 1 sec)
D. Max Median / Максимальная медиана (1750点)
E. Paired Payment / Парный платёж (2250点、実行時間制限: 4 sec): 未提出
F. Pairs of Paths / Пары путей (3000点、実行時間制限: 6 sec): 未提出
結果、感想

A. Shifting Stacks / Сдвигая стопки (500点、実行時間制限: 1 sec)

$h$ に手を加えた後の配列を $H$ とします。 $H_1,\,H_2,\,\dots,\,H_i$ を狭義単調増加にできるとき、 $H_j=\left\{ \begin{array}{ll} j-1 & (j \neq i)\\ i\text{ 以上の整数}\ \ \ \ & (j = i) \end{array} \right.$ にすることができます。このようにすることができるのは $1$ から $i$ までの任意の $j$ について $\displaystyle\sum_{k = 1}^{j}\, h_k \geq \sum_{k = 1}^{j}\, (k-1) = \frac{1}{2}\, j(j-1)$ が成立する時なので、この条件を $1$ から $n$ までの任意の $i$ について成立するかを確かめればいいです。

B. Eastern Exhibition / Восточная выставка (1000点、実行時間制限: 1 sec)

博覧会を立てる場所を $(x,\,y)$ とすると全ての家からの距離の合計は $$\sum_{i = 1}^{n}\, (|x_i - x| + |y_i - y|) = \sum_{i = 1}^{n}\, |x_i - x| + \sum_{i = 1}^{n}\, |y_i - y|]$$ であり、 $x$ 座標と $y$ 座標は独立で、個別に考えてよいことが分かります。それぞれの座標について絶対偏差の和となっていて、絶対偏差の和は中央値( $n$ が偶数の時は2つの中央値を両端とする閉区間内の任意の値)によって最小化されます。よって各座標についてその個数を求めて積をとればいいです。

C1. Guessing the Greatest (easy version) / Найти наибольшее (простая версия) (750点、実行時間制限: 1 sec)
C2. Guessing the Greatest (hard version) / Найти наибольшее (сложная версия) (750点、実行時間制限: 1 sec)

インタラクティブ問題です。イージー版とハード版がありますが、部分点と満点のような関係ですので、ハード版について考えてみます。
まず、全体の配列について尋ねることで2番目に大きい要素の位置 $m_2$ を調べます。区間 $[1,\,m_2]$ について尋ねることで最大要素が $m_2$ より左にあるか右にあるかを調べます( $m_2 = 1$ のときは右側)。初期区間を $\left\{ \begin{array}{ll} [1,\,m_2] & (\text{最大要素が左側})\\ [m_2,\,n]& (\text{otherwise})\ \ \ \ \ \ \end{array} \right.$ として二分探索を行います。区間内に最大値がある場合、 $m_2$ が、そうでない場合は別の数が返ってくるので、区間の端点の一方を最大の場所になるように探索ができます。計算回数は $2 + \left\lceil \log_2 {10^5} \right\rceil = 19$ 以下であるためハード版の条件である20回以内に答えが見つかります。

D. Max Median / Максимальная медиана (1750点)

$b_i = \left\{ \begin{array}{ll} 1 & (a_i \geq m)\\ -1 & (\text{otherwise}) \end{array} \right.$ となるような配列 $b$ を定義した時 $$\mathrm{median}([a_l,\,\dots,\,a_r]) \geq m \Longleftrightarrow \sum_{i = l}^{r} b_i \gt 0 $$ となります。 $b$ について長さが $k$ 以上の区間の最大値が正であればいいのですが、この区間の最大値は累積和と区間端の最大最小から $O(n)$ で求めることができます。よってこの $m$ について二分探索を行うことで $O(n\log n)$ で求めることができます。