C問題までが15分で終わって1時間以上あったのに解けなかった。
愚直法
「人数が多い順に部署をソートし、1番目からK番目の部署から1人ずつ連れてきて1チーム作る。これをK番目に多い部署の人数が0になるまで繰り返す。」
O(N^2 logN max(A))なのでACはとれない。加速する必要がある。
貪欲法 → ×
「人数が多い順に部署をソートし、K番目に多い部署の人数をnとする。1番目からK番目の部署からn人ずつ連れてきてnチーム作る。これをK番目に多い部署の人数が0になるまで繰り返す」
これでサンプルは通るが嘘解法。
例えば部署の人数がa:4, b:4, c:4で2人で1チームを作るとき、嘘解放だとab×4を作ったところで停止するが、実際にはab×2, ac×2, bc×2の計6チーム作れる。
また、ソートのたびにO(N logN)の時間計算量を要するので、全部でO(N^2 logN)でTLEでもある。
最大フロー??
例えば部署の人数がa:4, b:4, c:4で2人で1チームを作るとき、まずabを4チーム作っておいて、そのうち2チームを解散してca×2とcb×2を作れば6チームできる。最大フローっぽい手順であり、ACの人数が異様に少ないのもあり、もしやこれでは??と迷ったが、K人で1チームを作るグラフは出来そうにない。(K=2なら最大フロー問題には出来そうだが張る辺がN^2オーダーになる)
逆問題
ところで、この問題はO(N logN)くらいでないと間に合わない。O(N)のアルゴリズムをlogN回繰り返すものの代表格といえば、やはり二分探索法であろう。何とか解きやすい逆問題を設定できないか。
元の問題が「最大でいくつ作れますか？」なのでこちらを固定する。
Mチーム作ることにする。チーム分けの表を用意する。5チームに分けるなら以下のようになる。
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| □ | □ | □ | □ | □ |
| □ | □ | □ | □ | □ |
| □ | □ | □ | □ | □ |
| … | … | … | … | … |
これにa:4, b:4, c:4を順に並べてみる↓
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| a | a | a | a | b |
| b | b | b | c | c |
| c | c | □ | □ | □ |
| … | … | … | … | … |
これ↑が何を意味するかというと、「5チーム作るなら1チーム2人以下なら可能」ということ。
チームの人数を4人にしてみる↓
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| a | a | a | a |
| b | b | b | b |
| c | c | c | c |
| … | … | … | … |
↑「4チーム作るなら1チーム3人以下なら可能」
チームの人数を3人にしてみる↓
| 1 | 2 | 3 |
|---|---|---|
| a | a | a |
| a | b | b |
| b | b | c |
| c | c | c |
| … | … | … |
…「3チーム作るなら1チーム4人以下なら可能」かというとそうではない。部署の人数がチームの数を超えたために2週目に入ってしまい、1チームに同じ部署から複数人が含まれる事態になった。これを避けるには「1部署あたりの参加人数」を「チームの数」以下に制限する必要がある。今なら３人以下。
| 1 | 2 | 3 |
|---|---|---|
| a | a | a |
| b | b | b |
| c | c | c |
| … | … | … |
↑「3チーム作るなら1チーム3人以下なら可能」
チーム数をMとしたときの参加人数は全部で $\Sigma_{i=1}^N min(A_i, M)$ なので、
1チームあたりの人数は$\Sigma_{i=1}^N min(A_i, M) / M$以下なら可能ということになる。これはO(N)で計算できる。
あとはチーム数Mを色々変えて、1チームあたりの人数がK人以上とすることが可能なMの上限値を求めればよい。
AC解法
use proconio::input;
fn main() {
input!{
n: usize, k: i64,
a: [i64; n],
}
let mut l = 0;
let mut r = 200_000 * 1_000_000_000_000 + 1;
while r-l > 1 {
let m = (l+r) / 2;
let sum: i64 = a.iter().map(|x| x.min(&m)).sum();
if sum / m >= k {
l = m;
} else {
r = m;
}
}
let ans = l;
println!("{}", ans);
}
分かってしまえば呆気ない。本番中に解けたかった。