Zenn
🔵

【ABC346】AtCoder Beginner Contest 346【C++】

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

コンテスト名

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

コンテストURL

https://atcoder.jp/contests/abc346

開催日

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

A: Adjacent Product

解法

  • 問題文通りに実装する
ABC346A.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];
    }

    for(int i=0; i<n-1; i++){
        if(i){
            cout << " ";
        }
        cout << A[i]*A[i+1];
    }

    cout << endl;
    return 0;
}

B: Piano

解法

  • 周期は 12
  • 文字列 wbwbwwbwbwbw の繰り返しは % で対応する
  • 計算量は O(12(W + B))
ABC346B.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    int w, b;
    cin >> w >> b;

    string s = "wbwbwwbwbwbw";

    int n = s.size();
    int cnt;
    for(int i=0; i<n; i++){
        cnt = 0;
        for(int j=0; j<w+b; j++){
            if(s[(i+j)%n]=='w'){
                cnt++;
            }
        }
        if(cnt==w){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

C: Σ

解法

  • 1 以上 K 以下で A に現れたものを unordered_set<int> で管理する
  • 1 以上 K 以下の総和 \frac{(K+1)K}{2} から unordered_set<int> の総和を引く
  • \frac{(K+1)K}{2} を計算するとき long long int でキャストする
ABC346C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

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

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

    sort(A.begin(), A.end());
    // A.erase(unique(A.begin(), A.end()), A.end());
    unordered_set<int> S;
    for(int i=0; i<n; i++){
        if(A[i]<=k){
            S.insert(A[i]);
        }else{
            break;
        }
    }

    long long int sum = (long long int)(k+1)*k/2;
    for(unordered_set<int>::iterator it=S.begin(); it!=S.end(); it++){
        sum -= *it;
    }

    cout << sum << endl;

    return 0;
}

D: Gomamayo Sequence

解法

  1. 累積和
    • 同じ文字が続く部分で 2 分割すると考える
      • ...01011010... は ...0101 と 1010... に分割して考える
    • 「偶数文字目が 0 で奇数文字目が 1 の文字列」と「偶数文字目が 1 で奇数文字目が 0 の文字列」を分割部分で合体させる
      • どこで分割すれば最小コストになるかを全探索
      • 0 始まり（偶数文字目が 0 で奇数文字目が 1 の文字列始まり）と 1 始まり（偶数文字目が 1 で奇数文字目が 0 の文字列始まり）の 2 パターンを考える
  2. 動的計画法 (DP)
    • dp[i][j][k] := i 文字目までで隣接する文字が同じである箇所が j 個ある状態で i 文字目を k に置き換えるための最小コスト
    • j と k はそれぞれ 0, 1 の 2 通りだから計算量は O(N)
ABC346D_1.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

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

    vector<long long int> SL0(n+1), SL1(n+1);
    for(int i=0; i<n; i++){
        SL0[i+1] = SL0[i];
        SL1[i+1] = SL1[i];
        if(i%2==0){
            if(s[i]!='0'){
                SL0[i+1] += C[i];
            }else{
                SL1[i+1] += C[i];
            }
        }else{
            if(s[i]!='1'){
                SL0[i+1] += C[i];
            }else{
                SL1[i+1] += C[i];
            }
        }
    }

    long long int minv = 1e15;
    for(int i=1; i<n; i++){
        minv = min(minv, SL0[i]+(SL1[n]-SL1[i]));
        minv = min(minv, SL1[i]+(SL0[n]-SL0[i]));
    }

    cout << minv << endl;
    return 0;
}
ABC346D_2.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

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

    const long long int INF = 1e15;
    vector<vector<vector<long long int>>> dp(n, vector<vector<long long int>>(2, vector<long long int>(2, INF)));
    dp[0][0][s[0]-'0'] = 0;
    dp[0][0][1-(s[0]-'0')] = C[0];
    for(int i=1; i<n; i++){
        int next = s[i] - '0';
        if(next==0){
            dp[i][0][0] = dp[i-1][0][1];
            dp[i][0][1] = dp[i-1][0][0] + C[i];
            dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][1][1]);
            dp[i][1][1] = min(dp[i-1][0][1], dp[i-1][1][0]) + C[i];
        }else if(next==1){
            dp[i][0][0] = dp[i-1][0][1] + C[i];
            dp[i][0][1] = dp[i-1][0][0];
            dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][1][1]) + C[i];
            dp[i][1][1] = min(dp[i-1][0][1], dp[i-1][1][0]);
        }
    }

    cout << min(dp[n-1][1][0], dp[n-1][1][1]) << endl;
    return 0;
}

E: Paint

解法

  • 逆順にシミュレーションする
  • unordered_map<int, long long int> で各色のマス数を管理する
  • 色が未確定（逆順にシミュレーションしたときまだ塗られていない状態：未来に上塗りされない）ならば確定する
    • A_i 行目がまだ塗られていない（上塗りされていない）ならば色 X_i で確定
    • A_i 列目がまだ塗られていない（上塗りされていない）ならば色 X_i で確定
    • vector<bool> で各行・各列が塗られているかどうかを管理する
  • 直行する方向で上塗りされている行数・列数を引く
    • A_i 行目を塗るときには未来に 1 回以上塗られる列数を W から引く
    • A_i 列目を塗るときには未来に 1 回以上塗られる行数を H から引く
    • 未来に 1 回以上塗られる行番号・列番号をそれぞれ unordered_set<int> で記録する
  • 色 0 に注意する
ABC346E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main(){
    int h, w, m;
    cin >> h >> w >> m;

    vector<int> T(m), A(m), X(m);
    int maxc = 0;
    for(int i=0; i<m; i++){
        cin >> T[i] >> A[i] >> X[i];
        A[i]--;
        maxc = max(maxc, X[i]);
    }

    unordered_map<int, long long int> CM;
    vector<bool> GM(h), RM(w);
    unordered_set<int> GS, RS;
    for(int i=m-1; i>=0; i--){
        if(T[i]==1){
            if(!GM[A[i]]){
                CM[X[i]] += w;
                GM[A[i]] = true;
                CM[X[i]] -= RS.size();
                GS.insert(A[i]);
            }
        }else if(T[i]==2){
            if(!RM[A[i]]){
                CM[X[i]] += h;
                RM[A[i]] = true;
                CM[X[i]] -= GS.size();
                RS.insert(A[i]);
            }
        }
    }

    for(int i=0; i<h; i++){
        if(!GM[i]){
            CM[0] += w;
            GM[i] = 0;
            CM[0] -= RS.size();
            GS.insert(i);
        }
    }

    int cnt = 0;
    for(int i=0; i<=maxc; i++){
        if(CM[i]){
            cnt++;
        }
    }
    cout << cnt << endl;
    for(int i=0; i<=maxc; i++){
        if(CM[i]){
            cout << i << " " << CM[i] << '\n';
        }
    }

    return 0;
}

Discussion