AtCoder Beginner Contest 185



###[A - ABC Preparation](https://atcoder.jp/contests/abc185/tasks/abc185_a)

O(1)

```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 argc, const char * argv[]) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
 
    cout << min(min(a, b), min(c, d)) << endl;
 
    return 0;
}
```

###[B - Smartphone Addiction](https://atcoder.jp/contests/abc185/tasks/abc185_b)

tが10^9、配列を使用し時間１ずつ計測をしていくのは配列が用意できないためできない。
M１０００を基準にしO(1000)なら大丈夫なので、カフェの滞在時間を基準にして計測する。

```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 argc, const char * argv[]) {
    int n, m, t;
    cin >> n >> m >> t;
 
    vector<double> a(m);
    vector<double> b(m);
 
    double res=n;
    double now=0;
    bool is_0 = false;
    rep(i, m){
        cin >> a[i] >> b[i];
 
        res -= (a[i] - now);
        now = b[i];
        if(res <= 0){
            is_0 = true;
            break;
        }
        res += (b[i] - a[i]);
        res = min(n, res);
    }
    if(now<t && is_0==false){
        res -= (t - now);
        if(res <= 0) is_0 = true;
    }
 
    if(is_0) cout << "No" << endl;
    else cout << "Yes" << endl;
 
    return 0;
}
```

###[C - Duodecim Ferra](https://atcoder.jp/contests/abc185/tasks/abc185_c)

長さLの丸太を１１分割する方法はL-1C１１の計算になります。
２００ー１C１１は桁数が多いのでpythonを使用します。

```python:python
L = int(input())
cnt = 1
r = 1
while cnt<=11:
   r = r * cnt
   cnt = cnt + 1
cnt = 1
res = 1
while cnt<=11:
   res = res * (L - cnt)
   cnt = cnt + 1
res = res // r
print(res)
```

###[D - Stamp](https://atcoder.jp/contests/abc185/tasks/abc185_d)

計算量はO(２＊M)、O(N)である。
もっとも幅の狭いkを計測。
各幅ごとにkの商を加算、余りがある場合は＋１を行う。
全てのMの要素を処理後、最後のマスと処理を行う。

```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(void) {
    int n, m;
    cin >> n >> m;

    vector<int> a(m);
    rep(i, m) cin >> a[i];

    sort(a.begin(), a.end());

    int d=n;
    int now=0;
    rep(i, m){
        if(a[i]-now-1 > 0) d = min(d, a[i]-now-1);
        now = a[i];
    }

    now = 0;
    int res = 0;
    rep(i, m){
        if(a[i]-now-1 > 0){
            res += (a[i]-now-1) / d;
            if((a[i]-now-1) % d != 0) res++;
        } 
        now = a[i];
    }
    if(n-now > 0){
            res += (n-now) / d;
            if((n-now) % d != 0) res++;
    } 
    cout << res << endl;

    return 0;
}
```

解説の記載。
for(int w:s) は綺麗に見えて良いなと思いました。
これから使っていきます。
また、切り上げ（w＋k−１）/kは初めて知りました。

```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(void) {
    int n, m;
    cin >> n >> m;

    vector<int> a(m);
    rep(i, m) cin >> a[i];

    sort(a.begin(), a.end());
    a.push_back(n+1);

    int cur=1;
    vector<int> s;
    rep(i, m+1){
        int k = a[i]-cur;
        if(k > 0) s.push_back(k);
        cur = a[i]+1;
    }

    int k=n;
    for(int w:s) k = min(k, w);
    int res = 0;
    for(int w:s) res += (w + k - 1) / k;
    cout << res << endl;

    return 0;
}
```