AtCoder Beginner Contest 145
はい. AtCoder Beginner Contest 145 です
ABCの3完でした.
Dが解けませんでした…辛い…
A - Circle
を出力するだけですね.
#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
が奇数だとそもそも半分で分けることが無理なので 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
だから, 全列挙しても間に合うはずなので,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 問題解けたら更新します.