AtCoder

ABC024 C問題(民族大移動)を解く

AtCoder_ABC024_C

AtCoder が提供しているABC(AtCoder Beginner Contest)024 C問題をC++で解いてみました。ABC024は、2015年5月23日21:00に実施されました。

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

C問題 民族大移動(Difficulty : 1007(参考値))

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

ABC024 C問題 民族大移動

民族を固定して、可能な限りゴール方向に街を移動します。AtCoder Problems による Difficulty は 1007(参考値)でした。

解答案

C++ プログラム例(ABC024C)

この問題は貪欲法で解くことができます。特定の民族に注目し、スタート地点からゴール地点まで、現在の位置(now)を可能な限りゴール方向に動かします。

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

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

int main()
{
	int n, d, k;
	cin >> n >> d >> k;
	vector<int> L(d), R(d);
	for (int i = 0; i < d; ++i) {
		cin >> L[i] >> R[i];
	}

	for (int i = 0; i < k; ++i) {
		int s, t;
		cin >> s >> t;
		int now = s;
		for (int day = 0; day < d; ++day) {
			if ((L[day] <= now) && (now <= R[day])) {
				if ((L[day] <= t) && (t <= R[day])) {
					cout << day + 1 << endl;
					break;
				} else if (t < L[day]) {
					now = L[day];
				} else if (R[day] < t) {
					now = R[day];
				}
			}
		}
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

貪欲法で解けることに気付くことがポイントでした。

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

COMMENT

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

CAPTCHA