AtCoder 生活104日目

前回

104日目

今日はC問題2問とD問題を3問ときました。

問題	難易度	自力で解けた	かかった時間
ABC109	C	◯	14分37秒
ABC116	C	◯	33分22秒
ABC190	D	✕	89分50秒

ABC109_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(){
    int N,X;
    cin >> N >> X;
    vector<int> r(N);
    rep(i,N){
        int a;
        cin >> a;
        r[i] = abs(X - a);
    }
    int ans = gcd(r[0],r[1]);
    for(int i = 2;i<N;i++){
        ans = gcd(ans,r[i]);
    }
    cout << ans << endl;
}

解くのにかかった時間：14分37秒

ABC116_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(){
    int n;
    cin >> n;
    int ans = 0;
    int h = 0;
    rep(i,n) {
        int a;
        cin >> a;
        if(a==0)h= 0;
        else{
            if(a <= h){
                h = a;
                continue;
            }
            ans += a - h;
            h = max(h,a);
        }
    }
    cout << ans << endl;
}

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

ABC190_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;
    cin >> n;
    ll n2 = 2*n;
    int ans = 0;
    auto check = [&](ll l){
        ll tmp = n2/l - l + 1;
        if(abs(tmp)%2 == 0) ans++;
    };
    for(ll x = 1;x*x < n2;x++){
        if(n2%x) continue;
        ll y = n2/x;
        check(x);
        if(x != y)check(y);
    }
    cout << ans << endl;
}

解くのにかかった時間：89分50秒
感想：数学的発想ができなかった。

最後に

久々にやったけど最近の灰色bit全探索やり始めてきて難易度が高くなってきた気がする。