CS Academy Round #79 - Groups

• 問題

計算量の説明がどこにも書かれていなくて困った。以下は自分の理解。

$i$番目のクエリで与えられる$P_i$人の人間について、代表者の人数を$x_i$、代表者以外の人数を$y_i$とする。$x_i$個のグループそれぞれについて、走査して離脱しないメンバーが見つかったら打ち切るのが想定解らしい。$D=10^5$として1つのクエリで調べるノード数は最大で$\min(x_iy_i, D)$なので、計算量は$\sum_{i=1}^Q \min(x_iy_i, D)$と書ける。これを評価したい。

まず、$\sum_{i=1}^Q P_i = \sum_{i=1}^Q (x_i + y_i) \le D$という制約がある。$x_i + y_i$が一定のとき$x_iy_i$は$x_i = y_i$で最大値を取るので、$\sum_{i=1}^Q x_i \le D/2$という条件下で$\sum_{i=1}^Q \min(x_i^2, D)$を評価する問題ということにいなる。面倒なので、代わりに$\sum_{i=1}^Q x_i \le D$としておく。

$x_i + x_j$が一定のとき、$x_i^2 + x_j^2$は$x_j=0$で最大になる^[1]ので、$\sum_{i=1}^Q x_i^2$を大きくするには値をできるだけ偏らせるのが最善である。ただし、1つの変数を$\sqrt D$より大きくしても意味がないので、最大値を取る配分の一つは$(x_1, x_2, ..., x_Q) = (\sqrt D, ..., \sqrt D, 0, ..., 0)$という形になる。$\sum_{i=1}^Q x_i \le D$より、最大で$\sqrt D$個程度の$x_i$を$\sqrt D$にできるから、このとき$\sum_{i=1}^Q \min(x_i^2, D) = D\sqrt D$と見積もれる。

---

1. 平面上で、原点を中心とするマンハッタン距離に関する円と、ユークリッド距離に関する円を思い浮かべればよい。 ↩︎