けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 053 D - Card Eater (ARC 068 D) (3Q, 緑色, 400 点)

AtCoder AtCoder400点 ABC-D ARC-D NoviSteps3Q 緑色diff 不変量 最適化テク:自明な上界が最適解 最適化問題 最小回数・最小個数を求める 最大スコア 数列 集計処理 操作 切り上げ処理

きちんとした手続きを経て求めたいところ

問題概要

N 個の整数からなる数列 A_{1}, A_{2}, \dots, A_{N} が与えられる。この数列に次の操作を繰り返して、数列の項がすべて相異なるようにしたい。できあがる数列の項数の最大値を求めよ。

【操作】
数列から 3 個の整数を選ぶ。それら 3 個の整数の最小値と最大値を削除して 1 個だけ残す。

制約

  • 3 \le N \le 10^{5}
  • N は奇数

考えたこと

問題の意味を掴むのが大変かもしれない。このようなときは、いろいろ手を動かして実験してみよう。たとえば

  • (3, 3, 3, 3, 3) のように同じ数が 3 個以上あるとき、そこから 3 個を選ぶと、 k 個 → k - 2 個に減らすことができる
  • (2, 2, 3, 3) のように同じ数が 2 個ずつあるとき：そこからどのように 3 個を選んでも、2 個ずつ → 1 個ずつに減らすことができる

といったことが見て取れる。いずれにしても「重複度」的な数量が 2 だけ減少するように思える。

数列の「重複度」を定義する

上の「重複度」という数量を次のように定義しよう。

各整数値 v に対して、数列中に v が K_{v} 個だけあるとき、 K_{v} - 1 の値を足していく。

この値を数列の重複度とよぶことにする。

数列の値がすべて相異なるとき、重複度は 0 である。われわれの目標は、数列の重複度を減らしていき、最終的に 0 にすることである。

ここで、次のことに着目しよう。

  • どのように操作をしても、重複度が 2 以上減ることはない（そもそも数列から 2 個より多くの数を減らさないため）
  • 重複度が 2 以上であるとき、重複度を 2 だけ減らすことができる（重複しているところを狙い撃つようにする）
    • 重複度が 1 であるとき、重複度を 0 にすることができる

これらから、問題は次のようにシンプルなものになる。

「重複度を 2 ずつ減らしていったときに、何回で 0 にできるか」

ここまで来れば簡単な算数である。重複度を求めるのは、ソートや map でできる。計算量は O(N \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    int res = 0;
    for (int i = 0; i+1 < N; i++) if (A[i] == A[i+1]) res++;
    cout << N - (res + 1) / 2 * 2 << endl;
}