AtCoder Beginner Contest 181

##[A - Heavy Rotation](https://atcoder.jp/contests/abc181/tasks/abc181_a)

問題文から奇数、偶数で判定を行うのが分かります。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    if(n%2==0) cout << "White" << endl;
    else cout << "Black" << endl;
    
    return 0;
}
```

##[B - Trapezoid Sum](https://atcoder.jp/contests/abc181/tasks/abc181_b)

Nは10^5として、計算量はO(N^2)。
C++なら間に合うと思いそのまま書きました。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    int a, b;
    ll ans=0;
    rep(i, n){
        cin >> a >> b;
        
        for(int j=a; j<=b; j++){
            ans += j;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}
```

1以上x以下の全ての整数の和はx(x+1)/2で求めることができます。
1以上x-1以下の全ての整数の和はx(x-1)/2で求めることができます。
aからbの間の整数の和は、(x(x+1)/2) - x(x-1)/2で求める事ができます。
正しい回答は、

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    ll ans=0;
    rep(i, n){
        int a, b;
        cin >> a >> b;
        
        ans += b*(b+1)/2 - a*(a-1)/2;
    }
    cout << ans << endl;
    
    return 0;
}
```


##[C - Collinearity](https://atcoder.jp/contests/abc181/tasks/abc181_c)

傾きで判定すると０除算になり９０分ほどハマりました。
三角形の面積が0の時に３点は同じ直線上にあリます。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    int a, b, ans=0;
    vector<P> p;
    rep(i, n){
        cin >> a >> b;
        p.push_back(P(a, b));
    }
    
    
    for(int a=0; a<n-2; a++){
        for(int b=a+1; b<n-1; b++){
            for(int c=b+1; c<n; c++){
                if((p[b].first - p[a].first) * (p[c].second - p[a].second) - (p[b].second - p[a].second) * (p[c].first - p[a].first) == 0){
                    ans=1;
                    break;
                }
            }
        }
    }
    
    if(ans==1) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}
```

解説によると０除算は式の変換により対応できる。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    int a, b, ans=0;
    vector<P> p;
    rep(i, n){
        cin >> a >> b;
        p.push_back(P(a, b));
    }
    
    
    for(int a=0; a<n-2; a++){
        for(int b=a+1; b<n-1; b++){
            for(int c=b+1; c<n; c++){
                int x1 = p[b].first - p[a].first;
                int x2 = p[c].first - p[a].first;
                int y1 = p[b].second - p[a].second;
                int y2 = p[c].second - p[a].second;
                
                if(y1*x2==y2*x1){
                    ans=1;
                    break;
                }
            }
        }
    }
    
    if(ans==1) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}
```

##[D - Hachi](https://atcoder.jp/contests/abc181/tasks/abc181_d)

8の倍数である条件は、下３桁が８の倍数である事。
１桁、２桁、３桁の処理を個別に記載します。
配列に使える数字の数をカウントします。
112から１０００まで８の倍数でループし、３桁から各桁を取り出し必要な数字が必要な数だけあるか判定します。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
bool solve(string s){
    if(s.size() == 1) return s == "8";
    if(s.size() == 2){
        if(stoi(s) % 8 == 0) return true;
        swap(s[0], s[1]);
        return stoi(s) % 8 == 0;
    }
    vector<int> cnt(10);
    for(char x:s) cnt[x - '0']++;
    for(int i=112; i<1000; i+=8){
        auto c = cnt;
        for(char x:to_string(i)) c[x - '0']--;
        if(all_of(c.begin(), c.end(), [](int x){return x>=0;})) return true;
    }
    
    return  false;
}
 
int main(int argc, const char * argv[]) {
    string s;
    cin >> s;
    
    map<char, int> m;
    rep(i, s.length()){
        m[s[i]]++;
    }
 
    cout << (solve(s) ? "Yes" : "No") << endl;
    
    return 0;
}
```