AtCoder Beginner Contest 265

## [A - Apple](https://atcoder.jp/contests/abc265/tasks/abc265_a)

パターン分け。
計算式は、

```
 N / 3 * Y + N % 3 * X
```

です。

```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 X, Y, N;
    cin >> X >> Y >> N;

    if(Y / 3 < X){
        cout <<  N / 3 * Y + N % 3 * X << endl;
    }else{
        cout << N * X << endl;
    }

    return 0;
} 
```

## [B - Explore](https://atcoder.jp/contests/abc265/tasks/abc265_b)

mapを使用して、$X_{i}$の部屋になった際、$Y_{i}$を加算する。


```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, T;
    cin >> N >> M >> T;
    vector<ll> A(N);
    for(int i=0; i<N-1; i++) cin >> A[i];

    map<ll, ll> mp; 
    for(int i=0; i<M; i++){
        int x, y;
        cin >> x >> y;
        mp[x] = y;
    }

    for(int i=0; i<N; i++){
        T += mp[i+1];
        T -= A[i];

        if(T<=0){
            cout << "No" << endl; 
            return 0;
        }
    }
    cout << "Yes" << endl; 

    return 0;
} 
```

## [C - Belt Conveyor](https://atcoder.jp/contests/abc265/tasks/abc265_c)

シミュレートします。
無限に続くかは同じルートを通るかにて判断をします。

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

char G[510][510];
bool visible[510][510];

int main() {
    int H, W;
    cin >> H >> W;

    for(int i=1; i<=H; i++){
        string S;
        cin >> S;
        for(int j=1; j<=W; j++){
            G[i][j] = S[j-1];
        }
    }

    bool ok=false;
    int x=1, y=1, cnt=0;
    while(!ok){
        if(visible[y][x]){
            cout << -1 << endl;
            return 0;
        }
        visible[y][x] = true;
        if(G[y][x] == 'U' && y != 1){
            y--;
        }else if(G[y][x] == 'D' && y != H){
            y++;
        }else if(G[y][x] == 'L' && x != 1){
            x--;
        }else if(G[y][x] == 'R' && x != W){
            x++;
        }else{
            ok = true;
            break;
        }
    }
    cout << y << ' ' << x << endl;

    return 0;
} 
```

## [D - Iroha and Haiku (New ABC Edition)](https://atcoder.jp/contests/abc265/tasks/abc265_d)

二分探索と累積和を使用する複数アルゴリズムの問題です。
累積和を使用して$A_x$から$A_{y-1}$までの合計を求めます。
事前に計算量を減らします。

- $A_x$から$A_{y-1}$
- $A_y$から$A_{z-1}$
- $A_z$から$A_{w-1}$

の制約なので、xからwまで連続したインデックスになります。
$A_0$から$A_{x-1}$の加算を行うとP、Q、Rと判定を行いやすくなります。

```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, P, Q, R;
    cin >> N >> P >> Q >> R;

    set<ll> st;
    st.insert(0);
    ll sum = 0;   
    for(int i=0; i<N; i++){
        ll a;
        cin >> a;
        sum += a;
        st.insert(sum);
    }

    for(auto x:st){
        if(st.find(x+P) != st.end() && st.find(x+P+Q) != st.end() && st.find(x+P+Q+R) != st.end()){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
} 
```