beet's soil

競プロのことなど

Facebook Hacker Cup 2017 Qualification Round

初24時間コンテスト

【30 Lazy Loading】

ソートして重いやつから貪欲。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int T;
  cin>>T;
  for(int t=0;t<T;t++){
    int n;
    cin>>n;
    int w[n];
    for(int i=0;i<n;i++) cin>>w[i];
    sort(w,w+n);
    int ans=0,l=0,r=n-1;
    while(1){
      int tmp=w[r];
      for(int i=1;l<=r&&i*tmp<50;i++,l++);
      //cout<<l<<" "<<r<<endl;
      if(l>r) break;
      ans++;
      r--;
    }
    printf("Case #%d: ",t+1);
    cout<<ans<<endl;
  }
  return 0;
}
【45 Fighting the Zombie】

構文解析+DP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double calc(int x,int y,int z,int h){
  double dp[x+1][x*y+1];
  for(int i=0;i<=x;i++)
    for(int j=0;j<=x*y;j++)
      dp[i][j]=0;
  dp[0][0]=1.0;
  for(int i=0;i<x;i++){
    for(int j=0;j<=x*y;j++){
      if(dp[i][j]==0) continue;
      for(int k=1;k<=y;k++){
	dp[i+1][j+k]+=dp[i][j]/y;
      }
    }
  }
  double res=0.0;
  for(int j=0;j<=x*y;j++)
    if(j+z>=h) res+=dp[x][j];
  return res;
}
int main(){
  int T;
  cin>>T;
  for(int t=0;t<T;t++){
    int h,s;
    cin>>h>>s;
    double ans=0.0;
    string sp;
    for(int i=0;i<s;i++){
      cin>>sp;
      int x=0,y=0,z=0,j;
      for(j=0;j<(int)sp.size();j++)
	if(sp[j]!='d') x=x*10+sp[j]-'0';
	else break;
      for(j++;j<(int)sp.size();j++)
	if(sp[j]!='+'&&sp[j]!='-') y=y*10+sp[j]-'0';
	else break;
      if(j<(int)sp.size()){
	int si=1-2*(sp[j]=='-');
	for(j++;j<(int)sp.size();j++)
	  z=z*10+sp[j]-'0';
	z*=si;
      }
      //cout<<x<<" "<<y<<" "<<z<<endl;
      ans=max(ans,calc(x,y,z,h));
    }
    printf("Case #%d: %.12lf\n",t+1,ans);
  }
  return 0;
}
【全体】

A落ちたけどBC通ってとりあえず通過。
6分制限怖い、、、