Educational Codeforces Round 108のきろく

問題文和訳はこちら

A. Red and Blue Beans / Красные и синие мармеладки
B. The Cake Is a Lie / Торт - это ложь
C. Berland Regional / Берляндский отбор
D. Maximum Sum of Products / Максимальная сумма произведений
E. Off by One / Сдвиг на один: 未提出
F. Chests and Keys / Сундуки и ключи (実行時間制限: 3 sec): 未提出
結果、感想

A. Red and Blue Beans / Красные и синие мармеладки

赤い豆の方が数が少ないとします(多い場合は赤と青を入れ替える)。このとき $r$ 個の小包に分けることができ、各ポケットに青豆を $1$ 個以上 $d+1$ 個以下入れることができるので $b \leq r(d+1)$ のとき条件を満たします。

B. The Cake Is a Lie / Торт - это ложь

どの経路を辿ったとしてもセル $(n,\,m)$ へ到達するのにかかる費用は $nm-1$ burle となります。以下はその証明です。

$n = m = 1$ のとき $1 \cdot 1 - 1 = 0$ より成立。
$n = 1$ または $m = 1$ のとき経路は1通り(それぞれずっと右、下)であり、それぞれ費用は $m-1 = 1 \cdot m -1,$ $n-1= n \cdot 1 -1$ より成立します。
これら以外のセル $(n,\,m)$ については $n + m = l$ についての数学的帰納法で示せます。 $l-1$ について成立を仮定します。このマスに辿り着くには

セル $(n,\,m-1)$ から右に1マス
セル $(n-1,\,m)$ から下に1マス

のいずれかであり、このとき費用は帰納法の仮定を利用してそれぞれ $n(m-1) - 1 + n = nm -1,$ $(n-1)m - 1 + m = nm -1$ より成立するため、これで証明ができました。

C. Berland Regional / Берляндский отбор

大学 $i$ の学生数を $c_i$ とすると、チームメンバー数が $k$ のとき $\displaystyle \left\lfloor \frac{c_i}{k} \right\rfloor$ チームができ、 $\displaystyle \left\lfloor \frac{c_i}{k} \right\rfloor k$ 人が参加します。各大学について強い順に学生をソートし、累積和をとっておくことで高速に計算することができます。

D. Maximum Sum of Products / Максимальная сумма произведений

全ての部分列について計算すると組み合わせが $O(n^2)$ で、和の計算が $O(n)$ より $O(n^3)$ なので間に合いません。
反転する部分列の中心を固定し、幅を $2$ (両方向に $1$ )ずつ大きくすることで和の計算(更新)を $O(1)$ に落とすことができ、間に合うようになります。