Zenn
🔵

【ABC347】AtCoder Beginner Contest 347【C++】

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

コンテスト名

AtCoder Beginner Contest 347

コンテストURL

https://atcoder.jp/contests/abc347

開催日

2024/03/30 21:00-22:40

A: Divisible

解法

  • 問題文通りに実装する
ABC347A.cpp
#include <iostream>
using namespace std;

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

    int a, cnt = 0;
    for(int i=0; i<n; i++){
        cin >> a;
        if(a%k==0){
            if(cnt){
                cout << " ";
            }
            cout << a/k;
            cnt++;
        }
    }

    cout << endl;
    return 0;
}

B: Substring

解法

  • substr() で部分文字列をすべて求めて unordered_set<string> で重複を除く
ABC347B.cpp
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main(){
    string s;
    cin >> s;

    unordered_set<string> S;
    for(int i=0; i<s.size(); i++){
        for(int j=1; i+j-1<s.size(); j++){
            S.insert(s.substr(i, j));
        }
    }

    cout << S.size() << endl;
    return 0;
}

C: Ideal Holidays

解法

  • 各 D_i に対して mod (A + B) をとる
  1. 最小値と最大値の差が A 日におさまるかを確かめる
    • 週をまたぐケースは +A して対処する
  2. 予定がない日が連続して B 日以上あるかを確かめる
    • 週をまたぐケースは 2 週分考えることで対処する
ABC347C_1.cpp
#include <iostream>
#include <algorithm>
using namespace std;

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

    int d;
    int minv = a+b, maxv = 0, minv2 = a+b, maxv2 = 0;
    for(int i=0; i<n; i++){
        cin >> d;
        minv = min(minv, d%(a+b));
        maxv = max(maxv, d%(a+b));
        minv2 = min(minv2, (d+a)%(a+b));
        maxv2 = max(maxv2, (d+a)%(a+b));
    }

    if(maxv-minv<a || maxv2-minv2<a){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
ABC347C_2.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<long long int> D(2*n);
    for(int i=0; i<n; i++){
        cin >> D[i];
        D[i] %= (a + b);
        D[i+n] = D[i] + a + b;
    }

    sort(D.begin(), D.end());
    for(int i=0; i<D.size()-1; i++){
        if(D[i+1]-D[i]>b){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

D: Popcount and XOR

解法

  • C の i 桁目が 1 ならば X の i 桁目か Y の i 桁目の一方が 1 で他方が 0
  • C の i 桁目が 0 ならば X の i 桁目と Y の i 桁目の両方が 1 か両方が 0
  • 1LL に注意する
  • XOR は可換
  • 0 \leqq X, Y, C < 2^{60} より 60 桁までだから a + b + popcount(C) \leqq 120
  • X \oplus Y = C より popcount(C) \leqq a + b, a \leqq b + popcount(C), b \leqq popcount(C) + a
  1. C の 1 である桁を X か Y のいずれかに 1 として振り分ける
  2. X と Y が未完成ならば C の 0 である桁を X と Y の両方に 1 として振り分ける
ABC347D.cpp
#include <iostream>
using namespace std;

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

    int cnt = 0;
    for(int i=0; i<60; i++){
        if(c & (1LL<<i)){
            cnt++;
        }
    }
    
    int diff = (a + b) - cnt;
    if(diff%2!=0 || a+b+cnt>120 || a>b+cnt || b>a+cnt || cnt>a+b){
        cout << -1 << endl;
        return 0;
    }
    diff /= 2;

    long long int x = 0, y = 0;
    cnt = 0;
    for(int i=0; i<60; i++){
        if(c & (1LL<<i)){
            x += (1LL<<i);
            if(cnt<(b-diff)){
                y += (1LL<<i);
            }
            cnt++;
        }
    }

    x -= y;

    long long int z = 0;
    cnt = 0;
    for(int i=0; i<60; i++){
        if(cnt==diff){
            break;
        }
        if(!(c & (1LL<<i))){
            z += (1LL<<i);
            cnt++;
        }
    }

    x += z;
    y += z;

    cout << x << " " << y << endl;

    return 0;
}

E: Set Add Query

解法

  • 累積和
  • 先に集合 S の要素の増減を unordered_set<int> でシミュレーションする
  • 各値の追加と削除を vector<vector<int>> に記録する
  • 最後まで集合 S に含まれていた値の計算に注意する
    • Q + 1 個目のクエリで削除されたものと考える
ABC347E.cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

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

    vector<long long int> A(n), X(q);
    for(int i=0; i<q; i++){
        cin >> X[i];
        X[i]--;
    }

    unordered_set<int> S;
    vector<vector<int>> V(n);
    vector<long long int> cnt(q+1);
    for(int i=0; i<q; i++){
        if(S.count(X[i])){
            S.erase(X[i]);
            V[X[i]].push_back(i);
        }else{
            S.insert(X[i]);
            V[X[i]].push_back(i);
        }
        cnt[i+1] = S.size();
    }

    for(int i=0; i<n; i++){
        if(V[i].size()%2==1){
            V[i].push_back(q);
        }
    }

    for(int i=0; i<q; i++){
        cnt[i+1] += cnt[i];
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<V[i].size(); j+=2){
            A[i] += (cnt[V[i][j+1]]-cnt[V[i][j]]);
        }
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }
    
    cout << endl;
    return 0;
}

Discussion