SHIINBLOG

AtCoder Beginner Contest 126

はい. AtCoder Beginner Contest 126 です

22:00から始めるという縛りプレイでした.

タイムはそんなに悪くないかな… f:id:zeronosu77108:20190519232304p:plain

A - Changing a Character

問題文
k番目の文字を小文字にするやつ.
char型に1文字ずつ読み込んでいって,k番目なら tolower するだけでできた.

#include <iostream>

using namespace std;

int main(void) {
    int n,k;
    char c;
    cin >> n >> k;

    for (int i=1; i<=n; i++) {
        cin >> c;
        if ( k == i ) {
            c = tolower(c);
        }
        cout << c;
    }
    cout << endl;
}



B - YYMM or MMYY

問題文
日付の表記判断.
2桁ずつに別けて, 1 ≦ x ≦ 12 か判断するだけ.

#include <iostream>

using namespace std;


int main(void) {
    string str;
    int i,j;
    cin >> str;
    bool i_f, j_f;
    i_f = j_f = false;

    i = stoi( str.substr(0,2) );
    j = stoi( str.substr(2,2) );

    if ( 0<i && i<=12 ) {
        i_f = true;
    }
    if ( 0<j && j<=12 ) {
        j_f = true;
    }

    if (i_f && j_f) {
        cout << "AMBIGUOUS" << endl;
    } else if ( i_f ) {
        cout << "MMYY" << endl;
    } else if ( j_f ) {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
}



C - Dice and Coin

問題文
確率の計算していくだけ.テキトーでいけるかなと思って書いた.

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp *= 2.0;
        }
        ans += (1.0 / tmp);
    }

    printf("%.16f\n", ans);
}

すると,サンプルの2と何故か微妙に違う…
時間も無かったので,とりあえずそのまま提出しました.


解説を見るとほぼ同じプログラム…
なんと確率の分母を全部取って割り算ではなく,逐次で /=2 していた.

うーん,そんなに差が出るんか…?

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = 1.0 / n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp /= 2.0;
        }
        ans += tmp;
    }

    // cout << ans << endl;
    printf("%.16f\n", ans);
}

2019-05-20 追記
doublelong double にしたら 誤差が 1*10^{-9} 以下になりました.




D - Even Relation

問題文
はい.時間が無くて超雑に書きました.
通るわけ無いですよね.

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int ans[100010];
    bool f[100010];
    for (int i=0; i<10000; i++) {
        f[i] = false; ans[i] = 1;
    }

    int u[100010],v[100010],w[100010];
    
    cin >> n;
    
    for (int i=0; i<n-1; i++) {
        cin >> u[i] >> v[i] >> w[i];
        if (w[i]%2 == 0) {
            f[u[i]-1] = true;
            f[v[i]-1] = true;
        } else {
            if ( ans[u[i]-1] != -1 && ans[v[i]-1] != -1 ) {
                if ( ! f[u[i]-1] ) {
                    ans[u[i]-1] = 0;
                } else if ( ! f[v[i]-1] ) {
                    ans[v[i]-1] = 0;
                } 
            }
        }

    }

    for (int i=0; i<n; i++) {
        cout << ans[i] << endl;
    }
}

とりあえず2点間が偶数なら良いじゃん!っていうアレで書いたんだけど,
雑過ぎました.
しかも,未定義を -1 とした名残の if文が残っている…



圧倒的時間不足により問題文把握,プログラムが雑になってしまった感があります…
次はちゃんと時間作るぞ〜

あ, E問題 と F問題は解けたら上げます.