ABC455の記録

AtCoderBeginnerContest455の感想と自分が解いたところまでの解説を書いていきます
今回はA,B,C,E,FをC++,をA,Bをpythonで解きます
AtCoder Beginner Contest 455

1.感想

A問題
やるだけ
B問題
少しめんどくさい
C問題
やるだけ
D問題
分からん
E問題
包除原理だなこれ
F問題
初のF
遅延セグ木にsturct入れるだけ
G問題
みてない

2.結果

+40いいね

3.解説

A問題455

a, b, cを入力してから確かめる

pythonでの例

a, b, c = map(int, input().split())
if a != b and b == c:
    print("Yes")
else:
    print("No")

C++での例

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if (a != b && b == c) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B問題Spiral Galaxy

入力してからたしかめる

pythonでの例

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 0
for a in range(0, H):
    for b in range(a, H):
        for c in range(0, W):
            for d in range(c, W):
                ok = True
                for i in range(a, b+1):
                    for j in range(c, d+1):
                        if S[i][j] != S[a+b-i][c+d-j]:
                            ok = False
                if ok:
                    ans += 1

print(ans)

C++での例

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

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto& s : S) cin >> s;

    int ans = 0;
    for (int a = 0; a < H; a++) for (int b = a; b < H; b++){
        for (int c = 0; c < W; c++) for (int d = c; d < W; d++){
            bool ok = true;
            for (int i = a; i <= b; i++) for (int j = c; j <= d; j++){
                if (S[i][j] != S[a+b-i][c+d-j]) ok = false;
            }
            if (ok) ans++;
        }
    }

    cout << ans << endl;
}

C問題Vanish

mapで値と個数を管理してから
それをかけてソートして
空になるかK回になるか

C++での例

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

int main(){
    int N, K;
    cin >> N >> K;
    map<long, int> mp;
    for (int i = 0; i < N; i++){
        int x;
        cin >> x;
        mp[x]++;
    }

    vector<long> A;
    for (auto [a, b] : mp) A.push_back(a*b);
    sort(A.begin(), A.end());
    while (!A.empty() && K--) A.pop_back();

    long ans = 0;
    for (int i : A) ans += i;
    cout << ans << endl;
}

E問題Unbalanced ABC Substrings

A,B,Cでそれぞれ累積和と取ってからA-B,B-C,C-Aを求める

C++での例

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

template <typename T> long F(const vector<T>& v){
    map<T, long> mp;
    long res = 0;
    for (auto i : v) res += mp[i]++;
    return res;
}

int main(){
    long N;
    string S;
    cin >> N >> S;
    vector<int> A(N+1, 0), B(N+1, 0), C(N+1, 0);
    for (int i = 0; i < N; i++){
        A[i+1] = A[i]+(S[i] == 'A');
        B[i+1] = B[i]+(S[i] == 'B');
        C[i+1] = C[i]+(S[i] == 'C');
    }

    vector<int> ab(N+1), bc(N+1), ca(N+1);
    vector<pair<int, int>> abc(N+1);
    for (int i = 0; i <= N; i++){
        ab[i] = A[i]-B[i];
        bc[i] = B[i]-C[i];
        ca[i] = C[i]-A[i];
        abc[i] = {ab[i], bc[i]};
    }

    cout << ((N*N+N)/2)-F(ab)-F(bc)-F(ca)+2*F(abc) << endl;
}

F問題Merge Slimes 2

遅延セグ木
$x=\sum_{i=l}^{r}A[i]$
$y=\sum_{i=l}^{r}A[i]^2$
$ans = \frac{x^2-y}{2}$
となるからこれをつくる

C++での例

#include <iostream>
#include <atcoder/lazysegtree>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

struct S{
    int len;
    mint sum, sum2;
};
using F = mint;
S op(S l, S r){
    return S{
        l.len+r.len,
        l.sum+r.sum,
        l.sum2+r.sum2
    };
};
S e(){
    return S{0, 0, 0};
}
S mapp(F f, S x){
    if (f == 0) return x;
    mint a = f;
    mint sum = x.sum+a*x.len;
    mint sum2 = x.sum2+2*a*x.sum+a*a*x.len;
    return S{x.len, sum, sum2};
}
F comp(F f, F g){
    return f+g;
}
F id(){
    return 0;
}

int main(){
    int N, Q;
    cin >> N >> Q;
    lazy_segtree<S, op, e, F, mapp, comp, id> seg(vector(N, S{1, 0, 0}));
    while (Q--){
        int l, r, a;
        cin >> l >> r >> a, l--;
        seg.apply(l, r, a);
        S res = seg.prod(l, r);
        mint x = res.sum, y = res.sum2;
        cout << ((x*x-y)/2).val() << endl;
    }
}