第二回日本最強プログラマー学生選手権

##[A - Competition](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_a)

O(N)
10^3 * 10^3 < 10000000
全パターンを試します。

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

int main() {
    int x, y, z;
    cin >> x >> y >> z;

    int res = 0;
    for(int i=1000000; i>=0; i--){
        if((y * z) > (i * x)){
            res = i;
            break;
        }
    }    

    cout << res << endl;

    return 0;
}
```

O(1)で回答する場合、数式は、

```txt:txt
x:y = z:i
yz = ix
yz / x = i
1円安く販売数するので。
(yz - 1) / x = i
```

の考察で導き出せます。
よってコードは、

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

int main() {
    int x, y, z;
    cin >> x >> y >> z;  

    cout << (y * z - 1) / x << endl;

    return 0;
}
```

##[B - Xor of Sequences](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_b)

O(N)
答えは、 A ∪ B - A ∩ B。
pythonだと簡単に書けます、しかしC++erなのでC++で回答。

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

int main() {
    set<int> A, B;
    int n, m;
    cin >> n >> m;

    rep(i, n){
        int a;
        cin >> a;
        A.insert(a);
    }

    rep(i, m){
        int b;
        cin >> b;
        B.insert(b);
    }

    set<int> t_union, t_intersection, res;
    set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(t_union, t_union.begin()));
    set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(t_intersection, t_intersection.begin()));
    set_difference(t_union.begin(), t_union.end(), t_intersection.begin(), t_intersection.end(), inserter(res, res.begin()));

    for(auto &itr:res){
        cout << itr << ' ';
    }

    return 0;
}
```

##[C - Max GCD 2](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_c)

O(N)
x, yについて全探索するのはできないです。
よって、gcd(x, y)の値を全探索します。
i = gcd(x, y)として、B / i - (A - 1) / iの間に２つ以上の整数が存在していた場合に判定を行います。

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

int main() {
    int A, B;
    cin >> A >> B;

    int res = 0;
    for(int i=1; i< 200001; i++){
        int cnt = B / i - (A - 1) / i;
        if(2 <= cnt){
            res = i;
        }
    }
    cout << res << endl;

    return 0;
}
```