Official
B - Old Maid Editorial
by
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:
