AtCoder 生活106日目

前回

106日目

今日は、灰色2問と茶色2問と緑色1問を解きました。

問題	難易度	自力で解けた	かかった時間
ARC108	A	◯	47分22秒
CODE FESTIVAL 2016 qual C	A	◯	11分47秒
ABC131	C	◯	35分13秒
diverta 2019 Programming Contest	B	✕	36分26秒
ABC188	D	✕	99分59秒

ARC108_A

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    ll s,p;
    cin >> s >> p;
    for(ll i = 1;i*i <= p;i++){
        if(p%i != 0)continue;
        ll j = p/i;
        if(i+j == s){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

解くのにかかった時間：47分22秒

CODE FESTIVAL 2016 qual C _A

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    string s;
    cin >> s;
    bool ok = false;
    rep(i,s.size()){
        if(ok)if(s[i] == 'F'){
            cout << "Yes" << endl;
            return 0;
        }
        if(s[i] == 'C')ok = true;
    }
    cout << "No" << endl;
}

解くのにかかった時間：11分47秒

ABC131_C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll ra = b/c-a/c;
    if(a%c == 0) ra++;
    ll rb = b/d-a/d;
    if(a%d == 0) rb++;
    ll ab = lcm(c,d);
    ll rab = b/ab-a/ab;
    if(a%ab == 0) rab++;
    ll rans = ra + rb - rab;
    ll ans = b-a+1;
    cout << ans - rans << endl;
}

解くのにかかった時間：35分13秒

diverta 2019 Programming Contest_B

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    int r,g,b,n;
    cin >> r >> g >> b >> n;
    int ans = 0;
    rep(i,3001){
        rep(j,3001){
            int v = i*r + j*g;
            if(n >= v && (n-v)%b == 0)ans++;
        }
    }
    cout << ans << endl;
}

解くのにかかった時間：36分26秒
感想：全探索をまず考えることを忘れ始めている…

ABC188_D

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    ll n,x;
    cin >> n >> x;
    vector<pair<ll,ll>> events;
    rep(i,n){
        ll a,b,c;
        cin >> a >> b >> c;
        events.emplace_back(a,c);
        events.emplace_back(b+1,-c);
    }
    sort(events.begin(),events.end());
    ll ans = 0,s = 0,pre = 0;
    for(auto event : events){
        ans += min(x,s)*(event.first - pre);
        s += event.second;
        pre = event.first;
    }
    cout << ans << endl;
}

解くのにかかった時間：99分59秒
感想：emplace_backの活用方法を今回はじめて知った。

最後に

ABCの灰色の問題は安定して５分以内に解くことを目標にして行こうと思う。
今回始めて緑色の問題を解いたが、解説を読んだ際にかなり理解できた気がする。
いろんな問題を解いてもっと精進していきたいと思う。