[AtCoder]AtCoder Beginner Contest 131

はじめに

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

コンテストページ

A問題

各文字が前後の文字と１つも一致してなければGood、そうでない場合Badです。

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

int main()
{
    string s;
    cin >> s;
    bool good = true;
    for(int i = 0; i < 3; i++){
        if(s[i] == s[i+1]) good = false;
    }

    if(good) cout << "Good" << endl;
    else cout << "Bad" << endl;
    return 0;
}

B問題

1からNまでの各りんごの味をいれた配列を用意し、その中で味の絶対値がもっとも小さいものを求め味の合計から引いたものが答えになります。

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

int main()
{
    int n,l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = l + i;
    
    int m = INT32_MAX;
    for (int i = 0; i < n; i++){
        if(abs(a[i]) < abs(m)){
            m = a[i];
        }
    }

    cout << accumulate(a.begin(), a.end(), 0) - m << endl;
    return 0;
}

C問題

本問題は２つの要素から成り立っています。

１つ目

①一般にX以下の整数でZで割り切れるものの個数はX/Z個です。
②X以下Y以上の整数でZで割り切れるものの個数は、①からY未満の整数でZで割り切れるものも個数(Y-1)/Zを引いたものになります。

２つ目

一般にある範囲の整数のXの倍数でもYの倍数でもないものの数は、その範囲の数の個数からXの倍数の数とYの倍数の数を引き、重複して引いたXとYの最小公倍数の倍数の数の分を足し直したものになります。

これらの要素を組み合わせて本問題を考えると、B以下でCでもDでも割り切れない数の個数とA未満でCでもDでも割り切れない数の個数をそれぞれ求めて、引いてものが個数となります。

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

int main()
{
    ll a,b,c,d,cd;
    cin >> a >> b >> c >> d;
    cd = lcm(c,d);

    // B以下でCでもDでも割り切れないものの個数
    ll x = b - (b/c + b/d - b/cd);
    // A未満でCでもDでも割り切れないものの個数
    ll y = (a-1) - ((a-1)/c + (a-1)/d - (a-1)/cd);

    cout << x - y << endl;
    return 0;
}

D問題

締め切りの早いものから順に処理していけばよいです。根拠は公式解説をご参考ください。

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int,int>> ab(n);
    for(int i = 0; i < n; i++) cin >> ab[i].first >> ab[i].second;
    sort(ab.begin(), ab.end(), [](auto& lhs, auto& rhs){return lhs.second < rhs.second;});

    int time = 0;
    bool yes = true;
    for(auto& x : ab){
        time += x.first;
        if(x.second < time) {
            yes = false;
            break;
        }
    }

    if(yes) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

E問題(未AC)

まだ解いていません。

F問題(未AC)

まだ解いていません。