[AtCoder]AtCoder Beginner Contest 188 A~E問題

A問題

2数の差が２以下の場合はNo、そうでない場合Yes

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

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

    if(abs(a-b) <= 2){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

B問題

問題文そのまま。

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

int main()
{
    int n;
    cin >> n;
    int a[100000] = {0};
    int b[100000] = {0};

    long long ans = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        ans += a[i] * b[i];
    }

    if(ans == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

C問題

2のN乗は1を右にNビットシフトすればよい。
セグ木を使うまでもなくAの前半分と後ろ半分それぞれのmaxのうち小さい方のIndexを出力すればよい問題。

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

int main()
{
    int n;
    cin >> n;
    n = 1 << n;
    vector<int> a(n);

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

    auto left = max_element(a.begin(), a.begin() + (n/2));
    auto right = max_element(a.begin() + (n/2), a.end());

    if(min(*left,*right) == *left){
        cout << distance(a.begin(), left) + 1 << endl;
    }else{
        cout << distance(a.begin(), right) + 1 << endl;
    }

    return 0;
}

D問題

a,bの制約上、各日ごとにかかる金額を計算していては間に合わない。
a_i日目にc_i円増額、b_i+1日目にc_i円減額ととらえ、それを日にちでソートしてシュミレーションを行う。

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

int main()
{
    ll N,C;
    cin >> N >> C;
    vector<pair<ll ,ll>> tl;

    for(ll i = 0; i < N; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        tl.push_back(make_pair(a,c));
        tl.push_back(make_pair(b+1,-c));
    }

    sort(tl.begin(), tl.end());

    ll ans = 0;
    ll sub = 0;
    ll prev = 0;
    for(auto e : tl){
        ans += min(sub, C) * (e.first - prev);
        sub += e.second;
        prev = e.first;
    }

    cout << ans << endl;

    return 0;
}

E問題

DP問題。
X_i < Y_iから道をsortしておき、道を辿って各町について以下二点を記録していく

1. その町までの経路上の町の最安値
2. その町で金を売った場合の最大利益

2の最大値が答えとなる。

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

int main()
{
    ll n,m;
    cin >> n >> m;
    vector<ll> a(n);
    vector<pair<ll,ll>> xy;
    vector<ll> mini(n,0);
    vector<ll> gain(n,LLONG_MIN);

    for(int i = 0; i < n; i++) {
        cin >> a[i];
        mini[i] = a[i];
    }
    for(int i = 0; i < m; i++){
        ll x,y;
        cin >> x >> y;
        x--;
        y--;
        xy.push_back(make_pair(x,y));
    } 

    sort(xy.begin(), xy.end());

    for(auto tmp : xy){
        if(a[tmp.second] - mini[tmp.first] > gain[tmp.second]){
            gain[tmp.second] = a[tmp.second] - mini[tmp.first];
            mini[tmp.second] = min(mini[tmp.first], a[tmp.second]);
        }
    }

    cout << *max_element(gain.begin(), gain.end()) << endl;

    return 0;
}