beet's soil

競プロのことなど

AtCoder Regular Contest 064

出るまではね、、調子いいなとか思ってたんすよ、、
Cを読んで分からなくてD読んで分からなくてEを読んだ。

【E - Cosmic Rays】

おっダイクストラやるだけやんけ->EPSつけ忘れで1WA(TLE)

#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
 
using namespace std;

struct Point{
  double x,y;
  Point(){}
  Point(double x,double y) :x(x),y(y){}
  Point operator + (Point p) {return Point(x+p.x,y+p.y);}
  Point operator - (Point p) {return Point(x-p.x,y-p.y);}
  Point operator * (double k) {return Point(x*k,y*k);}
  Point operator / (double k) {return Point(x/k,y/k);}
  double norm(){return x*x+y*y;}
  double abs(){return sqrt(norm());}

  bool operator < (const Point &p) const{
    return x!=p.x ? x < p.x : y < p.y;
  }

  bool operator == (const Point &p) const{
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

struct Circle{
  Point c;
  double r;
  Circle(){}
  Circle(Point c,double r):c(c),r(r){}
};

double norm(Vector a){
  return a.x*a.x+a.y*a.y;
}
double abs(Vector a){
  return sqrt(norm(a));
}
double getDistanceCC(Circle c1,Circle c2){
  return max(0.0,abs(c1.c-c2.c)-(c1.r+c2.r));
}
double getDistanceCP(Circle c,Point p){
  return max(0.0,abs(c.c-p)-c.r);
}
int main(){
  Point s,t;
  cin>>s.x>>s.y>>t.x>>t.y;
  int n,i,j,k;cin>>n;
  double G[n+2][n+2];
  vector<Circle> vc;
  Circle c;
  for(i=0;i<n;i++){
    cin>>c.c.x>>c.c.y>>c.r;
    vc.push_back(c);
  }
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      G[i][j]=getDistanceCC(vc[i],vc[j]);
  int si=n,ti=n+1;
  for(i=0;i<n;i++){
    G[i][si]=G[si][i]=getDistanceCP(vc[i],s);
    G[i][ti]=G[ti][i]=getDistanceCP(vc[i],t);
  }
  G[si][ti]=G[ti][si]=abs(s-t);
  double dist[n+2],r;
  for(i=0;i<n+2;i++) dist[i]=1e10;
  typedef pair<double,int> P;
  priority_queue<P,vector<P>,greater<P> > q;
  q.push(P(0.0,si));
  while(!q.empty()){
    P p=q.top();q.pop();
    r=p.first;k=p.second;
    //cout << k << ":" << r << endl;
    if(dist[k]<r+EPS) continue;
    dist[k]=r;
    for(i=0;i<n+2;i++){
      if(r+G[k][i]<dist[i]) q.push(P(r+G[k][i],i));
    }
  }
  printf("%.10lf\n",dist[ti]);
  return 0;
}

この時点で解ける問題がなくて絶望していた

【C - Boxes and Candies】

交互にとるべきやろ->自明ケースで落ちる。
気づかなくて50分ぐらい溶かした。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,x,i,j,k,base=0,ans=0;
  ll dp[2]={};
  cin>>n>>x;
  ll a[n+2],b[n+2];
  a[0]=a[n+1]=0;
  for(i=1;i<=n;i++){
    cin>>a[i];
    if(a[i]>x) base+=a[i]-x,a[i]=x;
  }
  for(i=1;i<=n;i++){
    if(!a[i]) ans+=min(dp[0],dp[1]),dp[0]=dp[1]=0;
    else dp[i%2]+=max(0LL,a[i]-min(x-a[i-1],x-a[i+1]));
  }
  ans+=min(dp[0],dp[1]);
  for(i=0;i<=n+1;i++) b[i]=a[i];
  k=0;
  for(i=1;i<=n;i++){
    if(b[i]+b[i+1]>x) j=b[i]+b[i+1]-x,b[i+1]-=j,k+=j;
  }
  ans=min(ans,k);
  for(i=0;i<=n+1;i++) b[i]=a[i];
  k=0;
  for(i=n;i>=1;i--){
    if(b[i]+b[i-1]>x) j=b[i]+b[i-1]-x,b[i-1]-=j,k+=j;
  }
  ans=min(ans,k);
  cout << base+ans << endl;
  return 0;
}

上のDP(DPではない)はいらないらしい。
圧倒的つらみを感じる。

【D - An Ordinary Game】

考えてたけど分からなかった。
解説見て書いたらめっちゃ短くて泣いた。

#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;cin>>s;
  cout << ((s[0]==s[s.size()-1])^s.size()%2?"First":"Second") << endl;
  return 0;
}

天才かなってなった。

結果

1818 -> 1811 (-7)
CEの二完で199位でした。
AOJICPC埋めをやっていたのでもうちょい解けるかなとか思っていたけどそんなことはなかった。
個人的にE<<<