AtCoder 生活　25日目


[前回](https://qiita.com/flandrescarlet237/items/230cd4c7e2defc211f25)
#25日目
今回は、バーチャル参加を3回しました

![スクリーンショット 2020-04-13 17.21.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/2e93c48b-9640-b3b0-cc78-1dfbe2cb4022.png)
![スクリーンショット 2020-04-13 20.16.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/a4472788-a22b-84e7-cef6-f586b3c6808a.png)
![スクリーンショット 2020-04-13 22.35.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/3d2f1134-1be4-13b5-fa16-a93e0e12e541.png)


##[ABC129](https://atcoder.jp/contests/abc129)

###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 a,b,c;
    cin >> a >> b >> c;
    int x = a+b,y = a+c,z = b+c;
    cout << min({x,y,z}) << endl;
}

```

###B


```c++

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

int main(){
    int n;
    cin >> n;
    int sum = 0;
    vector<int> w(n);
    rep(i,n){
        cin >>  w[i];
        sum += w[i];
    }
  	int ans = 2e9;
    rep(i,n){
      	int any = 0;
      	rep(j,i)any += w[j];
      	int t = abs(sum - any);
        ans = min(ans,abs(t - any));
    }
    cout << ans << endl;
}

```

###C


```c++

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> broken(n+1);
    rep(i,m) {
        int a;
        cin >> a;
        broken[a] = 1;
    }
    vector<int> dp(n+2);
    const int mod = 1000000007;
    dp[n] = 1;
    for (int i = n-1; i >= 0; i--) {
        if (broken[i]) {
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i+1] + dp[i+2]) % mod;
    }
    cout << dp[0] << endl;
     return 0;
}    

```
感想:まず動的計画法をはじめて知った。



##[ABC130](https://atcoder.jp/contests/abc130)

###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,a;
    cin >> x >> a;
    if(x < a) cout << 0 << endl;
    else cout << 10 << endl;
}

```

###B


```c++

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

int main(){
    int n,x;
    cin >> n >> x;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    int sum = 0,res = 1;
    rep(i,n+1){
        sum += sum + l[i-1];
        if(sum > x){
            cout << res << endl;
            return 0;
        }
        res++;
    }
    cout << n+1 << endl;
}

```

###C


```c++

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

int main()
{
    double w=0.0, h=0.0, x=0.0, y=0.0;
    cin >> w >> h >> x >> y;

    cout << fixed << setprecision(6) << (w*h)/2 << " ";
    if(x==w/2&&y==h/2){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
}

```
感想:勝手に長方形同士で分けるものと考えてしまっていた


##[ABC131](https://atcoder.jp/contests/abc131)

###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(){
    string s;
    cin >> s;
    rep(i,4){
        if(s[i] == s[i+1]){
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
}

```

###B


```c++

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

int main(){
    int n,l;
    cin >> n >> l;
  	int sum = 0;
    int s = 200;
    int r;
    vector<int> v(n);
    rep(i,n){
        v[i] = l;
        l++;
        sum += v[i];
        s = min(s, abs(v[i]));
        if(s == abs(v[i])) r = v[i];
    }
    cout << sum - r << endl;
}


```

###C


```c++

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

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

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

int main(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll s = lcm(c,d);
    ll x = b/c + b/d;
    ll y = (a-1)/c + (a-1)/d;
    ll z = b/s - (a-1)/s;
    cout << b-(a-1)-(x-y-z) << endl;
}


```

```c++

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



int main() {
    ll a, b, c, d;
    cin>>a>>b>>c>>d;
 
    ll cn = b / c - (a - 1) / c;
    ll dn = b / d - (a - 1) / d;
    ll g = __gcd(c, d);
    ll l = c / g * d;
    ll ln = b / l - (a - 1) / l;
    cout<<(b - a + 1) - (cn + dn - ln)<<endl;
}
```

感想:上が自力でやってうまく行かなかったものなんですが、下との違いはなんでしょうか？


##最後に
昔のC問題は、アルゴリズムの知識が必要だったりしてなかなか解けません。
ただ、あと一歩にはたどり着いてるはずなので頑張っていきたいです。