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

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

AtCoder ABC 378 A - Pairing (6Q, 灰色, 100 点)

これ意外と難しいと思う!

問題概要

4 個の整数  A_{1}, A_{2}, A_{3}, A_{4} (1, 2, 3, 4 のいずれか) が与えられる。これら整数に対して、

「2 個同じ整数があったら 2 個まとめて消す」

という操作を最大で何回できるか?

考えたこと

整理が大変だけど、色んな解法がありそう。

ここでは、4 個の整数は 1, 2, 3, 4 しかありえないことに着目する。各整数が何個ずつあるかを考えれる。

たとえば、同じ数が 2 個あれば 1 回操作できるし、3 個あれば 1 回操作できるし、4 個あれば 2 回操作できる。一般に同じ数が n 個あれば n/2 回操作できる。

このようなことを 1〜4 それぞれについて実行すればよい。

コード

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

int main() {
    int A, n1 = 0, n2 = 0, n3 = 0, n4 = 0;
    for (int i = 0; i < 4; i++) {
        cin >> A;
        if (A == 1) n1++;
        else if (A == 2) n2++;
        else if (A == 3) n3++;
        else n4++;
    }
    
    cout << n1/2 + n2/2 + n3/2 + n4/2 << endl;
}