AtCoder ABC 295 C - Socks (5Q, 灰色, 300 点)

連想配列で集計するといい感じに解ける！

• 問題へのリンク

問題概要

枚の靴下があって、靴下 の色は という整数値で表される。

色の等しい靴下をペアにするとき、最大で何ペア作れるか？

制約

• 
• 

考えたこと

次のように考えたい。

---

• 色ごとに靴下が何個あるかを整理する
• そして、色ごとに、靴下が何ペア作れるかを求める（その色の靴下が 枚のとき n/2 ペア作れる）
• その総和を求めれば良い

---

この作業をするにあたって、連想配列が使える。C++ であれば、map<int, int> 型がピッタリである。

一般に、C++ の map の要素にアクセスするのに要する計算量は であるから、上記の解法の計算量は となる。

コード

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

int main() {
    int N, A;
    cin >> N;
    map<int, int> ma;
    for (int i = 0; i < N; i++) {
        cin >> A;
        ma[A]++;
    }

    int res = 0;
    for (auto [color, num] : ma) res += num / 2;
    cout << res << endl;
}