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

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

### コンテストURL
https://atcoder.jp/contests/abc346

### 開催日
2024/03/23 21:00-22:40

---

## [A: Adjacent Product](https://atcoder.jp/contests/abc346/tasks/abc346_a)
**解法**
- 問題文通りに実装する

```cpp: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](https://atcoder.jp/contests/abc346/tasks/abc346_b)
**解法**
- 周期は 12
- 文字列 `wbwbwwbwbwbw` の繰り返しは `%` で対応する
- 計算量は $O(12(W + B))$

```cpp: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: Σ](https://atcoder.jp/contests/abc346/tasks/abc346_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` でキャストする

```cpp: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](https://atcoder.jp/contests/abc346/tasks/abc346_d)
**解法**
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)$

```cpp: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;
}
```

```cpp: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](https://atcoder.jp/contests/abc346/tasks/abc346_e)
**解法**
- 逆順にシミュレーションする
- `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` に注意する

```cpp: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;
}
```