ABC052 D問題（Walk and Teleport）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）052 D問題をC++で解いてみました。ABC052は、2017年1月15日21:00に実施されました。

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

D問題 Walk and Teleport（Difficulty : 1060）

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

ABC052 D問題 Walk and Teleport

歩くかテレポートするか貪欲に選びます。AtCoder Problems による Difficulty は 1060 でした。

解答案

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

西から東に移動します。歩くか、テレポートするか、疲労度が少ない方を選び続けます。

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

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

typedef long long int ll;

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

	ll result = 0;
	for (int i = 0; i < n - 1; ++i) {
		result += min((x[i + 1] - x[i]) * a, b);
	}

	cout << result << endl;

	return 0;
}

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

最後に

典型的な貪欲法を用いる問題でした。

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