TopCoder SRM 582 Div1
今日はひさしぶりにSRMにでました。
Easyの問題は見るからに二分探索で絶対あってると思って書いた解法がなぜか例3を通してくれず、結果1問もできませんでした。
いや、間違っていたのは非常に単純で、単にソートをするときにStrengthとCountを対応させるのを忘れてただけなんですが。
こんなイージー・ミスをしてついにDiv2に落ちてしまいました。はぁ、なにやってんだろ自分。
気を取り直して、今日も解説行きます。
Easy (250点)
この問題はある星に宇宙生命体が攻めてくるのを魔女たちが倒す最適法を探す問題です。
魔女と宇宙生命体はそれぞれ強さをもっており、
(魔女の強さ) >= (宇宙生命体の強さ)
なら魔女が勝つことができます。
魔女は宇宙生命体を1匹倒すごとに疲れが1たまります。問題は、魔女たちの疲れの最大値が最小になるような倒し方を探して、その時の疲れの最大値を答えるというものです。
解き方はいたって単純で、疲れをHPのようにして考えます。つまり魔女にはあらかじめHPが与えられていて、疲れがそのHP以上になったら戦闘不能になるとします。
そのとき、敵を全員倒すことができるHPの最小値を二分探索で求めれば題意に沿う答えを得ることができます。
以下が正解のコードです。
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, ll> P;
class SpaceWarDiv1 {
public:
bool check(vector<int>& mgStr, vector<P> enemies, ll f) {
int en = enemies.size();
int mgn = mgStr.size();
for(int i=0; i<mgn; i++) {
ll fat = f;
for(int j=0; j<en; j++) {
if(mgStr[i] >= enemies[j].first) {
ll minv = min(fat, enemies[j].second);
fat -= minv;
enemies[j].second -= minv;
} else {
break;
}
if(fat == 0) break;
}
}
ll sum = 0;
for(int j=0; j<en; j++) sum += enemies[j].second;
return sum == 0;
}
long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount) {
vector<P> enemies(enemyStrength.size());
rep(i,enemyStrength.size()) {
enemies[i] = P(enemyStrength[i], enemyCount[i]);
}
sort(magicalGirlStrength.begin(), magicalGirlStrength.end());
sort(enemies.begin(), enemies.end());
ll INF = LLONG_MAX/2;
ll upper = INF;
ll lower = 0LL;
while(upper - lower > 1) {
ll mid = (upper + lower) / 2LL;
if(check(magicalGirlStrength, enemies, mid)) {
upper = mid;
} else {
lower = mid;
}
}
return (upper == INF) ? -1LL : upper;
}
}
まとめ
最近、いろいろ調子悪めです。今日の問題は取らなきゃいけない問題だった。
たぶん、普通に実力出せばDiv1のEasyは十分に解けるだろうと思うのですが・・・
細かい見落としをなくすようにするしかなさそうですね。
1回でDiv1に戻るのはさすがにどうにかなると思いますので、次に期待。