AtCoder 生活　49日目

[前回](https://qiita.com/flandrescarlet237/items/67af365fbf71d4b68fef)

#49日目
今回は、A問題を4問、B問題を4問、C問題を4問解きました。

|問題|難易度|自力で解けた|かかった時間|
|:-:|:-:|:-:|---|---|
|ABC035|A|◯|30分2秒|
|ABC035|B|✕|63分1秒|
|ABC034|A|◯|1分44秒|
|ABC034|B|◯|4分4秒|
|ABC033|A|◯|12分3秒|
|ABC033|B|◯|23分47秒|
|ABC032|A|◯|10分59秒|
|ABC032|B|✕|66分24秒|
|ABC122|C|✕|87分30秒|
|ABC118|C|✕|87分32秒|
|ABC117|C|✕|53分34秒|
|ABC116|C|✕|129分20秒|


##[ABC035](https://atcoder.jp/contests/abc035)

###A

```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>;

int gcd(int a,int b){
    if(a%b == 0){
        return(b);
    }
    else{
        return(gcd(b,a%b));
    }
}

int main(){
    int h,w;
    cin >> h >> w;
    int a = gcd(h,w);
    if(h/a == 4 && w/a == 3) cout << "4:3" << endl;
    else cout << "16:9" << endl;
}

```

解くのにかかった時間：30分2秒

###B


```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>;
using pil = pair<pii,int>;


int main(){
    string s;
    cin >> s;
    int t;
    cin >> t;
    int x = 0,y = 0;
    int cnt = 0;
    rep(i,s.size()){
        if(s[i] == '?') cnt++;
		else if(s[i] == 'L') x -= 1;
		else if(s[i] == 'R') x += 1;
		else if(s[i] == 'U') y += 1;
		else if(s[i] == 'D') y -= 1;
    }
    x = abs(x);
	y = abs(y);
	if(t == 1){
		cout << x + y + cnt << endl;
	}else if(t == 2){
		int m = x + y - cnt;
		if(m >= 0) cout << m << endl;
		else{
			cnt = -m;
			if(cnt % 2 == 0) cout << 0 << endl;
			if(cnt % 2 == 1) cout << 1 << endl;
		}
	}
}

```

解くのにかかった時間：63分1秒
感想：？の扱いに悩んでしまった。


##[ABC034](https://atcoder.jp/contests/abc034)

###A

```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>;

int main(){
    int x,y;
    cin >> x >> y;
    if(x > y)cout << "Worse" << endl;
    else cout << "Better" << endl;
}

```
解くのにかかった時間：1分44秒


###B


```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>;
using pil = pair<pii,int>;


int main(){
    ll n;
    cin >> n;
    if(n%2 == 0)cout << n-1 << endl;
    else cout << n+1 << endl;
}
```
解くのにかかった時間：4分4秒


##[ABC033](https://atcoder.jp/contests/abc033)

###A

```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>;

int main(){
    int n;
    cin >> n;
    bool ok = true;
    int a = n%10;
    n /= 10;
    int b = n%10;
    n /= 10;
    int c = n%10;
    int d = n/10;
    if(a == b && b == c && c == d) cout << "SAME" << endl;
    else cout << "DIFFERENT" << endl;
}

```
解くのにかかった時間：12分3秒


###B


```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>;
using pil = pair<pii,int>;
using pll = pair<int,string>;


int main(){
    int n;
    cin >> n;
    ll sum = 0;
    vector<pll> x(n);
    rep(i,n){
        string a;
        int b;
        cin >> a >> b;
        x[i].first = b;
        x[i].second = a;
        sum += b;
    }
    sort(x.rbegin(),x.rend());
    if(sum/2 < x[0].first){
        cout << x[0].second << endl;
    }
    else cout << "atcoder" << endl;
}

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


##[ABC032](https://atcoder.jp/contests/abc032)

###A

```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>;

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}

int main(){
    int s,t,n;
    cin >> s >> t >> n;
    int x = lcm(s,t);
    if(n%x == 0){
        cout << n << endl;
    }
    else{
        int s = n/x+1;
        cout << s*x << endl;
    }
}

```
解くのにかかった時間：10分59秒


###B


```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>;
using pil = pair<pii,int>;

int main(){
    string s;
    cin >> s;
    int t;
    cin >> t;
    set<string> a;
    if(t <= s.size()){
        string b;
        rep(i,s.size()-t+1){
            b = s.substr(i,t);
            a.insert(b);
        }
    }
    cout << a.size() << endl;
}

```
解くのにかかった時間：66分24秒
感想：今回始めてsetの存在を知りました。重複存在がある可能性があるときに使うと便利そうです。



##[ABC122_C](https://atcoder.jp/contests/abc122/tasks/abc122_c)

```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>;

int main(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> sum(n+1);
    for(int i = 1;i < n;i++){
        sum[i+1] = sum[i];
        if(s[i-1] == 'A' && s[i] == 'C')sum[i+1]++;
    }
    rep(i,q){
        int l,r;
        cin >> l >> r;
        cout << sum[r] - sum[l] << endl;
    }
}

```

解くのにかかった時間：87分30秒
感想：計算量を自力で減らせなかった。


##[ABC118_C](https://atcoder.jp/contests/abc118/tasks/abc118_c)

```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>;

int main(){
    ll n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int ans = a[0];
    rep(i,n){
        ans = __gcd(ans,a[i]);
    }
    cout << ans << endl;
}

```

解くのにかかった時間：87分32秒
感想：c++14ってgcdを__gcdで書けたんですね


##[ABC117_C](https://atcoder.jp/contests/abc117)

```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>;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> x(m);
    rep(i,m)cin >> x[i];
    sort(x.begin(),x.end());
    if(n >= m){
        cout << 0 << endl;
        return 0;
    }
    vector<int> d(m-1);
    rep(i,m-1)d[i] = x[i+1] - x[i];
    sort(d.begin(),d.end());
    int ans = 0;
    rep(i,m-n) ans += d[i];
    cout << ans << endl;
}

```

解くのにかかった時間：53分34秒
感想：差を考えて行くことを思いつかなかった。


##[ABC116_C](https://atcoder.jp/contests/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>;

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int res = 0;
    while(true){
        if(*max_element(h.begin(),h.end()) == 0) break;
        int i = 0;
        while(i < n){
            if(h[i] == 0)i++;
            else{
                res++;
                while(i < n && h[i] > 0){
                    h[i]--;
                    i++;
                }
            }
        }
    }
    cout << res << endl;
}

```

解くのにかかった時間：129分20秒
感想：*max_elementを初めて知った。この解き方が一番わかり易い


###最後に
茶色diffとなると解説も難しくなってきている気がする

難易度|かかった平均時間|解けた問題数|
|:-:|---|---|
|A|13分30秒|4問中4問|
|B|13分40秒|2問中4問|