AtCoder

ABC017 C問題(ハイスコア)を解く

AtCoder_ABC017_C

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

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

C問題 ハイスコア(Difficulty : 1607(参考値))

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

ABC017 C問題 ハイスコア

部分点が設定されている問題です。AtCoder Problems による Difficulty は 1607(参考値)でした。

解答案

この問題には3段階の点数が設定されています。

  • N8 かつ M8 を満たすデータセットに正解した場合は、30点
  • N5000 かつ M5000 を満たすデータセットに正解した場合は、70点
  • N100,000 かつ M100,000 を満たすデータセットに正解した場合は、1点

部分点の設定により、得点は30点、100点、101点となります。

N8 かつ M8 のデータセットでは、最大で 28 通りの遺跡の選択肢があり、これをbit全探索で全て試すことで得点の最大値を求めることができます。

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

100点解法(30点+70点)

M 種類の宝石のうち、各宝石を1つずつ選び、その宝石を取らない(その宝石を得られる遺跡を選ばない)場合の得点の最大値を求めます(20~29行目)。計算量は、O(MN)=2.5×107 となり、制限時間内に収まります。

N>5000 または M>5000 の場合は、時間切れになる可能性があります。採点サーバへの負荷を避けるために -1 を出力して終了します(15~18行目)。

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

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

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

	if ((n > 5000) || (m > 5000)) {
		cout << -1 << endl;
		return 0;
	}

	int result = 0;
	for (int i = 0; i < m; ++i) {
		int t_result = 0;
		for (int j = 0; j < n; ++j) {
			if ((i < L[j]) || (R[j] < i)) {
				t_result += s[j];
			}
		}
		result = max(result, t_result);
	}

	cout << result << endl;

	return 0;
}

満点(101点)解法

いもす法ですべての遺跡を処理して、それぞれの宝石の番号に対して得点を求めます。総得点から一番低い得点を引けば、得点の最大値を求めることができます。

この前後の問題は、いもす法が使える問題が多い印象です。

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> L(n), R(n), s(n);
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> L[i] >> R[i] >> s[i];
		--L[i];
		--R[i];
		sum += s[i];
	}

	vector<int> t(m + 1, 0);
	for (int i = 0; i < n; ++i) {
		t[L[i]] += s[i];
		t[R[i] + 1] -= s[i];
	}
	for (int i = 0; i < m; ++i) {
		t[i + 1] += t[i];
	}

	int result = 0;
	for (int i = 0; i < m; ++i) {
		result = max(result, sum - t[i]);
	}

	cout << result << endl;

	return 0;
}

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

最後に

この時期には、部分点が設定されている問題が比較的多く見られました。現在のコンテストに部分点の制度が復活すれば、より楽しめると考えています。

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

COMMENT

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

CAPTCHA