# CF Round \#623 div.2
Original duration: 120min.
Commentary: https://codeforces.com/blog/entry/74214
Difficulty: 800(Gray) - 1300(Green) - 1200(Green) - 1700(Blue) - 2500(Red) - 2800(Bronze)

## A. Dead Pixel
### 問題概要
$a \times b$ グリッドの $(x, y)$ に障害物がある。このグリッド上にとれる最大の長方形面積を求める。

### 解法
$\max(bx, ay, b(a - (x + 1)), a(b - (y + 1)))$

### コメント

## B. Homecoming
### 問題概要
$1$ 次元上の各区間が $2$ 種類の移動方法のいずれかを持つ。それぞれの移動方法に対するコストは移動方法を変えない間常に $a, b$ である。コスト $p$ で右端からどこまでいけるか求める。
### 解法
明らかに出来るだけ同じ移動方法で一気に移動した方がよいので、右から順番にシミュレーションする。
### コメント

## C. Restoring Permutation
### 問題概要
$b_i=\min(a_{2i-1},a_{2i})$ を満たす辞書順最小の順列 $(a_{2n})$ を求める。
### 解法
貪欲に行ってよい。$x > b_i$ を満たす未使用最小の $x$ をペアにする。
### コメント
順列の個数を求める方法も考えてみよう。（$O(N)$, 答えは $2^n\prod_i (2n-2i-b^{\prime}_i)$）
（応用）辞書順で k 番目を求める方法も考えてみよう。（DP で $O(N^2)$）

類題：
- https://yukicoder.me/problems/no/794

## D. Recommendations
### 問題概要
$(a_n)$ があり、各要素 $a_i$ を $+1$ するコストは $t_i$ である。$(a_n)$ を $\rm distinct$ にするための最小コストを求める。
### 解法
下から考えれば、$\rm priority\ queue$ で管理すればよいことがわかる。償却計算量 $O(n\log n)$ になる。
### コメント
上から（下から）見る典型：
- JOI - 日本沈没
- https://atcoder.jp/contests/abc140/tasks/abc140_e

## E. Double Elimination
### 問題概要
最初に $2^n$ チームが番号 $2x-1, 2x$ どうしで対戦し、上位グループと下位グループに分かれる。その後は、上位グループ $2^k$ チームの試合の敗者 $2^{k-1}$ チーム、下位グループ $2^k$ チームの試合の敗者 $2^{k-1}$ チームがそれぞれ下位グループに移動、敗退となり、さらに移動後に残った下位グループ（上位グループの敗者と下位グループの勝者） $2^{k-1} + 2^{k-1}$ チームでの試合の敗者 $2^{k-1}$ チームが敗退となる。この $3$ 試合を繰り返し、最終的に残った上位グループ $1$ チームと下位グループ $1$ チームが対戦する。

チーム $(a_k)$ の合計最大試合数 $\left|\{m\ |\ \exists_i\ a_i \in m\}\right|$ を求める。
### 解法
$\rm dp$ らしい。
### コメント
制約が小さければ最小費用流に帰着できる。

## F. Au Pont Rouge
### 問題概要
文字列 $S$ の分割 $(s_n)\ |\ S=\sum_i s_i$ に対して $\min_i s_i$ を集めた多重集合における後ろから $k$ 番目を求める。
### 解法
$\rm suffix\ array$ を用いて $\rm dp$ を行うらしい。
### コメント
$\min_i s_i$ に対する $|\{(s_n)\}|$ の数え上げ $\rm dp$ に帰着される。うまくやれば $O(n^2k)$ くらいにはなりそう。

## 全体コメント・補足情報
全然関係ないんですが、https://shuzaei.hatenablog.com/entry/adv_20221202 を解いてくれたら嬉しい！