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

青に復帰しました。問題文和訳はこちら

A. Strange Table / Странная таблица
B. Partial Replacement / Частичная замена
C. Double-ended Strings / Двусторонние строки
D. Epic Transformation / Эпическая трансформация
- 一番多いのが過半数の場合
- そうでない場合
E. Restoring the Permutation / Восстановление перестановки
F. Triangular Paths / Треугольные пути
G. Maximize the Remaining String / Максимизируй оставшуюся строку
結果、感想

A. Strange Table / Странная таблица

$i$ 行 $j$ 列 ( $i,\,j$ は0オリジン) の"by columns"での数値は $jn + i + 1$ であるので、 $x = jn + i + 1$ より $i = (x-1) \bmod{n},$ $\displaystyle j = \left\lfloor \frac{x-1}{n} \right\rfloor$ が求まります。
$i$ 行 $j$ 列の"by rows"での数値は $im + j + 1$ となるのでこれに代入して答えが求まります。

B. Partial Replacement / Частичная замена

条件を満たしつつできるだけ置き換える'*'を離した時が最適解です。'*'の位置を配列等で記憶しておいてstd::upper_boundなどの二分探索系の関数を用いたり、実際に探していくことで求めることができます。

C. Double-ended Strings / Двусторонние строки

制約が小さいので $a,\,b$ 両方の開始位置と作る文字列の長さを全探索することができます。長さに関しては尺取り法によって高速化できます。
長さが $n$ のとき操作回数は $|a| + |b| - 2n$ となります。よって最大の長さを探せばいいです。

D. Epic Transformation / Эпическая трансформация

制約が小さいので毎回最多2つを減らしていくという貪欲法で通すことはできます。しかし、次のようにも求められます。

一番多いのが過半数の場合

一番多いのとそれ以外のものをペアにして消していくことができ、その個数を $c$ とすると $n - 2(n-c) = 2c - n$ を達成することができます。それ以外の消し方ではこの数を達成することができません。

そうでない場合

$n$ が奇数の時はどうしても1つ残りますが、毎回最多2つを減らしていくことで全てのペアを消すことができます。
この時 $n$ を $2$ で割った余りだけ残ります。

E. Restoring the Permutation / Восстановление перестановки

左から順に答えを作っていきます。辞書順最小のものを $a,$ 最大のものを $b$ とします。

$i = 1$ または $q_i \neq q_{i -1}$ のときは $a_i = b_i = q_i$ となります。

そうでないとき、 $a$ についてはこれまで $a$ に選ばれていない数のなかで最小のものが $a_i$ になります。 $b$ についてはこれまで $b$ に選ばれてない数のうち $q_i$ 未満で最大のものが $b_i$ です。

F. Triangular Paths / Треугольные пути

三角形内において上から下へしか動くことができないので $r$ の小さい順に訪れまるのでそのようにソートしておきます。

$(r,\,c)$ について $(x,\,y) = (r-c,\,c-1)$ と座標変換します。変換後の座標においては $x$ が偶数の時は右、つまり $(x+1,\,y)$ への辺が活性化していて、奇数の時は上、つまり $(x,\,y+1)$ への辺が活性化しています。

さて、 $(r_i,\,c_i)$ から $(r_{i+1},\,c_{i+1})$ へ行くときのコストはどうなるでしょうか? それぞれの変換後の座標を $(x_i,\,y_i),$ $(x_{i+1},\,y_{i+1})$ とします。このとき問題文中の経路が必ず存在するという制約から $x_i \leq x_{i+1},$ $y_i \leq y_{i+1}$ であることが分かります。

$ \displaystyle \left\lfloor \frac{x_i}{2} \right\rfloor \lt \left\lfloor \frac{x_{i+1}}{2} \right\rfloor $ のとき

$x$ が奇数の時 $y$ 座標が $y_{i+1}$ になるまで上に上がり、そこから右に行くことでコスト $\displaystyle \left\lfloor \frac{x_{i+1}}{2} \right\rfloor - \left\lfloor \frac{x_i}{2} \right\rfloor$ で行くことができます。