SRM 353 Div2

1000が悲しい
結果
Easy(250) 237.94
Medium(550) 370.94
Hard(950) Failed System Test^^


Easy
全探索

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>

using namespace std;


typedef long long int lli;
typedef unsigned int uint;


class EllipseCoverage {

	public: int calculateCoverage(int x1, int y1, int x2, int y2, int d){
		int res=0;
		for(double x=-500;x<=500;x++){
			for(double y=-500;y<=500;y++){
				res+=(hypot(x1-x,y1-y)+hypot(x2-x,y2-y)<d);
			}
		}
		return res;
	}

};

Medium
結構面倒な実装ゲー

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>

using namespace std;


typedef long long int lli;
typedef unsigned int uint;

void sort(vector<string> &a){
	int swaps=0;
	vector<string> b;
	for(int i=0;i<(int)a.size();i++){
		b.push_back(a[i]);
		for(int j=0;j<(int)b[i].size();j++){
			b[i][j]|=32;
		}
	}
	while(1){
		swaps=0;
		for(int i=0;i<(int)a.size()-1;i++){
			if(b[i]>b[i+1]){
				swap(b[i],b[i+1]);
				swap(a[i],a[i+1]);
				swaps++;
			}
		}

		if(swaps==0)break;
	}
}
string String(int Number,string Character){
	string ret="";
	for(int i=0;i<Number;i++)ret+=Character;
	return ret;
}

class Glossary {

	public: vector<string> buildGlossary(vector<string> items){
		vector<string> item[26];
		for(int i=0;i<(int)items.size();i++){
			item[(items[i][0]|32)-97].push_back(items[i]);
		}

		for(int i=0;i<26;i++)
			sort(item[i]);

		vector<string> l;
		for(int i=0;i<='M'-'A';i++){
			if(item[i].empty())continue;
			string s;
			s+=(char)(i+'A');
			s+="                  ";
			l.push_back(s);
			l.push_back("-------------------");
			for(int j=0;j<(int)item[i].size();j++){
				s="  ";
				s=s+item[i][j];
				s+=String(19-s.size()," ");
				l.push_back(s);
			}
		}
		vector<string> r;
		for(int i='M'-'A'+1;i<26;i++){
			if(item[i].empty())continue;
			string s;
			s+=(char)(i+'A');
			s+="                  ";
			r.push_back(s);
			r.push_back("-------------------");
			for(int j=0;j<(int)item[i].size();j++){
				s="  ";
				s=s+item[i][j];
				s+=String(19-s.size()," ");
				r.push_back(s);
			}
		}
		int m=max(r.size(),l.size());
		vector<string> res;
		for(int i=0;i<m;i++){
			string t="";
			if(l.size()>i){
				t=l[i];
			}else{
				t=String(19," ");
			}
			t=t+"  ";
			if(r.size()>i){
				t+=r[i];
			}else{
				t+=String(19," ");
			}
			res.push_back(t);
		}

		return res;
	}

};

Hard
単純なDPだけど誤差死した。
t=d/Vではなくt=sqrt(2*y/g)を使ったせいで誤差が大きくなった。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>

using namespace std;


typedef long long int lli;
typedef unsigned int uint;

struct Platform{
	int x,y,c;
};
bool operator<(Platform a,Platform b){
	return a.y>b.y;
}
int G,V;
double EPS=1e-8;
bool canmove(int x1,int y1,int x2,int y2){
	int dist=abs(x1-x2);
	int down=y1-y2;
	if(down<0)return false;
	double t=dist/(double)V;
	if(0.5*t*t*G<=down+EPS){
		return true;
	}
	return false;
}
int n;
vector<Platform> p;
int dp[100];
int solve(int s){
	if(s==n)return 0;
	if(dp[s]>=0)return dp[s];
	int res=0;
	for(int i=s+1;i<n;i++){
		if(canmove(p[s].x,p[s].y,p[i].x,p[i].y)){
			res=max(res,solve(i)+p[i].c);
		}
	}
	return dp[s]=res;
}
class PlatformJumper {

	public: int maxCoins(vector<string> platforms, int v, int g){
		p.clear();
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<(int)platforms.size();i++){
			int a,b,c;
			sscanf(platforms[i].c_str(),"%d %d %d",&a,&b,&c);
			Platform t;
			t.x=a;t.y=b;t.c=c;
			p.push_back(t);
		}
		std::stable_sort(p.begin(),p.end());
		G=g;V=v;
		n=p.size();
		int res=0;
		for(int i=0;i<n;i++){
			res=max(p[i].c+solve(i),res);
		}
		return res;
	}
};