beet's soil

競プロのことなど

Facebook Hacker Cup 2017 Round 1

通過すると来週つらいなあと思いながら出た。

【10: Pie Progress】

i日目にはi個以上買っていないといけないみたいな貪欲+DP。
安い方から買う方がいいのでそれぞれの日ごとにソートしておく。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1LL<<55LL;
int main(){
  ll T;
  cin>>T;
  for(ll t=1;t<=T;t++){
    printf("Case #%lld: ",t);
    ll n,m;
    cin>>n>>m;
    vector<ll> v[n];
    for(ll i=0;i<n;i++){
      v[i].resize(m);
      for(ll j=0;j<m;j++) cin>>v[i][j];
      sort(v[i].begin(),v[i].end());
    }
    ll dp[n+1][n+1],ans=INF;;
    for(ll i=0;i<=n;i++)
      for(ll j=0;j<=n;j++)
	dp[i][j]=INF;
    dp[0][0]=0;
    for(ll i=0;i<n;i++){
      ll c[m+1];
      c[0]=0;
      for(ll j=0;j<m;j++) c[j+1]=c[j]+v[i][j];
      for(ll j=i;j<=n;j++){
	dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
	for(ll k=0;j+k<=n&&k<=m;k++)
	  dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+c[k]+k*k);
      }
      //for(ll j=0;j<=n;j++) cout<<dp[i+1][j]<<" \n"[j==n];
      ans=min(ans,dp[i+1][n]);
    }
    cout<<ans<<endl;
  }
  return 0;
}
【25: Manic Moving】

ワーシャルフロイドしたあと、今の位置と一個前の配達を済ませてあるかを持ってDP
K=1がコーナーなので気をつける

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll T;
  cin>>T;
  for(ll t=1;t<=T;t++){
    ll n,m,k;
    cin>>n>>m>>k;
    //cout<<n<<m<<k<<endl;
    ll e[n][n],inf=1LL<<50LL;
    for(ll i=0;i<n;i++)
      for(ll j=0;j<n;j++) e[i][j]=(i!=j)*inf;
    for(ll i=0;i<m;i++){
      ll a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      e[a][b]=min(e[a][b],c);
      e[b][a]=min(e[b][a],c);
    }
    for(ll l=0;l<n;l++)
      for(ll i=0;i<n;i++)
	for(ll j=0;j<n;j++)
	  e[i][j]=min(e[i][j],e[i][l]+e[l][j]);
    ll s[k],d[k];
    for(ll i=0;i<k;i++){
      cin>>s[i]>>d[i];
      s[i]--;d[i]--;
    }
    ll dp[2][k],ans=inf;
    for(ll i=0;i<k;i++) dp[0][i]=dp[1][i]=inf;
    dp[0][0]=e[0][s[0]];
    //cout<<dp[0][0]<<endl;
    for(int i=0;i<k-1;i++){
      dp[0][i+1]=min(dp[0][i+1],dp[0][i]+e[s[i]][d[i]]+e[d[i]][s[i+1]]);
      dp[1][i+1]=min(dp[1][i+1],dp[0][i]+e[s[i]][s[i+1]]);

      if(i){
	dp[0][i+1]=min(dp[0][i+1],dp[1][i]+e[s[i]][d[i-1]]+e[d[i-1]][d[i]]+e[d[i]][s[i+1]]);
	dp[1][i+1]=min(dp[1][i+1],dp[1][i]+e[s[i]][d[i-1]]+e[d[i-1]][s[i+1]]);
      }
      //cout<<dp[0][i+1]<<endl<<dp[1][i+1]<<endl;
    }
    ans=dp[0][k-1]+e[s[k-1]][d[k-1]];
    if(k-1) ans=min(ans,dp[1][k-1]+e[s[k-1]][d[k-2]]+e[d[k-2]][d[k-1]]);
    cout<<"Case #"<<t<<": "<<(ans>=inf?-1:ans)<<endl;
  }
  return 0;
}
【40: Beach Umbrellas】

両端決め打ちすると空白を含めた場合の数みたいになるのでがんばって求める。
N!と(N-2)!が打ち消しあってO(N^2)。
K=1のときはM。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD=1000000007LL;
ll extgcd(ll a,ll b,ll& x,ll& y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
int main(){
  ll T;
  cin>>T;
  for(ll t=1;t<=T;t++){
    ll n,m;
    cin>>n>>m;
    ll r[n],sr=0;
    for(ll i=0;i<n;i++){
      cin>>r[i];
      sr+=r[i]*2;
    }
    if(n==1){
      cout<<"Case #"<<t<<": "<<m<<endl;
      continue;
    }
    ll p[5000],in=(mod_inverse(n,MOD)*mod_inverse(n-1,MOD))%MOD;
    for(ll i=0;i<5000;i++){
      p[i]=1LL;
      for(ll j=0;j<n;j++) (p[i]*=(m-sr)+i+j)%=MOD;
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
      for(ll j=0;j<n;j++){
	if(i==j||(m-sr)+r[i]+r[j]<0) continue;
	(ans+=(p[r[i]+r[j]]*in)%MOD)%=MOD;
      }
    }
    cout<<"Case #"<<t<<": "<<ans<<endl;
  }
  return 0;
}
【全体】

ACD通って75点で通過。
一応Tシャツ圏内なのでがんばるぞい。