JOI Kakisemi Contest 2019：D - ふたつのケーキ

S 人の人と 2 種類のケーキがある．イチゴケーキは N 個に分かれていて，ショートケーキ M 個に分かれている．イチゴケーキに関しては， S 人に分ける個数が決まっている．ここで，各人について，2 種類のケーキを取る個数の差の 2 乗の和を最小化する問題．

S = 2 より人は 2 人しかない．よって，イチゴケーキを分ける境目の個数の近くの切れ目 2 通りを試せばよい．(x / N) >= (y / M) の一次不等式を解けば四則演算のみで解ける．

N, M <= 50 より DP を考える．

dp[何人目まで配分を決めたか][ショートケーキを既に配分した個数] とおくと，O(S * M^2) となる．高速化すると O(SM) などにすることができるが，後の小課題にはつながらない．

各人について誤差の 2 乗は x 軸を N, y 軸を M とする二次元平面状で下に凸の放物線になる．この放物線の傾きは単調増加なので priority_queue などで O(MlogS) で求められる．

ギリギリ (B_i / M) <= (A_i / N) であるような B_i を求めればよい．これは誤差をソートして計算すればよく，小課題３より O(SlogS)．

また，微分係数を二分探索しても解くことができる．

きろく