LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@testcampus

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

Posted at

コンテスト名

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

コンテストURL

開催日

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;
}
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?