# Ukraine

## A
正整数列Aが与えられる
f(A) = \sum A_i * (A_{i+1})
と定める
円形で，(A_n * A_0)も含める
Aの並び替えの内，ｆ（Ａ）の最大値は？

## B
0と1からなる円に並んだ長さnの数列aに対して、f(a)を長さkの連続部分列の総和n個を順番通り(？)に並べた感じの数列(slide和みたいな)で定義する
f(a)としてあり得る数列は何通りあるか

複数テストケース
$k < n \le 10^6$

nとkのgcdをとる
初期値を除くとgcd個の差分サイクルで数列は定義される
ある二つが異なるのに被るとき、サイクルの値がすべて0とすべて1で被っている
すべて0のサイクルとすべて1のサイクルの個数が等しいときまずい

すべて0のサイクルと1のサイクルの個数を全探索するとO(n)な気がするが、間に合わない！
いや0のサイクルの個数が等しいとまずいです
$\sum ((2^{n/g}-2)^{g-i})(i+1)\binom{g}{i}$
↑愚直会いました
$\sum c^{g-i}(i+1)\binom{g}{i}$
とりあえず(c+1)^gを足して、i+1->i
$\sum c^{g-i}g\binom{g-1}{i-1}$
$\sum c^{g-1-(i-1)}g\binom{g-1}{i-1}$
$g(c+1)^{g-1}$
https://manabitimes.jp/math/588

$(c+1+x)^g$の$x^0$と$x^1$の係数和？

(c+1)^g + g(c+1)^(g-1)x

c^0+c^1 \binom{g,1}+..c^2

g個ボールがあって、g-iとiの2パターンに分ける
片方はある数だけc倍、もう片方は高々1個だけ選べる(i+1倍)

## C
n個の"W"とn個の"B"を含む長さ2nの文字列Sが与えられる
2n頂点のグラフを考える
S[i] != S[j] の時，
i-j間に重み |i - j|の辺が存在する
グラフのハミルトンサイクルの内，重みが最小であるものは何個あるか？
重みを答える必要はなくて個数だけでOK．

重みはW，Bをインデックスの小さい順に結んでいく感じになるはず
サンプル３：62208 = 2 ^ 8 * 3 ^ 5

WBWBWB -> 2
あるindexの間の位置は左のWBの差をdとすればmax(1,d)*2回通る？
かっこ列？
WBの差が0の地点で分割する

WWWWWWBBBBBB

W,W,W-W,W,W

1
4
WBBBWWBW

## D
n頂点グラフが存在する（与えられない）
辺重みは全部１
i-j間の最短距離の偶奇の情報が与えられる．
条件を満たすグラフは存在するか？構築も

0 -> inf にしていいはず

## E

長さnの正整数列Aが与えられる
Aを以下の条件を満たすように，複数の連続する部分列に分割する
- ２つ以上に分割
- 分割された各部分列のXOR和がdistinct

n >= 2
全体のXOR和が非零 -> 1つのみとその他
全体のXOR和がゼロ
0以外の要素が2種類あれば構成可能
先頭から見た累積XOR和がゼロでない2種類見付け出して，そこまでを1つ目，2つ目の区間で残りを3つ目にすればいい

## F
n頂点-n頂点の二部グラフが与えられる
3色以下で彩色できないようにするために必要な辺の本数を求めよ
$2 \le n \le 10^4$
$2n-1 \le m \le 200000$

4頂点のクリークを持つ
2~3が答え
https://atcoder.jp/contests/abc260/tasks/abc260_f

## G

## H

## I
行と列が狭義単調増加になるように
1～n+mで空いているマスを埋める方法は何通りか？

基本Aij=i+j

0-indexed
Bij = Aij - i - j - 1
sample 1
00?
?11

## J
順列が与えられる
転倒数が奇数となる最長の(連続とは限らない)部分列の長さを求めよ
(存在しないなら-1)
Q回のswapが行われる
$n,q \le 200000$

-1 : 1 2 3 4 5
全体が奇数: n
1個とると奇数にできる: n - 1
上以外： n - 2
i < j, A_i > A_j　をとりのぞく

答えが n - 2 の場合：
i % 2 == A[i] % 2 \forall i

https://www.spoj.com/problems/SWAPS/
https://codeforces.com/contest/911/problem/D
https://codeforces.com/blog/entry/19551?#comment-243538

## K
以下の操作がm種類あり、長さnの数列に対して何回でも行える
$p_{a_i}>p_{b_i}$ならば、2数を入れ替える
任意の順列を任意の順列に変えることが可能か？
$n,m \le 200000$

SCC で1つの連結成分になる：必要条件

## L
n頂点完全グラフの辺を、すべての長さn-1の連続部分列が木をなすように並びかえよ
$n \le 500$
## M
１～nの順列であって、転倒数が奇数であるような連続部分列をk個持つようなものは存在しますか？あるなら構築せよ
$\sum n^2 \le 4000000$

## N
-2がA個、-1がB個、1がC個、2がD個からなる数列であって、連続部分列の総和が0にならないものの数を求めよ
$A,B,C,D \le 10^6$
累積和がdistinct

2と-2の並びは
2,2,2,2,-2,-2,-2,-2,2,2,2,2
系以外ないはず(適切に正負判定して固定)
1と-1は間に高々1個と、-2がない場合に1を後ろに任意個数、最後の2がない場合に-1を後ろに任意個数

1系は(同符号なら自由、異符号だと連続してるとやばい)、最後逆符号で遡る場合に偶奇を入れ替えたあと、それ以外で最後に1を挿入した箇所まで遡れる

最後の2が無い場合
-2 -2 1 -2 -2 1 -2 -2 1 -2 -2 1
がありえる
2 と -2 の間に 1 or -1 が入る
2の個数 <= -2 の個数
1 or -1 のどちらかが0個の時は
2の個数 < -2 の個数

2, ..., 2, 1 or -1, -2, ..., -2 割と自由 -2, ..., -2, 1 or -1, 2, ..., 2

-2の間において
1の消費に-2が2個必要
選択肢
・-2を2個、1を1個削る
・-1を1個削る
・-2を1個削る
-2を2個と1をまとめる(最後の2にとって-1と同等)

2,2,2,2,2,-2,-2,-2
2,2,2,2,2,2,-2,-2,-2