ABC022-B Bumble Beeを解く

今回のエントリーはAtCoder Beginners Contestの過去問を扱います。今回扱うのは第22回のコンテストのB問題です。B問題にしては入力が大きく、計算量を意識するよい練習となります。

問題文

高橋君はマルハナバチ(Bumblebee)という種類のミツバチです。

今日も花の蜜を求めて異なる個の花を訪れました。

高橋君が番目に訪れた花の種類はです。 番目の花は、 かつi番目の花の種類と番目の花の種類が同じになるようなが存在すれば受粉します。

高橋君が訪れた個の花の種類の情報が与えられるので、そのうちいくつの花が受粉したか求めてください。

なお、高橋君以外による受粉や自家受粉を考える必要はありません。

入力
入力は以下の形式で標準入力から与えられる

N
A1
A2
:
AN

• 1行目には高橋君が訪れた花の個数を表す整数が与えられる。
• 2行目からの行のうち行目には番目に高橋君が訪れた花の種類を表す整数が与えられる。

出力
受粉した花の個数を1行で出力せよ。出力の末尾にも改行を入れること。

この問題のリンクは
atcoder.jp

です。

考察

花を表す整数が「1, 2, 3, 2, 1」の場合には、4番目に現れる「2」と5番目に現れる「1」で受粉が起こります。なので、出力は2となります。

戦略1

この実験からすぐ思いつくのは、次のような戦略です。

入力を一つずつ受け取って、その番号がすでに一度でも出ていれば受粉する。これを1つずつ数えていけばよい

入力の個数はなので、入力を一つ一つ受け取るのにに比例した時間がかかります。加えて、入力一つ一つに対して既に出てきているかを調べる必要がありますが、これは最大でのオーダーだとすると、全部でのオーダーとなります。

なのでこれではの時間がかかってしまうので、これでは制限時間に引っ掛かります。つまり、この戦略で行くには、数字がすでに出ているかを調べる操作を以下の時間で済ませる方法を考える必要があります。

戦略2

もう1つ考えられる戦略が、計算をいくつかのパートに分割することです。具体的には、

• 入力値を全部配列に入れる
• 配列をソートする
• それぞれの数字が何回出てきているか数える

という計算に分割します。配列をソートする操作はいろいろあり、ソートのための関数が言語に備え付けられている場合がほとんどです(計算量は速いものは)。ここでのネックはソートした配列にそれぞれの数字が何回出てきているかを調べる部分です。

その前に、「それぞれの数字が何回出てきているか数える」ことでなぜうまくいくか簡単に説明します。例えば、配列に「１」が2回出てきたとします。その時、2つの「１」のうち、片方は最初にもう片方はそのあとに出てきたはずです。後に出てきた「１」では受粉が起こるので、各数字が出てきている回数から1を引いた数をすべての数字に対して足せば、求める答えが出てくるはずです。

数えるのは、配列を最初から1回だけ見ていけばよいので（ソートされているため）、この部分の計算量はで済みそうです。

解答例(C++14)

戦略1

この戦略では、すでに出てきた数字をどのような形で保存するかが重要になります。vectorに入れてしまうと、新しい入力を受け取って、それがすでに出てきたか探索するためにの時間がかかってしまうので、上で述べたように間に合いません。

しかしmapを使えば、探索はなので間に合います。

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n; cin >> n;
	map<int, int> m;
	int res = 0;    // 求める答え

	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (m.find(a) != m.end()) {    // すでに出てきていればresを１増やす
			res++;
		}
		else {
			m[a] = 1;    // まだ出てきていなければmapに加える
		}
	}

	cout << res << endl;
}

戦略2

配列をソートしたあと、ループを回して各数字が何回出てきているか数えてもよいのですが、C++にはuniqueという、配列の重複要素を除いた要素を先頭に集めてくれる便利な関数があるので、これを使います。

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> v;

  for (int i = 0; i < n; i++)
  {
    int a;
    cin >> a;
    v.push_back(a);
  }

  sort(v.begin(), v.end());
  auto it = unique(v.begin(), v.end()); 
  v.erase(it, v.end());    // itから先は一度出た数字が並んでいるので、消去する。

  cout << n - v.size() << endl;
}

解答例(Python 3)

おまけとして、上のそれぞれの解法をPythonで実装したものも載せておきます。

戦略1

n = int(input())
m = dict()

res = 0
for i in range(n):
  a = int(input())
  if (a in m.keys()):
    res += 1
  else:
    m[a] = 1

print(res)

戦略2

n = int(input())
v = []
for i in range(n):
  a = int(input())
  v.append(a)

print(n - len(set(v)))

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド