[AtCoder]AtCoder Beginner Contest 194

はじめに

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

コンテストページ

A問題

注意深く問題文を読みます。

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

int main()
{
    int a,b;
    cin >> a >> b;

    if(a+b >= 15 && b >= 8){
        cout << 1 << endl;
    }
    else if(a+b >= 10 && b >= 3){
        cout << 2 << endl;
    }
    else if(a+b >= 3){
        cout << 3 << endl;
    }
    else{
        cout << 4 << endl;
    }
    return 0;
}

B問題

仕事A、Bを割り当てる組み合わせを全探索します。

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];

    int ans = INT32_MAX;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ans = min(ans, (i == j) ? a[i] + b[j] : max(a[i], b[j]));
        }
    }

    cout << ans << endl;
    return 0;
}

C問題

問題の計算式をそのまま実装しようとすると計算量が間に合わないので以下のように式を展開し、展開した各項を独立で求めます。

(A_i - A_j)^2 = A_i^2 - 2A_iA_j + A_j^2

ただしこのままだとまだ-2A_iA_j部分がO(N^2)のままなので、累積和を利用して各iについてのA_i x A_jの和をO(1)にすることで全体としてO(n)になります。

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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> aa(n);
    vector<ll> sum(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        aa[i] = a[i] * a[i];
        if(i==0) sum[i] = a[i];
        else sum[i] = sum[i-1] + a[i];
    }

    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += (n-1) * aa[i];
        ans -= 2 * (a[i] * (sum[n-1] - sum[i]));
    }

    cout << ans << endl;
    return 0;
}

D問題

本問題は公式解説の以下の文が前提となります。

確率p(p≠0)で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む)の期待値は1/pである。

まず最初に初期状態である訪問済みの頂点が１つだけの場合を考えます。
この状態で未訪問の頂点が選ばれる確率は(n-1)/nなので未訪問の頂点が選ばれるまでの試行回数の期待値はn/(n-1)です。
次に訪問済みの頂点の数が2の場合を考えると、同様に未訪問の頂点が選ばれるまでの試行回数の期待値はn/(n-2)になります。
このようにして全ての頂点が訪問済みになるまで繰り返し、全ての試行回数の期待値を足してあげればよいです。

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

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

    double ans = 0;
    for (int i = 1; i < n; i++){
        ans += (double)n/(n-i);
    }

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

E問題

i=0のときの区間に含まれる数をmapに入れます。
またそれを用いて区間に含まれないN以下の数をsetに入れます。
あとは各iの区間に含まれる数はi-1のときと二個しか変化がないことを利用ししゃくとり法の要領で各iのmexを求めていけばよいです。

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) mp[a[i]]++;
    set<int> s;
    for (int i = 0; i <= n; i++){
        if(mp.count(i) == 0) s.insert(i);
    }
    int ans = *s.begin();
    for (int i = 0; i < n - m; i++){
        mp[a[i]]--;
        if(mp[a[i]] == 0){
            s.insert(a[i]);
            mp.erase(a[i]);
        }
        if(mp.count(a[i + m]) == 0){
            s.erase(a[i + m]);
        }
        mp[a[i + m]]++;
        ans = min(ans, *s.begin());
    }

    cout << ans << endl;
    return 0;
}

F問題(未AC)

まだ解いておりません。