ABC464の記録

AtCoderBeginnerContest464の感想と自分が解いたところまでの解説を書いていきます
A,B,C,D,EをC++,をA,B,C,Dをpythonで解きます
Atcoder Beginner Contest 464

1.感想

A問題
簡単
B問題
少しめんどい
C問題
クエリは好き
D問題
DP
E問題
set
F問題
制約的に半分全列挙
G問題
しらんて

2.結果

もうすこし上がってほしかった

3.解説

A問題 Decisive Battle

Eの個数とWの個数を比べる

S = input()  
print("East" if S.count('E') >  S.count('W') else "West")  

#include <bits/stdc++.h>  
using namespace std;  

int main(){  
    string S;  
    cin >> S;  
    cout << (count(S.begin(), S.end(), 'E') > count(S.begin(), S.end(), 'W')? "East": "West") << endl;  
}  

B問題 Crop

縦横の最大最小を求めてその間を出力

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

u, d, l, r = H, -1, W, -1  
for i in range(H):  
    for j in range(W):  
        if S[i][j] == '#':  
            u = min(u, i)  
            d = max(d, i)  
            l = min(l, j)  
            r = max(r, j)  

for i in range(u, d+1):  
    print(S[i][l:r+1])  

#include <bits/stdc++.h>  
using namespace std;  

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

    int u = H, d = -1, l = W, r = -1;  
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++){  
        if (S[i][j] == '#'){  
            u = min(u, i);  
            d = max(d, i);  
            l = min(l, j);  
            r = max(r, j);  
        }  
    }  

    for (int i = u; i <= d; i++){  
        for (int j = l; j <= r; j++) cout << S[i][j];  
        cout << endl;  
    }  
}  

C問題 Plumage Palette

色が変わる時間でまとめてクエリに対する答えを出力
計算量$O(N+M)$

N, M = map(int, input().split())  
E = [[] for _ in range(M+1)]  
C = [0 for i in range(N+1)]  

for i in range(N):  
    a, d, b = map(int, input().split())  
    if d == 1:  
        C[b] += 1  
    else:  
        C[a] += 1  
        E[d].append(a, b)  

k = 0  
for i in range(N+1):  
    if C[i] > 0:  
        k += 1  
print(k)  

for i in range(2, M+1):  
    for a, b in E[i]:  
        C[a] -= 1  
        if C[a] == 0:  
            k -= 1  
        if C[b] == 0:  
            k += 1  
        C[b] += 1  
    print(k)  

#include <bits/stdc++.h>  
using namespace std;  

int main(){  
    int N, M;  
    cin >> N >> M;  
    vector<vector<pair<int, int>>> E(M+1);  
    vector<int> C(N+1, 0);  

    for (int i = 0; i < N; i++){  
        int a, d, b;  
        cin >> a >> d >> b;  
        if (d == 1){  
            C[b]++;  
        }  
        else{  
            C[a]++;  
            E[d].emplace_back(a, b);  
        }  
    }  

    int k = 0;  
    for (int i = 1; i <= N; i++) if (C[i] > 0) k++;  
    cout << k << endl;  

    for (int i = 2; i <= M; i++){  
        for (auto [a, b] : E[i]){  
            if (--C[a] == 0) k--;  
            if (C[b]++ == 0) k++;  
        }  
        cout << k << endl;  
    }  
}  

D問題 Celester

dp[i][0]をi日目に雨の最大
dp[i][1]をi日目に晴の最大
計算量$O(\sum N)$

INF = 1<<60  

for _ in range(int(input())):  
    N = int(input())  
    S = input()  
    X = list(map(int, input().split()))  
    Y = list(map(int, input().split()))  

    dp = [[-INF, -INF] for _ in range(N)]  
    for i in range(N):  
        r, s = 0, -X[i]  
        if S[i] == 'S':  
            r, s = s, r  
        if i == 0:  
            dp[0] = r, s  
        else:  
            dp[i][0] = r+max(dp[i-1][0], dp[i-1][1])  
            dp[i][1] = s+max(dp[i-1][1], dp[i-1][0]+Y[i-1])  

    print(max(dp[N-1]))  

#include <bits/stdc++.h>  
using namespace std;  
const long INF = 1LL<<60;  

int main(){  
    int T;  
    cin >> T;  
    while (T--){  
        int N;  
        string S;  
        cin >> N >> S;  
        vector<long> X(N), Y(N-1);  
        for (long& i : X) cin >> i;  
        for (long& i : Y) cin >> i;  

        vector<vector<long>> dp(N, {-INF, -INF});  
        for (int i = 0; i < N; i++){  
            long r = 0, s = -X[i];  
            if (S[i] == 'S') swap(r, s);  
            if (i == 0){  
                dp[0] = {r, s};  
            }  
            else{  
                dp[i][0] = r+max(dp[i-1][0], dp[i-1][1]);  
                dp[i][1] = s+max(dp[i-1][1], dp[i-1][0]+Y[i-1]);  
            }  
        }  

        cout << max(dp[N-1][0], dp[N-1][1]) << endl;  
    }  
}  

E問題 Fill-Rect Query

これいもす法でいけるんだ
そうしたら$O(HW+Q)$

#include <bits/stdc++.h>  
using namespace std;  

int main(){  
    int H, W, Q;  
    cin >> H >> W >> Q;  
    vector<vector<int>> A(H, vector<int>(W, 0));  
    vector<char> X{'A'};  

    for (int i = 1; i <= Q; i++){  
        int r, c;  
        char x;  
        cin >> r >> c >> x;  
        X.push_back(x);  
        A[r-1][c-1] = i;  
    }  

    for (int i = H-1; i >= 0; i--) for (int j = W-1; j >= 0; j--){  
        if (i != 0) A[i-1][j] = max(A[i][j], A[i-1][j]);  
        if (j != 0) A[i][j-1] = max(A[i][j], A[i][j-1]);  
    }  

    for (int i = 0; i < H; i++){  
        for (int j = 0; j < W; j++) cout << X[A[i][j]];  
        cout << endl;  
    }  
}