AtCoder Beginner Contest 187

##[A - Large Digits](https://atcoder.jp/contests/abc187/tasks/abc187_a)

O(N)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
int sum(int a){
    int res=0;
    while(a>0){
        res += a % 10;
        a = a / 10;
    }
    return res;
}
 
int main() {
    int a, b;
    cin >> a >> b;
    cout << max(sum(a), sum(b)) << endl;
    return 0;
}
```

##[B - Gentle Pairs](https://atcoder.jp/contests/abc187/tasks/abc187_b)

j>iの制約の為、0除算にならない。
O(N^2)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
int main() {
    int n;
    cin >> n;
 
    vector<double> x(n);
    vector<double> y(n);
 
    rep(i, n) cin >> x[i] >> y[i];
 
    int res=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double m = (y[j] - y[i]) / (x[j] - x[i]);
            if(-1 <= m && m <= 1){
                res++;
            }
        }
    }
    cout << res << endl;
 
    return 0;
}
```

##[C - 1-SAT](https://atcoder.jp/contests/abc187/tasks/abc187_c)

これは数学1Aの集合の単元の問題。
多分setで解くと思いますが本番はmapで回答しました。
mapのfindを使用するために、恐らくO(NlogN)。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
void solve(vector<string> str1, vector<string> str2){
    string res = "";
    map<string, string> m;
    rep(i, str1.size()) m["!" + str1[i]] = str1[i];
 
    rep(i, str2.size()){
        if(m.find(str2[i]) != m.end()){
            res = m[str2[i]];
        }
    }
 
    if(res == "") cout << "satisfiable" << endl;
    else cout << res << endl;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<string> str1;
    vector<string> str2;
    rep(i, n){
        string s;
        cin >> s;
        if(s[0] == '!') str2.push_back(s);
        else str1.push_back(s);
    }
 
    /*rep(i, 200000){
        if(i%2==0) str2.push_back("a");
        else str1.push_back("!a");
    }*/
 
    solve(str1, str2);
 
    return 0;
}
```

##[D - Choose Me](https://atcoder.jp/contests/abc187/tasks/abc187_d)

数学の単元的には整数の性質の分野。
高橋が演説した際の増減数は、青木派*２＋高橋派になります。
ラムダ式による複数要素のソート、その後は貪欲法で回答できます。
恐らくO(NlogN)。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
ll aoki_sum=0;
ll takahashi_sum=0;
 
void solve(int n, vector<P> AB){
 
    sort(AB.begin(), AB.end(), []( const auto &x, const auto &y )
    {
        return get<0>( x ) * 2 + get<1>( x ) == get<0>( y ) * 2 + get<1>( y ) ?
        get<0>( x ) * 2 + get<1>( x ) > get<0>( y ) * 2 + get<1>( y ):
        get<0>( x ) * 2 + get<1>( x ) < get<0>( y ) * 2 + get<1>( y ) ;
    });
 
    int res=0;
    for(int i = AB.size()-1; i>=0; i--){
        aoki_sum = aoki_sum - AB[i].first;
        takahashi_sum += AB[i].first + AB[i].second;
        if(takahashi_sum>aoki_sum){
            res = AB.size() - i;
            break;
        }
    }
    cout << res << endl;
}
 
int main() {
    int n;
    cin >> n;
    //n = 200000;
 
    vector<P> AB(n);
    rep(i, n){
        cin >> AB[i].first >> AB[i].second;
        aoki_sum += AB[i].first;
    }
    /*rep(i, n){
        AB[i].first = 1000000000; 
        AB[i].second = 1000000000;
        aoki_sum += AB[i].first;
    }*/
 
    solve(n, AB);
 
    return 0;
}
```

上記が本番中の提出コード。
waが８個ほど発生します。
エスパーでint型をlong long型にするとACになると分かりました。
しかし、どこが原因でオーバーフローしてるか証明できないので提出せずに考察。
そのままタイプアップ、コンテスト終了後から３分後に見つけました。

```C++:C++
    sort(AB.begin(), AB.end(), []( const auto &x, const auto &y )
    {
        return get<0>( x ) * 2 + get<1>( x ) == get<0>( y ) * 2 + get<1>( y ) ?
        get<0>( x ) * 2 + get<1>( x ) > get<0>( y ) * 2 + get<1>( y ):
        get<0>( x ) * 2 + get<1>( x ) < get<0>( y ) * 2 + get<1>( y ) ;
    });
```

問題の箇所はここです。
青木派*２＋高橋派のソートはMAXで3*10^9になります。
これはint型の最大値を超えオーバーフローします。
時間内に証明できなかったので実力不足でした。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<ll,ll>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
ll aoki_sum=0;
ll takahashi_sum=0;
 
void solve(int n, vector<P> AB){
 
    sort(AB.begin(), AB.end(), []( const auto &x, const auto &y )
    {
        return get<0>( x ) * 2 + get<1>( x ) == get<0>( y ) * 2 + get<1>( y ) ?
        get<0>( x ) * 2 + get<1>( x ) > get<0>( y ) * 2 + get<1>( y ):
        get<0>( x ) * 2 + get<1>( x ) < get<0>( y ) * 2 + get<1>( y ) ;
    });
 
    int res=0;
    for(int i = AB.size()-1; i>=0; i--){
        aoki_sum = aoki_sum - AB[i].first;
        takahashi_sum += AB[i].first + AB[i].second;
        if(takahashi_sum>aoki_sum){
            res = AB.size() - i;
            break;
        }
    }
    cout << res << endl;
}
 
int main() {
    int n;
    cin >> n;
    //n = 200000;
 
    vector<P> AB(n);
    rep(i, n){
        cin >> AB[i].first >> AB[i].second;
        aoki_sum += AB[i].first;
    }
    /*rep(i, n){
        AB[i].first = 1000000000; 
        AB[i].second = 1000000000;
        aoki_sum += AB[i].first;
    }*/
 
    solve(n, AB);
 
    return 0;
}
```

pairの型をlong long型へ変更してAC。
自分の納得いく形で茶色へいきたいので１０回ぐらい入茶を逃してる。
エスパーしてもいいのかなあ。

##まとめ
２週間ほど数学１Aの教科書、白チャートを読み続けました。
プログラムは触ってませんがレベルアップしてるのが分かりました。
自分に足りないのは数学ですね。