公式

B - Old Maid 解説 by en_translator


This problem can be solved by the following procedure: inspect the card one by one,

  • if there is no card with the same integer written on it, confirm that the card is never eaten;
  • if there is a card with the same integer written on it, eat those two cards.

Finally, print the sum of the integers written on the confirmed card.

The following is sample code.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    for (int& a : A) {
        cin >> a;
    }

    // The sum for the confirmed cards 
    int answer = 0;
    // Repeat until everything is confirmed
    while (!A.empty()) {
        int a = A.back();
        A.pop_back();

        bool found = false; // The same card found?
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == a) { // If there is the same card,
                A.erase(begin(A) + i); // erase from A
                found = true;
                break;
            }
        }
        if (!found) { // If there is no same card,
            answer += a; // add to the sum
        }
    }

    cout << answer << endl;
    return 0;
}
N = int(input())

A = list(map(int, input().split()))

# The sum for the confirmed cards
answer = 0
# Repeat until everything is confirmed
while len(A) > 0:
    a = A.pop(0)

    if a in A: # If there is the same card,
        A.remove(a) # erase from A
    else: # If there is no same card,
        answer += a

print(answer)

There is an alternative way to solve it.

For the cards with an integer \(x\) written on them, there will be either one or zero of them in the final state. Since the operation does not change the parity of the number of cards with \(x\) written, so the card with \(x\) will remain if and only if there is and odd number of cards with \(x\) initially.

Hence, the problem can be solved by finding the sum of \(x\) with odd number of cards.

The following is sample code.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> parity(101);
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        parity[A] ^= A; // Makes it A if there are odd number of them, and 0 if even
    }

    // Print the sum
    cout << ranges::fold_left(parity, 0, plus{}) << endl;
}
N = int(input())

parity = [0 for i in range(101)]
for A in map(int, input().split()):
    parity[A] ^= A # Makes it A if there are odd number of them, and 0 if even

# Print the sum
print(sum(parity))