AtCoder Beginner Contest #003 復習

Atcoder 復習 atcoder

はい。
http://abc003.contest.atcoder.jp

A - AtCoder社の給料

Python2

n=int(raw_input())
ans=chk=0
chk+=(n+1)*(n/2)
chk*=10000
if n%2:
    chk+=(n+1)*5000
print chk*1.0/n

C++11

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


int main(){
    int mod=1000000007;
    int n,ans;
    scanf("%d",&n);
    if (n%2==0) {
        ans=(1+n)*(n/2);
    } else {
        ans=(1+n)*(n/2)+((n+1)/2);
    }
    printf("%d\n",ans*10000/n);
    return 0;
}

サイコロの目の総和*1万円を目の数で割れば期待値が出ると思う。もしくは1からxまで1万円掛けて目の数のxで割ったものを加算し続ける方法もある。

B - AtCoderトランプ

Python2

s=raw_input()
t=raw_input()
chk='atcoder@'
for i in range(len(s)):
    if s[i]!=t[i]:
        if '@' not in s[i]+t[i] or (s[i] not in chk or t[i] not in chk):
            print 'You will lose'
            exit()
print 'You can win'

C++11

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


int main(){
    int mod=1000000007;
    int n,m;
    char s[11],t[11];
    scanf("%s",s);
    scanf("%s",t);
    int chk=strlen(s);
    for (int i=0;i<chk;i++) {
        if (s[i]==t[i]) {
            continue;
        } else if (s[i]=='@' && (t[i]=='a' || t[i]=='t' || t[i]=='c' || t[i]=='o' || t[i]=='d' || t[i]=='e' || t[i]=='r')) {
            continue;
        } else if (t[i]=='@' && (s[i]=='a' || s[i]=='t' || s[i]=='c' || s[i]=='o' || s[i]=='d' || s[i]=='e' || s[i]=='r')) {
            continue;
        } else {
            printf("You will lose\n");
            return 0;
        }
    }
    printf("You can win\n");

    return 0;
}

文字列を比較していって違う文字が出てきた時にどちらも@ではない、どちらかは@であるがもう一方が置換できるatcoderではないことが発生した時にloseが確定する。末尾まで起きなかったらwinになる。

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

講座動画を見て最もレートを高めると幾つになるか。

a=0
n,k=map(int, raw_input().split())
l=map(int, raw_input().split())
l.sort()
for i in xrange(n-k,n):
    a=(l[i]+a)/2.0
print a

C++11

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


int main(){
    int mod=1000000007;
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> r(n);
    for (auto&e:r) {
        scanf("%d",&e);
    }
    sort(r.begin(), r.end());
    double ans=0;
    for (int i=n-k;i<n;i++) {
        ans=(ans+r[i])/2;
    }
    printf("%.10f\n",ans);

    return 0;
}

最大化のためにはスコアの大きいものを使う必要があり、より先に使ったものは減りが大きいのでスコアの上位k本を選んでその中でスコアの小さいものから使うのが最善となる。

D - AtCoder社の冬

Python2

t=1000000007
a=0
r,c=map(int, raw_input().split())
x,y=map(int, raw_input().split())
d,l=map(int, raw_input().split())
room=((r+1)-x)*((c+1)-y)
 
def pascal(num): 
    num = int(num) if num else 10
    l = [1]
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l
 
 
print pascal(d+l)[d]*room%t

C++11

#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;
            }
        }
        tmp++;
        memcpy(a,b,sizeof(b));
        long b[1000];
    }
    return a[r];
}



int main(){
    int mod=1000000007;
    int r,c,x,y,d,l,ans;
    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);
    return 0;
}

101点満点解法は無理だったので100点までしか出来ていない。100点までなら、
1.社員室の中でデスク/サーバーの区切り方が何通りあるか。
2.デスク/サーバースペースの中で設置の仕方が何通りあるか。
の積が解になる。
101点解法は少し保留。