result:ooooo---
rateing:1897->1981
紫になりました。
■A. Sorting Parts
最初からソート済みならNO
そうでないならYES
■B. MEX and Array
色々実験をすると
全てバラすのが一番効率がいい。
となるとAi=0の要素のみmexが1になるので計算
■C. Andrew and Stones
両サイドは無視できるとして
実験をすると
x11111xみたいなのは無理
x3xみたいなのも無理。
それ以外は？
全部可能。可能なときの回数は自明
■D. Yet Another Minimization Problem
(x+y)^2=x^2+y^2+2*xyなのでx^2とy^2はどこに振り分けても固定されるので
xyの部分の最小化を考える。
これは簡単なdpでできる
map<ここまで選んだAの総和、その場合の最小値>として持てばいい
Bの総和はAの総和+Bの総和が固定なのでkeyに持つ必要がない
■E. Best Pair
(x+y)*(Cx+Cy)のCx+Cyの部分を固定したい。
なぜなら、Cxの種類はsqrt(n)でなのでCxCyを全探索してもO(n)なため。
雑にやってもO( (n+m)*log(m) )とかで収まるはず。
■F. Towers
ただの木dpやったわ
rootをhiが最大に成るどこかに取る。
こうすると木の部分木とそれ以外のどちらにもhiが含まれるので
dfsの遷移をpair
頂点への遷移だけ少し別処理を行う。
