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; } };