AtCoder

ABC053 D問題(Card Eater)を解く

AtCoder_ABC053_D

AtCoder が提供しているABC(AtCoder Beginner Contest)053 D問題をC++で解いてみました。ABC053は、2017年1月28日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Card Eater(Difficulty : 1084)

問題の詳細は、リンク先をご覧ください。

ABC053 D問題 Card Eater

残るカードについての法則に気がつくかがポイントです。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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA