ACPC_VC_20200106_DIV1

あけましておめでとうございます

リンク

not-522.appspot.com

Addition and Subtraction Hard

先頭に+を足しておく
dpi,j:=$d{p}_{i,j}:=$ i$i$番目までの項を見て-の前で j$j$回かっこを開いたときの最大値とする
明らかに i$i$側を削るのは無理　遷移をグッと睨むと j$j$は3以上いらなさそう→いりません

K-th K

a$a$ に含まれる整数 i$i$ のうち左から i$i$ 番目に位置するものは、 a$a$ 全体では左から xi$x_i$ 番目に位置する。
⇒ xi$x_i$ 以前に ちょうど i−1$i-1$個の i$i$ が置かれていなければならない
で、これは区間スケジューリングっぽく貪欲におくべき

Tournament

二つの列 A,B$A,B$に対し、それを並び替えて maxi(Ai+Bi)$\underset{i}{max}(A_i+B_i)$ を最小化せよという問題に帰着される
結論から言うと、片方を昇順、もう片方を降順にソートするのが最適（なものの一つ）

理由
選択肢が有限通りしかなく上に有界なので最適解が存在する。
Ai<Aj$A_i<A_j$ かつ Bi<Bj$B_i<B_j$であるような i,j$i,j$ が存在するなら、片方をswapしてもコストは増えない。

感想

うん