[AtCoder]AtCoder Beginner Contest 133

はじめに

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

コンテストページ

A問題

電車はN人xA円。タクシーは人数に関わらずB円それぞれかかるのでその２つの金額の小さい方が答えです。

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

int main()
{
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
    return 0;
}

B問題

i<jを満たすの組み合わせを全探索し、条件を満たすものをカウントしていきます。
条件を満たしているかどうかの判定にはsqrt()で求まる平方根を整数にキャストしたとき少数点以下が切り捨てられることを利用し、平方根の二乗が元の数と一致するかどうかで判別しています。

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

int main()
{
    int n,d;
    cin >> n >> d;
    vector<vector<int>> x(n, vector<int>(d));
    for (int i = 0; i < n; i++) for (int j = 0; j < d; j++){
        cin >> x[i][j];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++){
        int dist = 0;
        for(int k = 0; k < d; k++){
            dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
        }
        if(dist == ((int)sqrt(dist) * (int)sqrt(dist))){
            ans++;
        }
    }

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

C問題

題意通りに全探索しようとすると計算量的に間に合いません。
以下の二通りを考えることで計算量を減らせます。

1. [l,r]に含まれる数の個数が2019個以上の場合、必ずその中に１つ以上2019で割り切れるものが存在する
2. [l,r]に含まれる数の個数が2019個未満の場合は計算が必要

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

int main()
{
    ll l,r;
    const ll M = 2019;
    cin >> l >> r;
    ll ans = INT32_MAX;
    if(r-l+1 >= M){
        ans = 0;
    }
    else{
        for (ll i = l; i < r; i++){
            for (ll j = i+1; j <= r; j++){
                ans = min(ans, (i*j)%M);
            }
        }
    }

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

D問題

答えとなる各山の降水量のうちどれか１つでも求まると、その両側のダムの水量から隣の山の降水量も求まります。
山1(山iをX_iとする)の降水量は以下のようにして求まります。

Sum = A_1 + A_2 + ... + A_N = X_1 + X_2 + ... + X_N\\
X_i + X_i+1 = 2A_i\\

上記二式から

X_1 = Sum - (X_2 + X_3 + ... + X_N) = Sum - 2(A_2 + A_4 + ... A_{N-1})

※ソースコードでは0インデックスで実装してます。

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

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    vector<ll> ans(n);
    ans[0] = sum;
    for(int i = 0; i < n; i++){
        if(i%2==1) ans[0] -= 2*a[i];
    }
    for(int i = 1; i < n; i++){
        ans[i] = 2 * a[i-1] - ans[i-1];
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

E問題(未AC)

まだ解いておりません。

F問題(未AC)

まだ解いておりません。