競技プログラミング用 知識集積所
ARC206B - Slime Swap
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
大きさをソートできる必要十分条件を考える。
問題の話はバブルソート※に近いことを考えると、同じ色同士で大きさが逆転している個所がないことがその条件となる。
問題の話はバブルソート※に近いことを考えると、同じ色同士で大きさが逆転している個所がないことがその条件となる。
ということは、各色ごとに、その色を最大何体残せるか数えて「それ以外の個体数*元の色番号」を足していけばいい。
最大何体残せるかは、同じ色のスライムだけを見たvectorの最長増加部分列の長さを求めればよい。
そのvector群は、最初にバケツソート※の要領で分類してしまえば高速に作れる。
また、色の変更先は、N体に対してN色使えることから色のダブりがあるなら必ず空き色が存在しているので、それを選べば心配いらない。
そのvector群は、最初にバケツソート※の要領で分類してしまえば高速に作れる。
また、色の変更先は、N体に対してN色使えることから色のダブりがあるなら必ず空き色が存在しているので、それを選べば心配いらない。
解答例
注意点
long long型を使う
解答がint型には収まらないことがある。
