ABC014 C問題（AtColor）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）014 C問題をC++で解いてみました。ABC014は、2014年9月13日21:00に実施されました。

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

C問題 AtColor（Difficulty : 1276（参考値））

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

ABC014 C問題 AtColor

いもす法で解ける典型問題です。AtCoder Problems による Difficulty は 1276（参考値）でした。

解答案

入力例1では、4つの閉区間が指定されています。[0, 2]、[2, 3]、[2, 4]、[5, 6] です。これを半開区間に書き換えます。つまり [0, 3)、[2, 4)、[2. 5)、[5, 7) と考えます。

半開区間の開始位置で +1、終了位置で -1 を加えます。最初の区間[0, 3) の処理をしましょう。

次の区間 [2, 4) も同じように処理します。

残りの [2, 5) と [5, 7) も同じように処理します。色5は -1 されて +1 されるため 0 となります。

この処理では、前の値との差を記しています。累積和を計算すると、購入を希望している消費者の人数が分かります。累積和は以下となります。

結果として、色2を3人が購入希望していることが判明します。

C++ プログラム例（ABC014C）

上記の処理（考え方）を「いもす法」と呼びます。提唱者の名前のようです。

13から20行目でいもす法を用いて処理を行っています。この結果、配列 color に購入を希望している人数が格納されています。配列 color の最大値が求める解となります（22ー29行目）。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}

	vector<int> color(1000000 + 2, 0);
	for (int i = 0; i < n; ++i) {
		++color[a[i]];
		--color[b[i] + 1];
	}
	for (int i = 0; i < (int)color.size() - 1; ++i) {
		color[i + 1] += color[i];
	}

	int color_max = 0;
	for (int i = 0; i < (int)color.size(); ++i) {
		if (color[i] > color_max) {
			color_max = color[i];
		}
	}

	cout << color_max << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

いもす法を使う典型的な問題です。このころのABCは、現在よりも典型的な問題が多く出題されていると感じます。

引き続き ABC の問題を紹介していきます。