Tamflexの貯蔵庫

やる気のない備忘録

abc 034

c問題

abc034.contest.atcoder.jp

前にやった剰余のやつ. フェルマーの小定理を用いて逆元を求める.

template <long long modulo>
class Modulo
{
private:
  long long inv()
  {
    long long p = mod - 2;
    long long ans = 1;
    for(;p != 0;p >>= 1LL)
    {
      if(p&1LL)ans=(ans * x) % mod;
      x=(x*x)%mod;
    }
    return ans;
  }
public:
  long long mod = modulo;
  unsigned long long x;
  Modulo() : x(0) {}
  Modulo(signed s) {while(s<0)s+=mod;x=s%mod;}
  Modulo(signed long long s) {while(s<0)s+=mod;x=s%mod;}
  operator int(){return (int) x;}
  operator long long(){return (long long) x;}
  Modulo &operator+=(Modulo q){if((x+=q.x)>=mod)x-=mod; return *this;}
  Modulo &operator-=(Modulo q){if((x+=mod-q.x)>=mod)x-=mod; return *this;}
  Modulo &operator*=(Modulo q){x=(unsigned long long)x*q.x%mod; return *this;}
  Modulo &operator/=(Modulo q){x=(unsigned long long)x*q.inv()%mod; return *this;}
  Modulo operator+(Modulo q){return Modulo(*this)+=q;}
  Modulo operator-(Modulo q){return Modulo(*this)-=q;}
  Modulo operator*(Modulo q){return Modulo(*this)*=q;}
  Modulo operator/(Modulo q){return Modulo(*this)/=q;}
  template<typename T> Modulo &operator+=(const T q){if((x+=q)>=mod)x-=mod; return *this;}
  template<typename T> Modulo &operator-=(const T q){if((x+=mod-q)>=mod)x-=mod; return *this;}
  template<typename T> Modulo &operator*=(const T q){x=(unsigned long long)x*q%mod; return *this;}
  template<typename T> Modulo &operator/=(const T q){x=(unsigned long long)x*(Modulo(q)).inv()%mod; return *this;}
  template<typename T> Modulo operator+(const T q){return Modulo(*this)+=q;}
  template<typename T> Modulo operator-(const T q){return Modulo(*this)-=q;}
  template<typename T> Modulo operator*(const T q){return Modulo(*this)*=q;}
  template<typename T> Modulo operator/(const T q){return Modulo(*this)/=q;}
};


int main()
{
  int w, h; cin >> w >> h; w--; h--;
  Modulo<1000000007> ans(1);
  Modulo<1000000007> tmp(1);
  FOR(i,1,min(w,h))
  {
    ans *= (w+h-i+1);
    tmp *= i;
  }
  ans /= tmp;
  cout << (ll)ans << endl;
  return 0;
}

D問題

abc034.contest.atcoder.jp

平均の最大化問題はそれが可能かどうか判定することによる二分探索が有効らしい.

int k,n;
double W[1001];
double P[1001];

int main()
{
  double l=101, r=-1, m;
  cin >> n >> k;
  REP(i,n)
  {
    cin >> W[i] >> P[i];
    l = min(l,P[i]);
    r = max(r,P[i]);
  }
  int cnt = 0;
  while(cnt < 100)
  {
    m = (l+r)/2;
    vector<double> a(n);
    REP(i,n) a[i]=(P[i]-m)*W[i];
    sort(a.begin(),a.end(),greater<double>());
    double s = 0;
    REP(i,k) s+=a[i];
    if(s>0) l=m;
    else r=m;
    cnt++;
  }
  printf("%.9lf\n",l);
}