#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全探索やり始めてきて難易度が高くなってきた気がする。