AtCoder Beginner Contest 366

## [A - Election 2](https://atcoder.jp/contests/abc366/tasks/abc366_a)

O(1)

abs(T - A) の値が、 N - (T + A)より大きい時に勝敗が確定しています。

```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, T, A;
    cin >> N >> T >> A;

    if(abs(T - A) > N - (T + A)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [B - Vertical Writing](https://atcoder.jp/contests/abc366/tasks/abc366_b)

O(N)
配列を右へ90度の回転を行う。
y軸をi, x軸をjとした時、
元の２次元配列Sと回転後の２次元配列Tの関係は、

```
T[j][N-i-1] = S[i][j];
```

となる。
回転後、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 N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
    int M = 0;
    rep(i, N) M = max(M, (int)S[i].size());

    vector<string> T(M, string(N, '*'));
    for(int i=0; i<N; i++){
        for(int j=0; j<S[i].size(); j++){
            T[j][N-i-1] = S[i][j];
        }
    }

    for(int i=0; i<M; i++){
        while(T[i].back() == '*') T[i].pop_back();
        cout << T[i] << endl;
    }

    return 0;
} 
```

## [C - Balls and Bag Query](https://atcoder.jp/contests/abc366/tasks/abc366_c)

O(N)
データ構造の問題です。
map<int, int>を使用すると解けます。

map<int, int>をmpと宣言。
queryが1の時、
xがkeyとしてmpに存在しないなら追加して1の値を代入。
xがkeyとしてmpに存在するなら、mp[x]に1を加算。

queryが2の時、
xがkeyとしてmp[x]に1を減算。
mp[x]が0になるなら要素を削除する。

queryが3の時、
mpのサイズを出力する。

```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 Q;
    cin >> Q;

    map<int, int> mp;
    for(int i=0; i<Q; i++){
        int q, x;
        cin >> q;

        if(q == 1){
            cin >> x;
            mp[x]++;
        }
        if(q == 2){
            cin >> x;
            mp[x]--;
            if(mp[x] <= 0) mp.erase(x);
        }
        if(q == 3){
            cout << mp.size() << endl;
        }
    }

    return 0;
} 
```

## [D - Cuboid Sum Query](https://atcoder.jp/contests/abc366/tasks/abc366_d)

O(N)
3次元累積和の問題です。
配列Sに配列Aの値を代入。

```
rep(i, N) rep(j, N) rep(k, N) S[i+1][j+1][k+1] = A[i][j][k];
```

各軸毎に累積和の処理を行います。

```
rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i+1][j][k] += S[i][j][k];
rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i][j+1][k] += S[i][j][k];
rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i][j][k+1] += S[i][j][k];
```

３次元配列における値の取り出し方は、

```
rx > lx
ry > ly
rz > lz
```

とした時、

```
S[rx][ry][rz]
 - S[lx][ry][rz] - S[rx][ly][rz] + S[lx][ly][rz]
 - S[rx][ry][lz] + S[rx][ly][lz] + S[lx][ry][lz]
 - S[lx][ly][lz];
```

クエリ毎にO(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 A[101][101][101];
int S[101][101][101];

int main() {
    int N;
    cin >> N;
    rep(i, N) rep(j, N) rep(k, N) cin >> A[i][j][k];

    rep(i, N) rep(j, N) rep(k, N) S[i+1][j+1][k+1] = A[i][j][k];

    rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i+1][j][k] += S[i][j][k];
    rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i][j+1][k] += S[i][j][k];
    rep(i, N+1) rep(j, N+1) rep(k, N+1) S[i][j][k+1] += S[i][j][k];
    
    int Q;
    cin >> Q;
    vector<int> Lx(Q), Rx(Q), Ly(Q), Ry(Q), Lz(Q), Rz(Q);
    rep(i, Q) cin >> Lx[i] >> Rx[i] >> Ly[i] >> Ry[i] >> Lz[i] >> Rz[i];

    rep(i, Q){
        int lx = Lx[i] - 1;
        int rx = Rx[i];
        int ly = Ly[i] - 1;
        int ry = Ry[i];
        int lz = Lz[i] - 1;
        int rz = Rz[i];

        int ans = S[rx][ry][rz]
         - S[lx][ry][rz] - S[rx][ly][rz] + S[lx][ly][rz]
         - S[rx][ry][lz] + S[rx][ly][lz] + S[lx][ry][lz]
         - S[lx][ly][lz];
        cout << ans << endl;
    }
    
    return 0;
} 
```