ABC 003
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; double s; REP(i, N) { s += 10000*double(i+1)/N; } printf("%.10f\n", s); }
Submission #1024144 - AtCoder Beginner Contest 003 | AtCoder
B問題
"string"[i]
というテクニックを学んだ
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { string S, T; cin >> S >> T; bool win = true; map<char, bool> ok; REP(i, 7) ok["atcoder"[i]] = true; REP(i, S.size()) { if(S[i] != T[i]) { if(S[i] == '@' && ok[T[i]]) continue; if(T[i] == '@' && ok[S[i]]) continue; win = false; } } if(win) cout << "You can win" << endl; else cout << "You will lose" << endl; }
Submission #1024159 - AtCoder Beginner Contest 003 | AtCoder
C問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N, K; cin >> N >> K; vector<int> R(N); REP(i, N) { cin >> R[i]; } sort(R.begin(), R.end()); double ans = 0; FOR(i, N-K, N) { ans = (ans + R[i]) / 2.0; } printf("%.10f\n", ans); }
Submission #1024161 - AtCoder Beginner Contest 003 | AtCoder
D問題
100点解法。nCrをパスカルの三角形を使って求める。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; const ll mod = 1000000007; vector<vector<int> > C(1000, vector<int>(1000, -1)); ll combination(int n, int r) { if(r == 0 || r == n) return 1; if(C[n][r] != -1) return C[n][r]; return (C[n][r] = (combination(n-1, r-1)+combination(n-1, r))%mod); } int main(void) { int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; cout << ((R-X+1) * (C-Y+1) * combination(D+L, D)) % mod << endl; }
101点解法 Submission #740595 - AtCoder Beginner Contest 003 | AtCoderを見た
上下左右の壁にくっついているパターンの数を、包除原理を用いて上下左右にくっついていないパターンを取り除くことで求める。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; const ll mod = 1e9+7; int R, C, X, Y, D, L; vector<vector<int> > memo(1000, vector<int>(1000, -1)); ll nCr(int n, int r) { if(n < 0 || r < 0 || n < r) return 0; if(r == 0 || r == n) return 1; if(memo[n][r] != -1) return memo[n][r]; return (memo[n][r] = (nCr(n-1, r-1) + nCr(n-1, r))%mod); } int main(void) { cin >> R >> C >> X >> Y >> D >> L; const int N = D + L; if(X*Y == N) { cout << (C-Y+1)*(R-X+1) * nCr(N, L) % mod << endl; } else { ll t = ( ( nCr(X*Y, N) - ( 2 * (nCr((X-1)*Y, N) + nCr(X*(Y-1), N)) ) + ( nCr((X-2)*Y, N) + nCr(X*(Y-2), N) + 4 * nCr((X-1)*(Y-1), N) ) - ( 2 * (nCr((X-2)*(Y-1), N) + nCr((X-1)*(Y-2), N)) ) + ( nCr((X-2)*(Y-2), N) ) ) * nCr(N, L) % mod * (C-Y+1) % mod * (R-X+1) ) % mod; while(t < 0) t += mod; cout << t << endl; } }