Yukicoder029 パワーアップ

問題概要

RPGをする。同じアイテムを2つ揃えるか、別のアイテムを4つ揃えるとパワーアップできる。 アイテムのidが$A[i],B[i],C[i]$と$N$回与えられる。
最大で何回パワーアップするか。

$N\leqq10^2$、$A[i],B[i],C[i]\leqq10$

yukicoder029

解法

一つ残るものは最後までためておいて、最後にまとめてパワーアップに使えば良い。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a(11, 0);
        FOR(i, 0, N) {
            FOR(j, 0, 3) {
                int x; cin >> x;
                a[x]++;
            }
        }
        int left = 0;
        FOR(i, 1, 11) {
            ans += a[i] / 2;
            left += a[i] % 2;
        }
        ans += left / 4;
    
        cout << ans << "\n";
    
        return 0;
    }