beet's soil

競プロのことなど

AtCoder Beginner Contest 057

ねむい

【A - Remaining Time】

a b + 24 %

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int a,b;
  cin>>a>>b;
  cout<<(a+b)%24<<endl;
  return 0;
}
【B - Checkpoints】

二重ループ。
最初学生と学生の最短距離求めてた(ア。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m;
  cin>>n>>m;
  int a[n],b[n],c[m],d[m];
  for(int i=0;i<n;i++) cin>>a[i]>>b[i];
  for(int i=0;i<m;i++) cin>>c[i]>>d[i];
  for(int i=0;i<n;i++){
    int ans=0;
    for(int j=0;j<m;j++){
      if(abs(a[i]-c[j])+abs(b[i]-d[j])<abs(a[i]-c[ans])+abs(b[i]-d[ans]))
	ans=j;
    }
    cout<<ans+1<<endl;
  }
  return 0;
}
【C - Digits in Multiplication】

10^10 -> √やろなあ

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int ans=to_string(n).size();
  for(int i=1;i*i<=n;i++){
    if(n%i) continue;
    ans=min(ans,max((int)to_string(i).size(),(int)to_string(n/i).size()));
  }
  cout<<ans<<endl;
  return 0;
}
【D - Maximum Average Sets】

出力例 4を見てOh…となる。
ソートして上から見て平均が変わらない範囲で場合の数。
MOD 10^9+7ではないのでパスカル三角数を使う。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int nck(int n,int k){
  int dp[n+1][n+1];
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=i;j++){
      if(j-1>=0){
	dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
      }else{
	dp[i][j]=dp[i-1][j];
      }
    }
  }
  //cout<<n<<" "<<k<<":"<<dp[n][k]<<endl;
  return dp[n][k];
}
signed main(){
  int n,a,b;
  cin>>n>>a>>b;
  int v[n];
  for(int i=0;i<n;i++) cin>>v[i];
  sort(v,v+n);
  reverse(v,v+n);
  int s[n];
  s[0]=0;
  for(int i=0;i<n;i++) s[i+1]=s[i]+v[i];
  printf("%.12f\n",(double)s[a]/a);
  int cnt=0;
  for(int i=a;i<=b;i++){
    if(s[a]*i==s[i]*a){
      if(i==n){
	cnt++;
	continue;
      }
      int tmp=0,idx=-1;
      for(int j=0;j<n;j++){
	if(v[i]<v[j]) idx=j;
	if(v[i]==v[j]) tmp++;
      }
      if(tmp==1){
	cnt+=1;
	break;
      }
      //cout<<i<<endl;
      //cout<<tmp<<" "<<i-idx-1<<endl;
      cnt+=nck(tmp,i-idx-1);
    }else{
      break;
    }
  }
  cout<<cnt<<endl;
  return 0;
}
【全体】

眠すぎてBバグらせたの本当にダメ。
パスカル三角数も持ってるべきだった。
unratedなのでまあよし。