ABC 003

abc003.contest.atcoder.jp

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;
    }
}