【ABC403】AtCoder Beginner Contest 403【C++】

コンテスト名

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）

コンテストURL

開催日

2025/04/27 21:00–22:40

---

A: Odd Position Sum

解法

• for 文のカウンタを 2 ずつ増やす

ABC403A.cpp

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

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

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

    int sum = 0;
    for(int i=0; i<n; i+=2){
        sum += A[i];
    }

    cout << sum << endl;

    return 0;
}

B: Four Hidden

解法

• 全探索する

ABC403B.cpp

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

int main(){
    string t, u;
    cin >> t >> u;

    for(int i=0; i<t.size()-u.size()+1; i++){
        bool flag = true;
        for(int j=i; j<i+u.size(); j++){
            if(t[j]==u[j-i] || t[j]=='?'){
                continue;
            }else{
                flag = false;
                break;
            }
        }

        if(flag){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

C: 403 Forbidden

解法

• vector<set<int>> で各ユーザの閲覧可能なコンテストページを記録する
• 各ユーザがすべてのコンテストページの閲覧権限を付与されているかどうかは、別途 vector<int> で記録する

ABC403C.cpp

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

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

    vector<set<int>> V(n);
    vector<int> A(n);

    int num, x, y;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> x >> y;
            x--;
            y--;
            V[x].insert(y);
        }else if(num==2){
            cin >> x;
            x--;
            A[x] = 1;
        }else if(num==3){
            cin >> x >> y;
            x--;
            y--;
            if(A[x]==1){
                cout << "Yes" << '\n';
            }else if(V[x].count(y)){
                cout << "Yes" << '\n';
            }else{
                cout << "No" << '\n';
            }
        }
    }

    return 0;
}

D: Forbidden Difference

解法

• 動的計画法 (DP)
• $D$ で割った余りが同じ要素ごとに動的計画法を考える
• 各値の要素数を記録しておき、連続しないように選ぶときの最大要素数を動的計画法で求める
  • $\mathrm{dp}[k][0]$ := $k$ 番目の要素までで、 $k$ 番目の要素を選択しない場合の最大要素数
  • $\mathrm{dp}[k][1]$ := $k$ 番目の要素までで、 $k$ 番目の要素を選択する場合の最大要素数
• $D = 0$ のときは別途、処理する

ABC403D.cpp

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

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

    const int MAXA = 1000000;

    vector<int> V(MAXA+1);
    int a;
    set<int> S;
    for(int i=0; i<n; i++){
        cin >> a;
        V[a]++;
        S.insert(a);
    }

    if(d==0){
        cout << n - S.size() << endl;
        return 0;
    }

    int sum = 0;
    for(int i=0; i<d; i++){
        vector<vector<int>> dp(MAXA/d+2, vector<int>(2));
        int k = 0;
        for(int j=i; j<=MAXA; j+=d){
            dp[k+1][0] = max(dp[k][0], dp[k][1]);
            dp[k+1][1] = dp[k][0] + V[j];

            if(j+d>MAXA){
                sum += max(dp[k+1][0], dp[k+1][1]);
            }

            k++;
        }
    }

    cout << n - sum << endl;

    return 0;
}