AtCoder が提供しているABC(AtCoder Beginner Contest)024 C問題をC++で解いてみました。ABC024は、2015年5月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 民族大移動(Difficulty : 1007(参考値))
問題の詳細は、リンク先をご覧ください。
民族を固定して、可能な限りゴール方向に街を移動します。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 の問題を紹介していきます。