SHIINBLOG

AtCoder Beginner Contest 145

はい. AtCoder Beginner Contest 145 です

ABCの3完でした.
Dが解けませんでした…辛い…

f:id:zeronosu77108:20191127133436p:plain


A - Circle

問題文

 R \times R を出力するだけですね.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int r;
    cin >> r;

    cout << r*r << endl;
}



B - Echo

問題文

 N が奇数だとそもそも半分で分けることが無理なので No します.
後は, substr で半分ずつに分けて判定します.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    if (n % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    if (s.substr(0,n/2) == s.substr(n/2, n/2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



C - Average Length

問題文

 N \leq 8 だから, 全列挙しても間に合うはずなので,next_permutation で列挙します.
next_permutation はソートしておく必要があるんだけど, x,y をまとめてソートするのがめんどくさかったので, iota で連続した数列を作ってそれを使いました)

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;

long long frac(long long n) {
    long long res = 1;
    for (int i=1; i<=n; i++) res *= i;
    return res;
}
int main() {
    long long n;
    long double ans = 0;
    long double sum = 0;
    cin >> n;
    vector<long double> x(n);
    vector<long double> y(n);

    for (int i=0; i<n; i++) cin>>x[i]>>y[i];

    vector<int> c(n);
    iota(c.begin(), c.end(), 0);

    do {
        for (int i=0; i<n-1; i++) {
            sum += sqrt( pow(x[c[i]]-x[c[i+1]],2) + pow(y[c[i]]-y[c[i+1]],2));
        }
    } while(next_permutation(c.begin(), c.end()));

    cout << setprecision(14) << (sum/frac(n)) << endl;
}



D - Knight

問題文

コンビネーションで求められることは分かっていたんですが,いろいろダメでした
辛い…

コンテスト後にときました.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

const long long mod = 1e9+7;
struct mint {
  long long x;
  mint(const long long x=0) : x(x%mod) {}
  mint& operator+=(const mint a) {if((x+=a.x)>=mod)x-=mod; return *this;}
  mint& operator-=(const mint a) {if((x+=mod-a.x)>=mod)x-=mod; return *this;}
  mint& operator*=(const mint a) {(x*=a.x) %= mod; return *this;}
  mint& operator+(const mint a) const {mint res(*this); return res+=a;}
  mint& operator-(const mint a) const {mint res(*this); return res-=a;}
  mint& operator*(const mint a) const {mint res(*this); return res*=a;}
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t>>1); a*=a;
    if(t&1) a*= *this;
    return a;
  }
  mint inv() const {return pow(mod-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint& operator/(const mint a) const {mint res(*this); return res/=a;}
};

mint fact(long long n) {
  mint res = 1;
  for (long long i=n; i>0; i--) res*=i;
  return res;
}

int main() {
  long long x,y;
  cin >> x >> y;

  if ((x+y)%3 != 0) {
    puts("0");
    return 0;
  }

  long long a = (2*x-y)/3;
  long long c = (2*y-x)/3;

  if (a<0 || c<0) {
    puts("0");
    return 0;
  }

  mint ans = fact(a+c);
  ans /= fact(a);
  ans /= fact(c);
  cout << ans.x << endl;
  return 0;
}



まとめ

レート微増(+2)でした.
最近下がりっぱなしだったので,少しましですね…

次はもっと頑張ります

E 問題解けたら更新します.