---
# System prepended metadata

title: UCUP 2-28

---

###### tags: ucup

# UCUP 2-28


## B
si

$[x^n] (x/(1-x) + x^2/(1-x-x^2) + x^3/(1-x-x^2-x^3) + ...)/(1-x)$

https://oeis.org/A079500


## E
yo




## I

## L



---
## --------------Solved------------------

## D
si

## H
yo

## C
si
正n角形 + 頂点以外で交差しないいくつかの対角線　が与えられる
頂点を2彩色して、すべてのサイクルにたいして、必ず2色現れるようなものを構成

## G
yo

## A
yo

https://atcoder.jp/contests/agc040/tasks/agc040_e 似てる
decreasing a と　increaqsing b の和でかけるか？
xy平面で右下に移動する
x+yが決められてる
左上にいるほうがより良い状態なのでx+y一定のうちどこが一番嬉しいかわかる
具体的な移動は、今いる点よりx+yがおおきければxをふやす
小さければyを減らす 以外やりようがない

yを減らした結果負になったら死亡



次の条件を満たすタプル列(a1, b1), (a2, b2), ..., (ak, bk)を作れ

- a1, a2, ..., ak, b1, b2, ..., bkはすべて1以上n以下
- a1, a2, ..., akはすべてdistinct
- b1, b2, ..., bkはすべてdistinct
- ai <= bi

そして、sum_i max_{j = a_i ... b_i} x_j を最大化

```
31 : k, sum = 1, 1
31 : k, sum = 2, 2
31 : k, sum = 3, 3
31 : k, sum = 4, 4
31 : k, sum = 5, 5

31 : k, sum = 1, 1000000000
31 : k, sum = 2, 2000000000
31 : k, sum = 3, 3000000000
31 : k, sum = 4, 4000000000
31 : k, sum = 5, 5000000000
31 : k, sum = 6, 5000000000
31 : k, sum = 7, 4000000000
31 : k, sum = 8, 3000000000
31 : k, sum = 9, 2000000000
31 : k, sum = 10, 1000000000

31 : k, sum = 1, 9
31 : k, sum = 2, 18
31 : k, sum = 3, 27
31 : k, sum = 4, 36
31 : k, sum = 5, 45
31 : k, sum = 6, 54
31 : k, sum = 7, 59
31 : k, sum = 8, 64
31 : k, sum = 9, 69
31 : k, sum = 10, 74
31 : k, sum = 11, 76
31 : k, sum = 12, 68
31 : k, sum = 13, 45
```

次の条件を満たす数列$x_1, x_2, ..., x_n$, $y_1, y_2, ..., y_n$を構築しろという問題。

- $x_1 \ge x_2 \ge ..., \ge x_n \ge 0$
- $0 \le -y_1 \le -y_2 \le ..., \le -y_n$
- $x_i + (- y_i) \ge a_i$

minimize sum x_i - sum y_i

これは最小費用流の双対問題


## J
si

根付き木が与えられて、頂点1からdfsする
クエリとして数列a_1,..,a_k が与えられる。これを連続部分列として含む dfs order は存在するか?

## K
su

https://atcoder.jp/contests/agc035/tasks/agc035_f に似てるかと思ったけどよく見たら違った

解説: https://img.atcoder.jp/agc035/editorial.pdf

解説中の「標準表現」ってやつは有用かも

## M
yo

おそらく次の問題と同値

文字列Sに対して次の操作を繰り返す、Sを空文字列にするまでの操作回数のminは？n - min(操作回数)を出力

- Sの連続部分文字列として>><<<, >><, <のように、(>をa回) + (<をb回) (abs(a-b) <= 1)となる文字列を選ぶ、それを削除する

## F
yo

O(q sqrt(q) k log n)