あうーーーー
ARCはCをぎりぎり通せず165位
SRMはMedを解いたことある問題だったにもかかわらず落として1110->1096
深夜から明けて結果みると眠さなどもろもろの条件が重なっていまとってもイライラ
ARC #4
A
全二点対の距離を全探査するだけ
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; int n; int x[100], y[100]; double calc(int i, int j) { return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j])); } int main() { scanf("%d",&n); for (int i=0; i<n; i++) { scanf("%d%d",&x[i],&y[i]); } double ans=0.0; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { ans=max(ans, calc(i,j)); } } printf("%.10f\n",ans); }
B
手こずらされた
ようするに長辺よりも他の辺のながさの合計が長いならば多角形がつくれて最短距離0、そうでなければ長辺-他の辺の長さの合計が最短距離になるということでいいらしい
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; int n, a1, a2, m; int d[500]; int main() { scanf("%d",&n); a1=0; m=0; for (int i=0; i<n; i++) { scanf("%d",&d[i]); a1+=d[i]; m=max(m, d[i]); } if (n==1) a2=a1; else if (n==2) { a2=abs(d[1]-d[0]); } else if (n==3) { if (d[0]+d[1]>=d[2]&&d[0]+d[2]>=d[1]&&d[1]+d[2]>=d[0]) { a2=0; } else { a2=m*2-d[0]-d[1]-d[2]; } } else { if (m*2-a1<0) a2=0; else a2=m*2-a1; } printf("%d\n%d\n",a1,a2); }
C
問題自体は簡単で1〜nまでの連続した数の平均で一つ忘れたというのは分母が必ずnになっていて、そのnから1〜nまでの合計は求められるから逆算すれば忘れた数も求められる。だからX/Yの分母分子に同じ数をかけて、求められた忘れた数が1以上になるところからnより大きくなる直前までを列挙していけばいいのだけれども普通に同じ数ってのを1から始めるとTLEになるケースがある。
だからここで数学の登場、とりあえずとある大学生に教えてもらったのは
x/y=(n+1)/2-m/2nで0
#include <cstdio> #include <map> #include <vector> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll, ll> P; ll x, y; vector<P> ans; ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); } int main() { scanf("%lld/%lld",&x,&y); ll g=gcd(x,y); x/=g; y/=g; int t=2*x/y/y; while (true) { ll X=x*t, Y=y*t; ll sum=Y*(Y+1)/2; if (sum-X>Y) break; if (sum-X>0) ans.push_back(P(Y,sum-X)); t++; } if (ans.size()==0) { puts("Impossible"); } else { for (int i=0; i<ans.size(); i++) { printf("%lld %lld\n",ans[i].first,ans[i].second); } } }
SRM445
TheNewHouseDivOne
問題文が正しく解釈できること
k番目に近い距離の最短を求めるので古い家の座標が整数値だからその距離はn.5またはm.0という数字にしかなりえないこと
範囲が狭いこと
に留意できれば簡単な問題なのだけれどもさすがにそんなの思いつけない
class TheNewHouseDivOne { public: double distance( vector <int> x, vector <int> y, int k ) { int sz=x.size(); double res=1000.0; double dist[sz]; for (double a=-51.0; a<=51.0; a+=0.5) { for (double b=-51.0; b<=51.0; b+=0.5) { for (int i=0; i<sz; i++) { dist[i]=abs(x[i]-a)+abs(y[i]-b); } sort(dist, dist+sz); res=min(res, dist[k-1]); } } return res; } };
SRM546
ContestWinner
やるだけ
class ContestWinner { public: int getWinner( vector <int> events ) { int res=0, p=0, sz=events.size(); mp cnt; for (int i=0; i<sz; i++) { if (cnt.find(events[i])!=cnt.end()) { cnt[events[i]]++; if (cnt[events[i]]>p) { res=events[i]; p=cnt[events[i]]; } } else { cnt[events[i]]=1; if (1>p) { res=events[i]; p=1; } } } return res; } };
TwoRectangles
二つの四角形の左下と右上の座標があたえられるから交差をどのようにしているか判定するというどっかで見たような問題
前もやったはずなのに忘れてたので再確認します。
まず交差しているとしたら点でも線でも四角形でもそこを四角形と考えるとその四角形の左下の座標は二つの四角形の左下の座標x,y成分ごとに大きい方をあつめた座標、右上はその真逆
これで交差している部分の左下と右上の座標が求まるんだからあとはそれが四角形か線か点かなんでもないのかを判定する
class TwoRectangles { public: string describeIntersection( vector <int> A, vector <int> B ) { int lx=max(A[0],B[0]); int ly=max(A[1],B[1]); int rx=min(A[2],B[2]); int ry=min(A[3],B[3]); if (lx==rx&&ly==ry) return "point"; if (lx<rx&&ly<ry) return "rectangle"; if (lx>rx||ly>ry) return "none"; return "segment"; } };
おわりに
もうやだ…(´Д`)ハァ…