Zenn
🔵

【ABC366】AtCoder Beginner Contest 366【C++】

2024/08/12に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 366

コンテストURL

https://atcoder.jp/contests/abc366

開催日

2024/08/10 21:00-22:40

A: Election 2

解法

  • 一方が有効票の半分より多く得票していれば、勝敗が確定している
ABC366A.cpp
#include <iostream>
using namespace std;

int main(){
    int n, t, a;
    cin >> n >> t >> a;

    if(t>n/2 || a>n/2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Vertical Writing

解法

  • 縦書きにしたとき、各行について各列の文字列が終わっていないならば、そのまま出力する
  • 縦書きにしたとき、各行について各列の文字列が終わっていれば、その列の右側にある文字列の長さによって場合分けする
    • その列の右側にある文字列のうち、一つでも終わっていない文字列があるならば、 * を出力する
    • その列の右側にある文字列のうち、終わっていない文字列が一つもないならば、何も出力しない
ABC366B.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<string> S;
    string s;
    int maxv = 0;
    for(int i=0; i<n; i++){
        cin >> s;
        S.push_back(s);
        maxv = max(maxv, (int)s.size());
    }

    for(int i=0; i<maxv; i++){
        for(int j=n-1; j>=0; j--){
            if(S[j].size()>=i+1){
                cout << S[j][i];
            }else{
                if(j==0){
                    continue;
                }

                bool flag = false;
                for(int k=j-1; k>=0; k--){
                    if(S[k].size()>=i+1){
                        flag = true;
                    }
                }
                
                if(flag){
                    cout << "*";
                }else{
                    break;
                }
            }
        }
        cout << endl;
    }

    return 0;
}

C: Balls and Bag Query

解法

  • 種類数が増減するかを毎回判定して記録する
    • 種類数が増えるのは、袋に一つもなかった種類のボールを入れるとき
    • 種類数が減るのは、袋に一つしかなかった種類のボールを捨てるとき
  • 各整数の袋の中にあるボール数は map<int, int> で管理する
ABC366C.cpp
#include <iostream>
#include <map>
using namespace std;

int main(){
    int q;
    cin >> q;

    map<int, int> M;
    int num, x;
    int cnt = 0;
    for(int i=0; i<q; i++){
        cin >> num;

        if(num==1){
            cin >> x;
            if(M[x]==0){
                cnt++;
            }
            M[x]++;
        }else if(num==2){
            cin >> x;
            if(M[x]==1){
                cnt--;
            }
            M[x]--;
        }else if(num==3){
            cout << cnt << endl;
        }
    }

    return 0;
}

D: Cuboid Sum Query

解法

  • 3 次元累積和を求める
ABC366D.cpp
#include <iostream>
#include <vector>
using namespace std;

int sumcalc(const vector<vector<vector<int>>>& S, int x1, int y1, int z1, int x2, int y2, int z2){
    return S[x2][y2][z2] - S[x1-1][y2][z2] - S[x2][y1-1][z2] - S[x2][y2][z1-1] + S[x1-1][y1-1][z2] + S[x1-1][y2][z1-1] + S[x2][y1-1][z1-1] - S[x1-1][y1-1][z1-1];
}

int main(){
    int n;
    cin >> n;

    vector<vector<vector<int>>> G(n, vector<vector<int>>(n, vector<int>(n)));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                cin >> G[i][j][k];
            }
        }
    }

    vector<vector<vector<int>>> S(n+1, vector<vector<int>>(n+1, vector<int>(n+1)));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                S[i+1][j+1][k+1] = G[i][j][k] + S[i][j+1][k+1] + S[i+1][j][k+1] + S[i+1][j+1][k] - S[i][j][k+1] - S[i][j+1][k] - S[i+1][j][k] + S[i][j][k];
            }
        }
    }

    int q;
    cin >> q;
    int x1, x2, y1, y2, z1, z2;
    for(int i=0; i<q; i++){
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        cout << sumcalc(S, x1, y1, z1, x2, y2, z2) << endl;
    }

    return 0;
}

E: Manhattan Multifocal Ellipse

解法

  • x と y は別々に考える
  • ありうる範囲は -2 \times 10^6 \leqq x, y \leqq 2 \times 10^6
  • ありうる範囲の各 x 、各 y について、 \sum\limits_{i=1}^N |x - x_i| 、 \sum\limits_{i=1}^N |y - y_i| を求めて vector<long logn int> にそれぞれ記録する
  • 条件を満たす x と y の組み合わせを二分探索で求める
ABC366E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int n, d;
    cin >> n >> d;

    vector<int> X(n), Y(n);
    long long int xsum = 0, ysum = 0;
    for(int i=0; i<n; i++){
        cin >> X[i] >> Y[i];
        xsum += abs(X[i]+2000000);
        ysum += abs(Y[i]+2000000);
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    vector<long long int> Xdiff(2*2000000+1), Ydiff(2*2000000+1);
    Xdiff[0] = xsum;
    Ydiff[0] = ysum;
    int num = -1999999;
    int left = 0;
    int j = 0;
    for(int i=1; i<2*2000000+1; i++){
        if(j<n && X[j]==num){
            int cnt = 0;
            while(j<n && X[j]==num){
                j++;
                cnt++;
            }
            Xdiff[i] = Xdiff[i-1] + left - (n - left);
            left += cnt;
        }else{
            Xdiff[i] = Xdiff[i-1] + left - (n - left);
        }

        num++;
    }

    num = -1999999;
    left = 0;
    j = 0;
    for(int i=1; i<2*2000000+1; i++){
        if(j<n && Y[j]==num){
            int cnt = 0;
            while(j<n && Y[j]==num){
                j++;
                cnt++;
            }
            Ydiff[i] = Ydiff[i-1] + left - (n - left);
            left += cnt;
        }else{
            Ydiff[i] = Ydiff[i-1] + left - (n - left);
        }

        num++;
    }

    sort(Xdiff.begin(), Xdiff.end());
    sort(Ydiff.begin(), Ydiff.end());

    long long int ans = 0;
    for(int i=0; i<2*2000000+1; i++){
        if(d-Xdiff[i]<Ydiff[0]){
            break;
        }else{
            int cnt = upper_bound(Ydiff.begin(), Ydiff.end(), d-Xdiff[i]) - Ydiff.begin();
            ans += cnt;
        }
    }

    cout << ans << endl;
    return 0;
}

Discussion