Codeforces Round 616

https://codeforces.com/contest/1290 (div1)
https://codeforces.com/contest/1291 (div2)

A. Mind Control
B. Irreducible Anagrams
C. Prefix Enlightenment
D. Coffee Varieties (hard version)
E. Cartesian Tree
F. Making Shapes

A. Mind Control

$k$ 人を固定した場合の自分の値はある区間からひとつ選ばれることになるので，区間 min をいろいろ計算すればよいです．

https://codeforces.com/contest/1290/submission/228100945

B. Irreducible Anagrams

同じ文字を固めた文字列を作ることを考えると，「種類数 $3$ 以上なら Yes」「種類数 $2$ で両端の文字が不一致なら Yes」が言えます．

非自明なのは，種類数 $2$ で両端の文字が一致する場合で，これは Yes であることが示せます．

列 $A, B$ が値 $0, 1$ からなるアナグラムであり， $A_{0} = A_{N - 1} = 1$ だとします． $x_{i} = A_{i} - B_{i}$ として， $x$ の累積和を考えると，両端以外に $0$ になる場所の存在が示せてそこで分割できます．

https://codeforces.com/contest/1290/submission/228100950

C. Prefix Enlightenment

集合を頂点とするグラフを考えます．ちょうど $2$ 個の集合に属する要素は集合の辺と見なせます．特殊な頂点を用意して， $1$ 個の集合に属する要素をそれとつないでおきます．

頂点に操作対象とするか否かで $0$ または $1$ を割り当てると，結局次のような問題になります．

頂点に $0$ または $1$ を割り当てよ．特殊な頂点は $0$ を割り当てなければならない．
辺で結ばれた $2$ 頂点について，和の偶奇の制約がある．

これはポテンシャル付き unionfind の基本問題で，連結成分内では割り当てが高々 $2$ 通りに決まります．

https://codeforces.com/contest/1290/submission/228100960

D. Coffee Varieties (hard version)

難しかった．種類数だけが重要なので，保持しているものと重複していることが分かったら，どれと重複しているかは突き止める必要がないです．

おおよそ次を繰り返すという流れで解けます．

現在保持しているインデックスを適当な順番に並べ列を作る．まずメモリをクリアして，次にその列にしたがってクエリしていく．
クエリで Yes がかえってきたインデックスは破棄，No がかえってきたインデックスのみを保持しなおす．

これを繰り返した結果，どの $2$ つの間も距離 $k$ 以下でクエリされたことがある状態にしたいということになります．

例えば $k / 2$ 頂点のブロックに分けてこれらのブロック間で完全グラフを作り，ハミルトンパスへの分解をとれば，制約のクエリ回数に対して余裕をもって目的を達成できます．

https://codeforces.com/contest/1290/submission/314432988

E. Cartesian Tree

各要素の dfs 順での preorder, postorder を保持することを考えます．すると，これは区間加算と chmin, chmax などで書けます．

要素を activate したり，区間加算，chmin，chmax をしたり，総和をとったりできればよいです．これは segtree beats! で処理できます．

https://codeforces.com/contest/1290/submission/314333808

F. Making Shapes

退化する場合を適切に扱う必要はありますが，本質的には次が重要です．

$(a_{i}, b_{i})$ が $n$ 種類，それぞれたくさんある．
$k_{i}$ 個ずつ選ぶ方法を数えよ． $\sum k_{i} a_{i} = 0$ ， $\sum k_{i} | a_{i} | ≦ m$ , $\sum k_{i} b_{i} = 0$ ， $\sum k_{i} | b_{i} | ≦ m$ という制約がある．

$k_{i}$ についての桁 dp で解けます． $k_{i}$ を偶数個選ぶか奇数個選ぶかを決めます．偶奇に応じてまず $0$ 個や $1$ 個とります．そのあと， $k_{i}$ が全部偶数という前提で残りの問題を解きます．残りの問題はすべてのスケールが半分になり，制約の種類も本問の $| a_{i} |, | b_{i} |$ の上限の制約程度しかないことから計算量が抑えられます．

https://codeforces.com/contest/1290/submission/297094134