Official

B - Old Maid Editorial by MMNMM Editorial for printing


この問題は、残っているカードを順に確認して、

  • 同じ整数が書かれているカードがないとき、そのカードは最後まで残ることが確定する。
  • 同じ整数が書かれているカードがあるとき、それらのカード \(2\) 枚を食べる。

という操作を行い、確定したカードの総和を出力することで解くことができます。

実装例は以下のようになります。

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

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

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

    // 残ることが確定したカードの合計
    int answer = 0;
    // 全部確定するまで操作を行う
    while (!A.empty()) {
        int a = A.back();
        A.pop_back();

        bool found = false; // 同じカードがあるか
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == a) { // 同じカードがあったら
                A.erase(begin(A) + i); // A から消す
                found = true;
                break;
            }
        }
        if (!found) { // 同じカードがなければ
            answer += a; // 合計に足す
        }
    }

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

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

# 残ることが確定したカードの合計
answer = 0
# 全部確定するまで操作を行う
while len(A) > 0:
    a = A.pop(0)

    if a in A: # 同じカードがあったら
        A.remove(a) # A から消す
    else: # 同じカードがなければ
        answer += a

print(answer)

別の方法で解くこともできます。

整数 \(x\) が書かれたカードは、最終的に \(1\) 枚残るか \(1\) 枚も残らないかのどちらかです。 操作によって整数 \(x\) が書かれたカードの枚数の偶奇が変化しないので、はじめに \(x\) が書かれたカードが奇数枚あるとき、かつそのときに限り \(x\) のカードが残ります。

よって、奇数枚ある \(x\) の合計を計算することでもこの問題を解くことができます。

実装例は以下のようになります。

#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; // 奇数枚なら A に、偶数枚なら 0 にする
    }

    // 全体の合計を出力
    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 # 奇数枚なら A に、偶数枚なら 0 にする

# 全体の合計を出力
print(sum(parity))

posted:
last update: