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

微減...。問題文和訳はこちら

A. GCD Sum (500点)
B. Box Fitting / Коробка (1000点)
C. Planar Reflections / Отражения от плоскостей (1750点)
D. Bananas in a Microwave / Бананы в микроволновке (2500点): 未提出
E. Two Houses / Два дома (2500点): 保留
F. Christmas Game / Рождественская игра (3000点): 未提出
結果、感想

A. GCD Sum (500点)

$3$ の倍数は各桁の数字の和も $3$ の倍数であり、 $N,$ $N+1,$ $N+2$ のいずれかは $3$ の倍数であるため、少なくともこの中に $\mathrm{gcdSum}$ が $1$ ではないものが存在します。よって $N$ から順に試していくことで答えが得られます。

B. Box Fitting / Коробка (1000点)

大きい方から和が $W$ を超えないように選んでいくのを長方形がなくなるまで繰り返していけばいいです。これはある金額を支払うのに必要な効果の枚数を最小にする問題の考え方を利用できるのですが、それは $2$ の累乗のみであるため、大きさが隣り合う長方形の幅が割り切れる関係であるため貪欲法で求めることができます(参照)。

C. Planar Reflections / Отражения от плоскостей (1750点)

まずDPを考えます。
$$ {\mathrm{dp}}_{i,j} = (\text{崩壊齢が $i$ である粒子が $j$ 枚の平面を通過した後の粒子の数}) $$ とすると、$$ {\mathrm{dp}}_{1,j} = 1 $$ で、$$ {\mathrm{dp}}_{i,0} = 1 $$であり、 $$ {\mathrm{dp}}_{i,j} = \sum_{l = n-j}^{n-1} {\mathrm{dp}}_{i-1,l}$$ という漸化式が成り立ち、答えは ${\mathrm{dp}}_{k,n}$ ですが、このままだと計算量が $O(n^2 k)$ であり間に合いません。そこで累積和を用いることで計算量を $O(nk)$ に落とすことができ、これで間に合います。