AtCoder が提供しているABC（AtCoder Beginner Contest）017 C問題をC++で解いてみました。ABC017は、2015年1月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 ハイスコア（Difficulty : 1607（参考値））
問題の詳細は、リンク先をご覧ください。
部分点が設定されている問題です。AtCoder Problems による Difficulty は 1607（参考値）でした。
解答案
この問題には3段階の点数が設定されています。
- $N \leqq 8$ かつ $M \leqq 8$ を満たすデータセットに正解した場合は、30点
- $N \leqq 5000$ かつ $M \leqq 5000$ を満たすデータセットに正解した場合は、70点
- $N \leqq 100,000$ かつ $M \leqq 100,000$ を満たすデータセットに正解した場合は、1点
部分点の設定により、得点は30点、100点、101点となります。
$N \leq 8$ かつ $M \leq 8$ のデータセットでは、最大で $2^8$ 通りの遺跡の選択肢があり、これをbit全探索で全て試すことで得点の最大値を求めることができます。
C++ プログラム例（ABC017C）
100点解法（30点＋70点）
$M$ 種類の宝石のうち、各宝石を1つずつ選び、その宝石を取らない（その宝石を得られる遺跡を選ばない）場合の得点の最大値を求めます（20～29行目）。計算量は、$O(M N) = 2.5 \times 10^7$ となり、制限時間内に収まります。
$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 の問題を紹介していきます。
