beet's soil

競プロのことなど

World CodeSprint 9

$75なんてなかった

【Grading Students】

やる。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int g;
    cin>>g;
    if(g<38){
      cout<<g<<endl;
      continue;
    }
    if(g%5>2){
      cout<<g+5-g%5<<endl;
      continue;
    }
    cout<<g<<endl;
  }
  return 0;
}
【Weighted Uniform Strings】

最初に全部setにぶち込んではい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  set<int> ss;
  for(int i=0;i<(int)s.size();i++){
    int t=0,c=s[i]-'a'+1;
    t+=c;
    //cout<<t<<endl;
    ss.insert(t);
    while(i+1<(int)s.size()&&s[i]==s[i+1]){
      t+=c;
      //cout<<t<<endl;
      ss.insert(t);
      i++;
    }
  }
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int q;
    cin>>q;
    cout<<(ss.count(q)?"Yes":"No")<<endl;
  }
  return 0;
}
Queen's Attack II】

番兵置いて4方向見てえい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct xy{
  int x,y;
  xy(){}
  xy(int x,int y):x(x),y(y){}
  bool operator<(const xy& a) const{
    if(x==a.x) return y<a.y;
    return x<a.x;
  }
};
int main(){
  int n,k;
  cin>>n>>k;
  xy b;
  cin>>b.x>>b.y;
  vector<xy> v[4];
  for(int i=0;i<k;i++){
    xy o;
    cin>>o.x>>o.y;
    if(o.x==b.x) v[0].push_back(o);
    if(o.y==b.y) v[1].push_back(o);
    if(o.x+o.y==b.x+b.y) v[2].push_back(o);
    if(o.x-o.y==b.x-b.y) v[3].push_back(o);
  }
  v[0].push_back(xy(b.x,0));
  v[0].push_back(xy(b.x,n+1));
  v[1].push_back(xy(0,b.y));
  v[1].push_back(xy(n+1,b.y));
  v[2].push_back(xy(b.x+b.y,0));
  v[2].push_back(xy(0,b.x+b.y));
  v[2].push_back(xy(b.x+b.y-(n+1),n+1));
  v[2].push_back(xy(n+1,b.x+b.y-(n+1)));
  v[3].push_back(xy(0,-(b.x-b.y)));
  v[3].push_back(xy(b.x-b.y,0));
  v[3].push_back(xy((b.x-b.y)+(n+1),n+1));
  v[3].push_back(xy(n+1,(n+1)-(b.x-b.y)));
  
  int ans=0;
  for(int i=0;i<4;i++){
    sort(v[i].begin(),v[i].end());
    xy s=v[i][0],t=v[i][v[i].size()-1];
    for(int j=0;j<(int)v[i].size();j++){
      if(i){
	if(v[i][j].x<b.x){
	  if(abs(v[i][j].x-b.x)<abs(s.x-b.x)) s=v[i][j];
	}else{
	  if(abs(v[i][j].x-b.x)<abs(t.x-b.x)) t=v[i][j];
	}
      }else{
	if(v[i][j].y<b.y){
	  if(abs(v[i][j].y-b.y)<abs(s.y-b.y)) s=v[i][j];
	}else{
	  if(abs(v[i][j].y-b.y)<abs(t.y-b.y)) t=v[i][j];
	}
      }
    }
    //cout<<t.x<<" "<<t.y<<":"<<s.x<<" "<<s.y<<"/"<<t.x-1-s.x-1<<" "<<t.y-1-s.y-1<<endl;
    if(i) ans+=t.x-1-s.x-1;
    else ans+=t.y-1-s.y-1;
  }
  cout<<ans<<endl;
  return 0;
}
【Kingdom Division】

dp[位置][色][連結かどうか]で木DPした。
適当に遷移書いたら通っちゃってびっくりした。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> G[114514];
ll dp[114514][2][2];
ll MOD=1000000007LL;
ll dfs(ll v,ll p){
  bool f=0;
  dp[v][0][1]=dp[v][1][1]=1;
  for(ll i=0;i<(ll)G[v].size();i++){
    if(G[v][i]==p) continue;
    dfs(G[v][i],v);
    (dp[v][0][1]*=dp[G[v][i]][1][0])%=MOD;
    (dp[v][1][1]*=dp[G[v][i]][0][0])%=MOD;
    
    if(!f) dp[v][0][0]=dp[v][1][0]=f=1;
    
    (dp[v][0][0]*=(dp[G[v][i]][0][0]+dp[G[v][i]][1][0]+dp[G[v][i]][0][1])%MOD)%=MOD;
    (dp[v][1][0]*=(dp[G[v][i]][0][0]+dp[G[v][i]][1][0]+dp[G[v][i]][1][1])%MOD)%=MOD;
  }
  if(f){
    (dp[v][0][0]+=MOD-dp[v][0][1])%=MOD;
    (dp[v][1][0]+=MOD-dp[v][1][1])%=MOD;
  }
  /*//
  cout<<v<<":"<<endl;
  cout<<dp[v][0][0]<<endl;
  cout<<dp[v][1][0]<<endl;
  cout<<dp[v][0][1]<<endl;
  cout<<dp[v][1][1]<<endl;
  //*/
  return (dp[v][0][0]+dp[v][1][0])%MOD;
}
int main(){
  memset(dp,0,sizeof(dp));
  ll n;
  cin>>n;
  for(ll i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cout<<dfs(0,-1)<<endl;
  return 0;
}
【Toll Cost Digits】

往復でコストが変わらないのと下一桁以外関係ないのがポイント。
下一桁を0-9にできるかみたいなのを幅優先して数えて、
それぞれの頂点について自分の分を除いて、始点からの差分をずらすとできる。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
bool us[114514][10];
vector<P> G[114514];
int main(){
  ll ans[10]={};
  ll n,e;
  cin>>n>>e;
  for(ll i=0;i<e;i++){
    ll x,y,r;
    cin>>x>>y>>r;
    x--;y--;
    G[x].push_back(P(y,r%10));
    G[y].push_back(P(x,(1000-r)%10));
  }
  for(ll i=0;i<n;i++){
    ll f=0;
    for(ll j=0;j<10;j++) f|=us[i][j];
    if(f) continue;
    ll tmp[10]={};
    set<ll> s;
    queue<P> q;
    q.push(P(i,0));
    while(!q.empty()){
      P p=q.front();q.pop();
      ll v=p.first,d=p.second;
      if(us[v][d]) continue;
      s.insert(v);
      us[v][d]=1;
      tmp[d]++;
      for(ll j=0;j<(ll)G[v].size();j++){
	ll u=G[v][j].first,nd=(d+G[v][j].second)%10;
	if(!us[u][nd]) q.push(P(u,nd));
      }
    }
    for(auto j:s){
      for(ll k=0;k<10;k++) tmp[k]-=us[j][k];
      for(ll k=0;k<10;k++){
	if(us[j][k]){
	  for(ll l=0;l<10;l++){
	    ans[(l+10-k)%10]+=tmp[l];
	  }
	  break;
	}
      }
      for(ll k=0;k<10;k++) tmp[k]+=us[j][k];
    }
  }
  
  for(ll i=0;i<10;i++) cout<<ans[i]<<endl;
  return 0;
}
【Two Subarrays】

20%+嘘で50%
始点決めてぶん回すのを時間ギリギリまでやった。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 42
int main(){
  ll n;
  cin>>n;
  ll a[n],s[n+1];
  s[0]=0;
  for(ll i=0;i<n;i++){
    cin>>a[i];
    s[i+1]=s[i]+a[i];
  }
  time_t start=clock();
  bool us[n];
  memset(us,0,sizeof(us));
  ll ans=0,len=n,cnt=0;

  for(ll i=0;i<n;i++){
    ll tmp=0;
    ll dp[MAX]={};
    us[i]=1;
    if(a[i]<=0) continue;
    for(ll j=i;j<n;j++){
      if(a[j]<=0) continue;
      for(int k=0;k<a[j];k++)
	dp[a[j]]=max(dp[a[j]],dp[k]+a[j]);
      tmp=max(tmp,dp[a[j]]);
      ll su=s[j+1]-s[i]-tmp;
      if(ans>su) continue;
      if(ans<su) ans=su,len=j-i+1,cnt=0;
      if(j-i+1<len) len=j-i+1,cnt=0;
      if(j-i+1==len) cnt++;
    }
    if((double)(clock()-start)/CLOCKS_PER_SEC>1.9) break;
  }
  if(ans) cout<<ans<<" "<<cnt<<endl;
  else cout<<0<<" "<<n<<endl;
  return 0;
}
【The Optimal Polygon (Approximate)】

乱択で9%
頑張った割に伸びなくて悲しかった。
(幾何ライブラリは省略)

struct PP{
  Point p;
  int x;
  PP(){}
  PP(Point p,int x):p(p),x(x){}
};
  
Point c=Point(0,0);
bool mysort2(const PP& pp1,const PP &pp2){
  Point p1=pp1.p,p2=pp2.p;
  Vector v1=p1-c,v2=p2-c;
  return atan2(v1.y,v1.x)<atan2(v2.y,v2.x);
}

double getAngle(){
  double res=rand()%180-90;
  return res;
}

int n;
double PI=3.141592653589793238;


double subp(vector<PP>&tmp){
  Polygon con,an;
  for(int i=0;i<n;i++) con.push_back(tmp[i].p);
  an=andrewScan(con);
  c=Point(0,0);
  for(int j=0;j<(int)an.size();j++){
    c=c+an[j];
  }
  c=c/(double)an.size();
  sort(tmp.begin(),tmp.end(),mysort2);
  con.clear();
  for(int i=0;i<n;i++) con.push_back(tmp[i].p);
  double len2=0;
  for(int j=0;j<n;j++) len2+=abs(tmp[j].p-tmp[(j+1)%n].p);
  double area2=area(con);
  return len2*len2/area2;
}

struct st{
  double d;
  vector<PP> ans,tmp;
  st(){}
  st(double d,vector<PP> ans,vector<PP> tmp):d(d),ans(ans),tmp(tmp){}
  bool operator<(const st& a)const{
    return d>a.d;
  }
};

int main(){
  double d;
  cin>>n>>d;
  vector<PP> p(n);
  for(int i=0;i<n;i++){
    cin>>p[i].p.x>>p[i].p.y;
    p[i].x=i;
  }
  vector<PP> ans,tmp=p;
  time_t start=clock();
  srand((unsigned)time(NULL));
  
  priority_queue<st> q;
  double dis=subp(tmp);
  q.push(st(dis,vector<PP>(),p));
  double mi=dis;
  while((double)(clock()-start)/CLOCKS_PER_SEC<1.9){
    st s,b;
    if(!q.empty()){
      b=s=q.top();
    }else{
      b=s=st(dis,vector<PP>(),p);
    }
    subp(s.tmp);
    int i=rand()%n;
    Vector u=s.tmp[i].p-c;
    Point rot=u/abs(u)*d;
    double ang=getAngle()*(PI*2)/360.0;
    rot=Point(rot.x*cos(ang)-rot.y*sin(ang),rot.x*sin(ang)+rot.y*cos(ang));
    s.tmp[i].p=s.tmp[i].p+rot;
    s.ans.push_back(s.tmp[i]);
    double di=subp(s.tmp);
    if(di<=mi){
      ans=s.ans;
      tmp=s.tmp;
      mi=di;
      if((int) s.ans.size()<n) q.push(st(di,s.ans,s.tmp));
    }else q.push(b);
  }
  cout<<ans.size()<<endl;
  for(int i=0;i<(int)ans.size();i++){
    printf("%d %.8f %.8f\n",ans[i].x+1,ans[i].p.x,ans[i].p.y);
  }
  subp(tmp);
  for(int i=0;i<n;i++) cout<<tmp[i].x+1<<" \n"[i==n-1];
  
  return 0;
}
【Box Operations】

愚直を書いて9.3%
セグ木とBITで3,4を加速したけどスコア伸びなかった。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,q;
  cin>>n>>q;
  int b[n];
  for(int i=0;i<n;i++) cin>>b[i];
  for(int i=0;i<q;i++){
    int t,l,r;
    cin>>t>>l>>r;
    if(t==1){
      int c;
      cin>>c;
      for(int j=l;j<=r;j++) b[j]+=c;
    }
    if(t==2){
      int d;
      cin>>d;
      for(int j=l;j<=r;j++){
	if(b[j]>=0) b[j]/=d;
	else b[j]=-(-b[j]/d+!!((-b[j])%d));
      }
    }
    if(t==3){
      int ans=b[l];
      for(int j=l;j<=r;j++) ans=min(ans,b[j]);
      cout<<ans<<endl;
    }
    if(t==4){
      int ans=0;
      for(int j=l;j<=r;j++) ans+=b[j];
      cout<<ans<<endl;
    }
  }
  return 0;
}
【全体】

222.40 point
137th/7287
1749 -> 2199 highest

1日目49thとかだったから期待してしまった、、、
Fが解ければ$75だったのになあ