[AtCoder]AtCoder Beginner Contest 193

はじめに

• AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
• 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。

コンテストページ

A問題

問題文通りなので割愛。

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

int main()
{
    double a,b;
    cin >> a >> b;
    cout << setprecision(8) << (1-b/a)*100 << endl;
    return 0;
}

B問題

各店舗についてA < Xなら買えるので、買える店舗の中で一番安い店を求めればよいです、

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

int main()
{
    int n;
    cin >> n;

    int ans = INT32_MAX;
    for(int i = 0; i < n; i++){
        int a,p,x;
        cin >> a >> p >> x;
        if(a < x){
            ans = min(ans, p);
        }
    }

    if(ans == INT32_MAX){
        cout << -1 << endl;
    }
    else{
        cout << ans << endl;
    }

    return 0;
}

C問題

aのb乗で表せるものの個数をカウントし、Nから引いてあげます。
計算を考慮しaは最大でもNの二乗根を超えることがないことから、aをNの二乗根まで全探索します。
カウントの重複を避けるためsetまたはunordered_setを使います。

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

int main()
{
    u64 n;
    cin >> n;
    set<u64> s;

    for(u64 i = 2; i*i <= n; i++){
        u64 x = i*i;
        while(x <= n){
            s.insert(x);
            x *= i;
        }
    }

    cout << n-s.size() << endl;
    return 0;
}

D問題

山札を構造体で定義し、各人がカードが4枚ずつ引いた状態にします。
最後の1枚の配られ方9*9通りのうち、高橋くんの勝つパターンのみの確率を足していってあげればよいです。
山札からカードを引く関数でカードの減算と戻り値で引く確率を返してあげるとスッキリします。

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

struct Deck{
    Deck(int k) : sum(k*9), num(10, k){};
    int sum;
    vector<int> num;
    double draw(int x){
        if(num[x]==0) return 0;
        double ret = (double)num[x]/sum;
        num[x]--;sum--;
        return ret;
    }
};

int main()
{
    int k;
    cin >> k;
    string s,t;
    cin >> s >> t;
    Deck D(k);
    for(int i = 0; i < 4; i++) D.draw(s[i]-'0');
    for(int i = 0; i < 4; i++) D.draw(t[i]-'0');

    double ans = 0;
    for(int i = 1; i < 10; i++){
        s[4] = i+'0';
        for(int j = 1; j < 10; j++){
            t[4] = j+'0';
            int ss = 0;
            int ts = 0;
            for(int k = 1; k < 10; k++){
                ss += k * pow(10, count(s.begin(), s.end(), '0' + k));
                ts += k * pow(10, count(t.begin(), t.end(), '0' + k));
            }
            if(ss > ts){
                Deck d = D;
                ans += d.draw(i) * d.draw(j);
            }
        }
    }

    cout << setprecision(16) << ans << endl;
    return 0;
}

E問題(未AC)

まだ解いておりません。

F問題(未AC)

まだ解いておりません。