ABC035 C問題（オセロ）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）035 C問題をC++で解いてみました。ABC035は、2016年3月26日21:00に実施されました。

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

C問題 オセロ（Difficulty : 1096（参考値））

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

ABC035 C問題 オセロ

いもす法を使う典型問題です。AtCoder Problems による Difficulty は 1096（参考値）でした。

解答案

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

オセロの駒をひっくり返す範囲を、いもす法を用いて計算します。足し合わせた結果がぐう素であれば黒（0）、奇数であれば白（1）となります。

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

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

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> t(n + 1, 0);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		++t[l - 1];
		--t[r];
	}
	for (int i = 0; i < n; ++i) {
		t[i + 1] += t[i];
	}

	for (int i = 0; i < n; ++i) {
		if (t[i] % 2 == 0) {
			cout << 0;
		} else {
			cout << 1;
		}
	}
	cout << endl;

	return 0;
}

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

最後に

典型問題を紹介しました。

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