【ABC385】AtCoder Beginner Contest 385【C++】

コンテスト名

ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）

コンテストURL

開催日

2024/12/21 21:00-22:40

---

A: Equally

解法

• グループの分け方をすべて調べる

ABC385A.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;

    if(a==b && b==c){
        cout << "Yes" << endl;
        return 0;
    }

    if(a+b==c || a+c==b || b+c==a){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;
    return 0;
}

B: Santa Claus 1

解法

• 問題文通りにシミュレーションする
• 通過または到着した家は set<pair<int, int>> に記録する

ABC385B.cpp

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int main(){
    int h, w, x, y;
    cin >> h >> w >> x >> y;
    x--;
    y--;

    vector<vector<char>> S(h, vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> S[i][j];
        }
    }

    string t;
    cin >> t;

    set<pair<int, int>> st;
    for(int i=0; i<t.size(); i++){
        if(t[i]=='U'){
            if(S[x-1][y]=='.'){
                x--;
            }else if(S[x-1][y]=='@'){
                x--;
                st.insert({x, y});
            }
        }else if(t[i]=='D'){
            if(S[x+1][y]=='.'){
                x++;
            }else if(S[x+1][y]=='@'){
                x++;
                st.insert({x, y});
            }
        }else if(t[i]=='L'){
            if(S[x][y-1]=='.'){
                y--;
            }else if(S[x][y-1]=='@'){
                y--;
                st.insert({x, y});
            }
        }else if(t[i]=='R'){
            if(S[x][y+1]=='.'){
                y++;
            }else if(S[x][y+1]=='@'){
                y++;
                st.insert({x, y});
            }
        }
    }

    cout << x+1 << " " << y+1 << " " << st.size() << endl;

    return 0;
}

C: Illuminate Buildings

解法

• 間隔、先頭について全探索する
• 間隔 $X$ のときについて、先頭が $1$ のときから $X$ のときまで調べればよい
  • 間隔 $X$ のときについての計算量は $\mathcal{O}(\frac{N}{X} \times X)$
• 全体の計算量は $\mathcal{O}(N^2)$

ABC385C.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> H(n);
    for(int i=0; i<n; i++){
        cin >> H[i];
    }

    int maxv = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++){
            int cnt = 1;
            for(int k=j; k+i<n; k+=i){
                if(H[k+i]==H[k]){
                    cnt++;
                }else{
                    maxv = max(maxv, cnt);
                    cnt = 1;
                }
            }
            maxv = max(maxv, cnt);
        }
    }

    cout << maxv << endl;

    return 0;
}

参考

D: Santa Claus 2

解法

• 二分探索
• map<long long int, set<long long int>> で家の位置を $x$ 軸方向と $y$ 軸方向について管理する
• 通過または到着した家は削除する

ABC385D.cpp

#include <iostream>
#include <set>
#include <map>
using namespace std;

int main(){
    long long int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;

    map<long long int, set<long long int>> MX;
    map<long long int, set<long long int>> MY;
    int x, y;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        MX[x].insert(y);
        MY[y].insert(x);
    }

    char d;
    long long int c;
    int cnt = 0;
    for(int i=0; i<m; i++){
        cin >> d >> c;
        if(d=='U'){
            auto it = MX[sx].lower_bound(sy);
            while(it!=MX[sx].end() && *it<=sy+c){
                MY[*it].erase(sx);
                MX[sx].erase(it++);
                cnt++;
            }
            sy += c;
        }else if(d=='D'){
            auto it = MX[sx].lower_bound(sy-c);
            while(it!=MX[sx].end() && *it<=sy){
                MY[*it].erase(sx);
                MX[sx].erase(it++);
                cnt++;
            }
            sy -= c;
        }else if(d=='L'){
            auto it = MY[sy].lower_bound(sx-c);
            while(it!=MY[sy].end() && *it<=sx){
                MX[*it].erase(sy);
                MY[sy].erase(it++);
                cnt++;
            }
            sx -= c;
        }else if(d=='R'){
            auto it = MY[sy].lower_bound(sx);
            while(it!=MY[sy].end() && *it<=sx+c){
                MX[*it].erase(sy);
                MY[sy].erase(it++);
                cnt++;
            }
            sx += c;
        }
    }

    cout << sx << " " << sy << " " << cnt << endl;

    return 0;
}