AtCoder Beginner Contest 365

## [A - Leap Year](https://atcoder.jp/contests/abc365/tasks/abc365_a)

O(1)

1年が366日になる条件は、
- Yが4の倍数であり、100の倍数でない
- Yが400の倍数である
この２つを判定して、それ以外を365と出力します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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 Y;
    cin >> Y;

    if(Y % 4 == 0 && Y % 100 != 0){
        cout << 366 << endl;
    }else if(Y % 400 == 0){
        cout << 366 << endl;
    }else{
        cout << 365 << endl;
    }

    return 0;
} 
```

## [B - Second Best](https://atcoder.jp/contests/abc365/tasks/abc365_b)

O(lonN)
sortの問題です。
Aの値とindexをpairで管理します。
vectotをソートして、N-2の要素が答えになります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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 N;
    cin >> N;

    vector<P> A(N);
    rep(i, N){
        int a;
        cin >> a;
        A[i] = P(a, i);
    }

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

    cout << A[N-2].second + 1 << endl;

    return 0;
} 
```

## [C - Transportation Expenses](https://atcoder.jp/contests/abc365/tasks/abc365_c)

O(NlogN)
任意のxを求める問題は二分探索です。
交通費補助額の上限額xの最大を求めましょう。

二分探索のleft、rightの範囲を決めます。
0円は範囲内としてokという変数で宣言します。
範囲外の最大値+1(A[i]の合計M + 1)をngとして変数で宣言します。

```
rep(i, N) sum += min(mid, A[i]);
```

にて、二分探索するmidとA[i]を比較して小さい値の合計sumを求めます。

```
if(sum <= M){
    ok = mid;
}else{
    ng = mid;
}
```

sum <= Mなら条件を満たしているのでokを更新。
sum > Mなら条件を満たしていないのでngを更新。
二分探索のwhileの終了条件を満たした時、答えはokに格納されています。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for(auto& a:A) cin >> a;
    sort(A.begin(), A.end());

    ll total = 0;
    rep(i, N) total += A[i];

    if(total <= M){
        cout << "infinite" << endl;
        return 0;
    }

    ll ok = 0;
    ll ng = M+1;
    while(abs(ok-ng)>1){
        ll mid = (ok + ng) / 2;
        ll sum = 0;
        rep(i, N) sum += min(mid, A[i]);

        if(sum <= M){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok << endl;

    return 0;
} 
```

## [D - AtCoder Janken 3](https://atcoder.jp/contests/abc365/tasks/abc365_d)

O(N)
動的計画法の問題です。

動的計画法で漸化式の条件は、下記になります。

```
高橋くんは青木くんに1度も負けなかった。
i=1,2,…,N−1について、高橋くんがi回目のじゃんけんに出した手とi+1回目のじゃんけんに出した手は異なる。
```

R = 0, P = 1, S = 2として、漸化式のコードを作成します。

```
rep(i, N){
    if(S[i] == 'R'){
        // 青木くんがグー（0）の時、高橋くんがパー(1)なら勝ちます。
        // 高橋くんがパーを出す時、前回の手はグーかチョキでないといけないです。
        // 前回の手がグーかチョキの要素に+1をして、勝った回数の最大値を更新します。
        dp[i+1][1] = max(dp[i][0] + 1,  dp[i][2] + 1);
        
        // 青木くんがグー（0）の時、高橋くんがグーなら引き分けます。
        // 高橋くんがグーを出す時、前回の手はパーかチョキでないといけないです。
        // 前回の手がパーかチョキの要素を、勝った回数の最大値として更新します。
        dp[i+1][0] = max(dp[i][1],  dp[i][2]);
    }
    if(S[i] == 'P'){
        dp[i+1][2] = max(dp[i][0] + 1,  dp[i][1] + 1);
        dp[i+1][1] = max(dp[i][0],  dp[i][2]);
    }
    if(S[i] == 'S'){
        dp[i+1][0] = max(dp[i][1] + 1,  dp[i][2] + 1);
        dp[i+1][2] = max(dp[i][0],  dp[i][1]);
    }
}
```

漸化式を作成したのでコードを実装します。


```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; 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 N;
    cin >> N;
    string S;
    cin >> S;

    vector<vector<int>> dp(N+1, vector<int>(3, 0));

    rep(i, N){
        if(S[i] == 'R'){
            dp[i+1][1] = max(dp[i][0] + 1,  dp[i][2] + 1);
            dp[i+1][0] = max(dp[i][1],  dp[i][2]);
        }
        if(S[i] == 'P'){
            dp[i+1][2] = max(dp[i][0] + 1,  dp[i][1] + 1);
            dp[i+1][1] = max(dp[i][0],  dp[i][2]);
        }
        if(S[i] == 'S'){
            dp[i+1][0] = max(dp[i][1] + 1,  dp[i][2] + 1);
            dp[i+1][2] = max(dp[i][0],  dp[i][1]);
        }
    }

    int ans = 0;
    rep(i, 3) ans = max(ans, dp[N][i]);
    cout << ans << endl;

    return 0;
} 
```