###### 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)