ABC 401-500/ABC424E - Cut in Half - 競技プログラミング用 知識集積所

---

問題

ABC424E

必要知識

B以下レベルの内容は省略

• 特になし

考え方

なんとびっくり、ほぼほぼ愚直解で間に合う。
強いて言えば、同じ長さの棒が大量発生するので、ランレングス圧縮※っぽく管理する必要があるくらい。

priority_queue※を使って、{長さ,個数}の形で長い順に取り出して半分にして戻す、をk個分切るまで繰り返す。
その後、同じように長い方からx-1個を捨てて、残りの中で最長のものを答えればよい。

「最長を取り出して、まとめて半分にして、戻す」をN回やると、棒の本数は少なくとも2倍以上になる。
つまり、取り出し回数はO(N*logk)で済む。
1回あたりの処理がO(logN)なので、全体でO(N*logN*logk)で済み、間に合う。

解答例

解答例

注意点

別解