AtCoder が提供しているABC(AtCoder Beginner Contest)053 D問題をC++で解いてみました。ABC053は、2017年1月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Card Eater(Difficulty : 1084)
問題の詳細は、リンク先をご覧ください。
残るカードについての法則に気がつくかがポイントです。AtCoder Problems による Difficulty は 1084 でした。
解答案
C++ プログラム例(ABC053D)
操作をシミュレーションしては計算量的に間に合いません。
以下の法則があります。
- 同じ整数のカードが3枚以上ある場合、その3枚を選んで操作することにより1枚にすることができます。つまり、同じ整数のカードは、1枚か2枚に減らすことができます。
- 最後に整数Aを1枚、整数Bを2枚を選んで操作して、整数Bを残すことができます。ここで整数Aが2枚あれば、整数Aも整数Bも残り、整数Aが1枚しかなければ整数Aは無くなります。
- 上の考察から、同じ整数が2枚あるカードが偶数個であれば、数字の種類は減ることはなく、2枚あるカードが奇数個であれば、数字の種類が1個減ります。
上記の手順を実装します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
map<int, int> b;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
++b[a];
}
int even = 0;
for (auto e : b) {
if (e.second % 2 == 0) {
++even;
}
}
int result = b.size() - even % 2;
cout << result << endl;
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
最後に
入力例から法則に気が付くことができるかがポイントでした。
引き続き ABC の問題を紹介していきます。