ABC466の記録

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

1.感想

A問題
まあそれなりに簡単かな
B問題
とりあえずmapが出てきた
配列で行けるね
C問題
急なインタラクティブだけどすぐに解けた
D問題
lazy_segtreeが一瞬考えてしまった
E問題
dp
意外と簡単だった
F問題
分からん
G問題
FPSなんかなこれは

2.結果

明日あるからまあいけるか

3.解説

A問題 Compromise

最大値が0未満ならYesじゃないならNo

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

int main(){  
    int N;  
    cin >> N;  
    vector<int> A(N);  
    for (int& x : A) cin >> x;  
    if (ranges::max(A) < 0) cout << "Yes" << endl;  
    else cout << "No" << endl;  
}  

N = int(input())  
X = list(map(int, input().split()))  
print("Yes" if max(X) < 0 else "No")  

B問題 Representative Balls

色でバケットする

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

int main(){  
    int N, M;  
    cin >> N >> M;  
    vector<int> A(M, -1);  

    for (int i = 0; i < N; i++){  
        int c, s;  
        cin >> c >> s;  
        A[c-1] = max(A[c-1], s);  
    }  

    for (int i = 0; i < M; i++) cout << A[i] << ' ';  
    cout << endl;  
}  

N, M = map(int, input().split())  
A = [-1 for i in range(M)]  

for i in range(N):  
    c, s = map(int, input().split())  
    A[c-1] = max(A[c-1], s)  

print(*A)  

C問題 Count Close Pairs

説明が難しいな
右をずらしながらやっていく

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

int main(){  
    int N;  
    cin >> N;  

    long ans = 0;  
    int r = 2;  
    for (int i = 1; i < N; i++){  
        r = max(r, i+1);  
        while (r <= N){  
            cout << "? " << i << ' ' << r << endl;  
            string s;  
            cin >> s;  
            if (s == "Yes") r++;  
            else break;  
        }  
        ans += r-i-1;  
    }  

    cout << "! " << ans << endl;  
}  

N = int(input())  

ans, r = 0, 2  
for i in range(1, N):  
    r = max(r, i+1)  
    while r <= N:  
        print("?", i, r)  
        s = input()  
        if s == "Yes":  
            r += 1  
        else:  
            break  
    ans += r-i-1  

print('!', ans)  

D問題 Placing Rooks

その行を最後に消したのがいつかを管理してそれのインデックスとが一致していたら+1

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

int main(){  
    int N, M;  
    cin >> N >> M;  
    vector<int> R(M), C(M), LR(N, -1), LC(N, -1);  

    for (int i = 0; i < M; i++){  
        cin >> R[i] >> C[i];  
        LR[--R[i]] = i;  
        LC[--C[i]] = i;  
    }  

    int ans = 0;  
    for (int i = 0; i < M; i++){  
        if (LR[R[i]] == i && LC[C[i]] == i){  
            ans++;  
        }  
    }  
    cout << ans << endl;  
}  

N, M = map(int, input().split())  
R = [-1 for i in range(M)]  
C = [-1 for i in range(M)]  
LR = [-1 for i in range(N)]  
LC = [-1 for i in range(N)]  

for i in range(M):  
    R[i], C[i] = map(lambda x: int(x)-1, input().split())  
    LR[R[i]], LC[C[i]] = i, i  

ans = 0  
for i in range(M):  
    if LR[R[i]] == i and LC[C[i]] == i:  
        ans += 1  
print(ans)  

E問題 Range Flip

ひっくり返した回数でdpをする

#include <bits/stdc++.h>  
using namespace std;  
const long INF = 4e18;  

int main(){  
    int N, K, V = 0;  
    cin >> N >> K;  
    vector<int> D(N);  

    for (int i = 0; i < N; i++){  
        int a, b;  
        cin >> a >> b;  
        V += a;  
        D[i] = b-a;  
    }  

    vector<vector<long>> dp(2*K+1, {-INF, -INF});  
    dp[0][0] = 0, dp[1][1] = D[0];  

    for (int i = 1; i < N; i++){  
        vector<vector<long>> ep(2*K+1, {-INF, -INF});  
        for (int j = 0; j <= 2*K; j++) for (int k : {0, 1}){  
            if (dp[j][k] == -INF) continue;  
            if (j+k <= 2*K) ep[j+k][0] = max(ep[j+k][0], dp[j][k]);  
            if (j-k+1 <= 2*K) ep[j-k+1][1] = max(ep[j-k+1][1], dp[j][k]+D[i]);  
        }  
        dp.swap(ep);  
    }  

    long ans = 0;  
    for (int i = 0; i <= 2*K; i++){  
        ans = max(ans, dp[i][0]);  
        if (i < 2*K) ans = max(ans, dp[i][1]);  
    }  
    cout << V+ans << endl;  
}