AtCoder Beginner Contest 003

はい。
AtCoder Beginner Contest 003
寝ぼけてるのでD問題無理で。寝ぼけてなくてもむりですけど。

A - AtCoder社の給料

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define sl1(a)  scanf("%lld",&a)
#define sl2(a,b)  scanf("%lld %lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld %lld %lld",&a,&b,&c)
#define PI 3.1415926535897932
//int64_t はatcoderメリット不明のため long long
#define ll long long
//#define ll int64_t
#define print(a) cout << a << endl


//
int souwa(int a) {return (1+a)*a/2;}
int lcm(int a,int b) { return a*b/__gcd(a,b); }
//l l lcm(ll a,ll b) { return a*b/__gcd(a,b); }

//
bool sankaku(int a,int b,int c) {vector <int> t={a,b,c};sort(t.begin(),t.end()); return t.at(0)+t.at(1)>t.at(2);};

/** sort(ar.begin(),ar.end())
    int sum=accumulate(ar.begin(),ar.end(),0); 
    do {// do内部で作られた順列に対して必要な処理を行う
        // cout << w.at(0) << w.at(1) << w.at(2) << endl;
    } while (next_permutation(w.begin(),w.end()));  //ex. vector <int> w= {1,2,3}; **/

// 何か貼るときはココから下に

int main(){
    int n,m,x,y,cnt=0;
    cin >> n;
    double ans=0.0;
    rep(i,n) ans+=(((1+i)*10000.0)/n);
    printf("%.10lf\n",ans);
    return 0;
}

出力例1で教えてくれている計算方法の通りに。

B - AtCoderトランプ

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define sl1(a)  scanf("%lld",&a)
#define sl2(a,b)  scanf("%lld %lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld %lld %lld",&a,&b,&c)
#define PI 3.1415926535897932
//int64_t はatcoderメリット不明のため long long
#define ll long long
//#define ll int64_t
#define print(a) cout << a << endl


//
int souwa(int a) {return (1+a)*a/2;}
int lcm(int a,int b) { return a*b/__gcd(a,b); }
//l l lcm(ll a,ll b) { return a*b/__gcd(a,b); }

//
bool sankaku(int a,int b,int c) {vector <int> t={a,b,c};sort(t.begin(),t.end()); return t.at(0)+t.at(1)>t.at(2);};

/** sort(ar.begin(),ar.end())
    int sum=accumulate(ar.begin(),ar.end(),0); 
    do {// do内部で作られた順列に対して必要な処理を行う
        // cout << w.at(0) << w.at(1) << w.at(2) << endl;
    } while (next_permutation(w.begin(),w.end()));  //ex. vector <int> w= {1,2,3}; **/

// 何か貼るときはココから下に

int main(){
    int mod=1000000007;
    int n,m,x,y,cnt=0,ans=0;
    string s,t,p="atcoder@";
    cin >> s >> t;
    rep(i,s.size()) {
        if (s.at(i)!=t.at(i) && s.at(i)=='@') {
            rep(j,8) {
                if (t.at(i)==p.at(j)) break;
                if (j==7) ans=1;
            }
        } else  if (s.at(i)!=t.at(i) && t.at(i)=='@') {
            rep(j,8) {
                if (s.at(i)==p.at(j)) break;
                if (j==7) ans=1;
            }
        } else if (s.at(i)!=t.at(i)) {
            ans=1;
        }
    }
    cout << ((ans)?"You will lose":"You can win") << endl;

    return 0;
}

先頭から比較する。相違している時は@と置き換えできる文字の関係かどうか。

C - AtCoderプログラミング講座

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define sl1(a)  scanf("%lld",&a)
#define sl2(a,b)  scanf("%lld %lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld %lld %lld",&a,&b,&c)
#define PI 3.1415926535897932
//int64_t はatcoderメリット不明のため long long
#define ll long long
//#define ll int64_t
#define print(a) cout << a << endl


//
int souwa(int a) {return (1+a)*a/2;}
int lcm(int a,int b) { return a*b/__gcd(a,b); }
//l l lcm(ll a,ll b) { return a*b/__gcd(a,b); }

//
bool sankaku(int a,int b,int c) {vector <int> t={a,b,c};sort(t.begin(),t.end()); return t.at(0)+t.at(1)>t.at(2);};

/** sort(ar.begin(),ar.end())
    int sum=accumulate(ar.begin(),ar.end(),0); 
    do {// do内部で作られた順列に対して必要な処理を行う
        // cout << w.at(0) << w.at(1) << w.at(2) << endl;
    } while (next_permutation(w.begin(),w.end()));  //ex. vector <int> w= {1,2,3}; **/

// 何か貼るときはココから下に

int main(){
    int mod=1000000007;
    int n,k,m,x,y,cnt=0;
    double ans=0;
    cin >> n >> k;
    vector<int> r(n);
    rep(i,n) cin >> r.at(i);
    sort(r.begin(),r.end());
    vector<int> w;
    rep(i,k) w.push_back(r.at(n-1-i));
    sort(w.begin(),w.end());
    rep(i,k) ans=(ans+w.at(i))/2;
    printf("%.10lf\n",ans);
    return 0;
}

効果の大きい動画は後から見る。先に見ると1/2され続けて損なので。

D - AtCoder社の冬

▶クリックで開閉

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
//long long mod=1000000007;

long long pscl(int n, int r) {
    long tmp=2;
    long a[1000];
    a[0]=1;
    a[1]=1;
    long b[1000];
    for (int i=2;i<=n;i++) {
        for (int j=0;j<tmp+1;j++) {
            if (j==0 || j==tmp) {
                b[j]=1;
            } else {
                //b[j]=(a[j]+a[j-1])%mod;
                1;
            }
        }
        tmp++;
        memcpy(a,b,sizeof(b));
        long b[1000];
    }
    return a[r];
}


const int MAX=510000;
const int MOD=1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];

//前処理 
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for (int i=2;i<MAX;i++) {
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
//二項係数計算
long long COM(int n,int k) {
    if (n<k) return 0;
    if (n<0 || k<0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}


int main(){
    int mod=1000000007;
    int r,c,x,y,d,l,ans=1;
    scanf("%d %d",&r,&c);
    scanf("%d %d",&x,&y);
    scanf("%d %d",&d,&l);
    //printf("%d\n",pscl(d+l,max(d,l))*((r+1)-x)*((c+1)-y)%mod);
    //ans=(r-y+1)*(c-x+1)%mod;
    COMinit();
    if (x*y>(d+l)) cout << 0 << endl;
    else cout << (r-x+1)*(c-y+1)%mod*COM(d+l,d)%mod<< endl;


    return 0;
}

100点分までは組み合わせ計算さえできればなんとか。社内で社員室の区切り方と、社員室内のデスク・サーバーの配置の仕方の組み合わせの積。100点分までは社員室に隙間なく詰め込むので大きな工夫要素はなし。
101点満点は隙間があるけど社員室の条件としては上下左右の壁に何も接しないことがないようにらしいので接しないパターンが除く必要があり。 これはあとで。