AtCoder Beginner Contest 008

はい。
AtCoder Beginner Contest 008
C問題満点とD問題は難易度おかしいのでまた今度。今日は頭痛いので。

A - アルバム

▶クリックで開閉

#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;
    cin >> n >> m;
    //cin >> m;

    print(m-n+1);
    return 0;
}

差分。

B - 投票

▶クリックで開閉

#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;
    cin >> n;
    map<string,int> w;
    rep(i,n){
        cin >> s;
        w[s]++;
        if(w[s]>ans){
            ans=w[s];
            t=s;
        }
    }

    print(t);
    return 0;
}

mapで数えました。文字列を全部vectorに突っ込んでからソートして先頭から見て同じのが連続とかでも数えられないことはないのかも。やりませんけど。

C - コイン

▶クリックで開閉

#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=0,x=0,y=0,cnt=0;
    double ans=0.0;
    cin >> n;
    vector<int> c(n);
    rep(i,n) cin >> c.at(i);
    rep(i,n) {
        cnt=0;
        rep(j,n) {
            if(i!=j && c.at(i)%c.at(j)==0) cnt++;
        }
        if (cnt%2) ans+=0.5;
        //else ans+=(1.0*(cnt+2))/(1.0*(cnt*2+2));
        else ans+=((cnt/2+1)*1.0)/(1.0*cnt+1.0);
    }

    printf("%.10lf\n",ans);

    return 0;
}

それに対して約数が何個あるかに注目する。約数が奇数個あるときはそれの配置される箇所が偶数箇所ある。_約数_約数_約数_みたいな感じ。 偶数箇所あって操作の最終結果の姿は左から表裏表裏...になる。最左のときは初期配置の表のままでそれが裏返されないため。以降は1つずつずれるごとに裏表裏...になる。なのでそれに対して約数の個数が奇数個のときは表の期待値が1/2で0.5となる。
それに対して約数が偶数個あるときは配置箇所が奇数箇所。_約数_約数_約数_約数_みたいな感じ。表裏表...となる。偶数は解説と違う式でACになって困ってる。
((cnt/2+1)*1.0)/(1.0*cnt+1.0) 分子の ((cnt/2+1)*1.0) は配置箇所の奇数個に対して表裏表...になるので。 分母の (1.0*cnt+1.0) は(偶数じゃなくても)約数がある個数の+1が配置箇所。それで期待値が求められるかなーでAC。いまいち証明しきれてない気がするので嘘解法かどうか自信なし。