AtCoder が提供しているABC（AtCoder Beginner Contest）085 D問題をC++で解いてみました。ABC085は、2018年1月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Katana Thrower（Difficulty : 954）
問題の詳細は、リンク先をご覧ください。
与えるダメージが高い刀から使います。AtCoder Problems による Difficulty は 954 でした。
解答案
C++ プログラム例（ABC085D）
振ることで与える最大のダメージを a_max とします。a_max より大きい投げつけるダメージ bi を持つ刀を優先的に使用し、残りの体力に対しては a_max のダメージを用いることで、最小の攻撃回数を求めることができます。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, h;
cin >> n >> h;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
sort(a.begin(), a.end(), greater<int>());
sort(b.begin(), b.end(), greater<int>());
int result = 0;
for (int i = 0; i < n; ++i) {
if (a[0] >= b[i]) {
break;
}
h -= b[i];
++result;
if (h <= 0) {
break;
}
}
if (h > 0) {
result += (h + a[0] - 1) / a[0];
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
貪欲法で解ける問題でした。
引き続き ABC の問題を紹介していきます。
