【ABC344】AtCoder Beginner Contest 344【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

コンテストURL

開催日

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

---

A: Spoiler

解法

• | を通過した回数で判別する
  • 1 回目の | から 2 回目の | までは出力しない

ABC344A.cpp

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

int main(){
    string s;
    cin >> s;
    bool flag = true;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='|'){
            flag = !flag;
        }else if(flag){
            cout << s[i];
        }
    }

    cout << endl;
    return 0;
}

B: Delimiter

解法

• 0 が入力されるまで while 文で vector<int> に読み込み続ける
• 逆順に出力

ABC344B.cpp

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

int main(){
    int x;
    vector<int> V;
    do{
        cin >> x;
        V.push_back(x);
    }while(x!=0);

    for(int i=V.size()-1; i>=0; i--){
        cout << V[i] << endl;
    }

    return 0;
}

C: A+B+C

解法

• 全探索
• そのまま 4 重ループにすると計算量は $O(NMLQ)$ になってしまう
• 数列 $A, B, C$ からそれぞれ 1 個ずつ要素を選んで作成できる和を unordered_set<int> で管理する
• count(X_i) で判別する
• 計算量は $O(NML + Q)$

ABC344C.cpp

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

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

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

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

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

    int sum;
    unordered_set<int> S; 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            for(int k=0; k<l; k++){
                sum = A[i]+B[j]+C[k];
                S.insert(sum);
            }
        }
    }

    for(int i=0; i<q; i++){
        if(S.count(X[i])){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}

D: String Bags

解法

• 動的計画法 (DP)
• $dp[i][k] :=$ 袋 $i$ までを用いて文字列 $T$ の $k$ 文字目までを作成するために必要な最小の金額
• 計算量は $O(NA|T||S|)$

ABC344D.cpp

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

string t;

bool check(int num, string s){
    if(t.size()<s.size()){
        return false;
    }

    string sub = t.substr(num, s.size());
    if(sub==s){
        return true;
    }

    return false;
}

int main(){
    cin >> t;

    int n;
    cin >> n;

    const int inf = t.size()+1;
    vector<vector<int>> dp(n+1, vector<int>(t.size()+1, inf));
    dp[0][0] = 0;

    int x;
    string s;
    for(int i=0; i<n; i++){
        cin >> x;
        for(int k=0; k<=t.size(); k++){
            dp[i+1][k] = dp[i][k];
        }
        for(int j=0; j<x; j++){
            cin >> s;
            for(int k=0; k<=t.size(); k++){
                if(check(k, s)){
                    dp[i+1][k+s.size()] = min(dp[i+1][k+s.size()], dp[i][k]+1);
                }
            }
        }
    }

    if(dp[n][t.size()]<inf){
        cout << dp[n][t.size()] << endl;
    }else{
        cout << -1 << endl;
    }
    
    return 0;
}

E: Insert or Erase

解法

• 双方向連結リストを実装する
• 前の要素と後ろの要素をそれぞれ unordered_map<int, int> で管理する
• 両端の番兵には 0 を利用できる
  • 制約条件からどの時点においても $1 \leqq A_i \leqq 10^9$ であり 0 が要素になることはないため

ABC344E.cpp

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

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

    unordered_map<int, int> F, B;
    F[0] = A[0];
    F[A[n-1]] = 0;
    B[A[0]] = 0;
    B[0] = A[n-1];
    for(int i=0; i<n-1; i++){
        F[A[i]] = A[i+1];
        B[A[i+1]] = A[i];
    }

    int q;
    cin >> q;
    int num, x, y;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> x >> y;
            F[y] = F[x];
            B[F[x]] = y;
            F[x] = y;
            B[y] = x;
        }else if(num==2){
            cin >> x;
            B[F[x]] = B[x];
            F[B[x]] = F[x];
        }
    }

    int a = 0, cnt = 0;
    do{
        if(cnt){
            cout << " ";
        }
        cnt++;
        cout << F[a];
        a = F[a];
    }while(F[a]);

    cout << endl;
    return 0;
}