ABC462の記録

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

1.感想

A問題
簡単
B問題
簡単
すこし時間かかったのが悲しい
C問題
簡単だな
D問題
いもす
E問題
数学だったんか
F問題
わからん
G問題
わからん

2.結果

まあいいね

3.解説

A問題 Secret Numbers

isdigitというのがあるのでそれを使う

S = list(input())
ans = []

for c in S:
    if c.isdigit():
        ans.append(c)

print(''.join(ans))

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

int main(){
    string S, ans;
    cin >> S;

    for (char c : S){
        if (isdigit(c)){
            ans.push_back(c);
        }
    }

    cout << ans << endl;
}

B問題 Secret Numbers

cからiに辺を伸ばすグラフとして考える

N = int(input())
ans = [[] for _ in range(N)]

for i in range(N):
    k, *a = map(int, input().split())
    for x in a:
        ans[x-1].append(i+1)

for a in ans:
    a.sort()
    print(len(a), *a)

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

int main(){
    int n;
    cin >> n;
    vector<vector<int>> ans(n);

    for (int i = 0; i < n; i++){
        int k, c;
        cin >> k;
        while (k--){
            cin >> c;
            ans[c-1].push_back(i+1);
        }
    }

    for (auto& i : ans){
        sort(i.begin(), i.end());
        cout << i.size();
        for (int j : i) cout << ' ' << j;
        cout << endl;
    }
}

C問題 Not Covered Points

x座標の時にyになるという配列を用意して計算
これだと意味ないけどソートが消せる事に後から気づいた

N = int(input())
A = [-1 for i in range(N)]

for i in range(N):
    x, y = map(int, input().split())
    A[x-1] = y;

ans, mn = 0, 10**10
for i in range(N):
    if mn > A[i]:
        mn = A[i]
        ans += 1

print(ans)

#include <bits/stdc++.h>
using namespace std;
const int inf = 1<<30;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);

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

    int ans = 0, mn = inf;
    for (int i = 0; i < N; i++){
        if (mn > A[i]){
            mn = A[i];
            ans++;
        }
    }

    cout << ans << endl;
}

D問題 Accomplice

いもす法をしてnC2

N, D = map(int, input().split())
M = 1000010
A = [0]*M

for i in range(N):
    s, t = map(int, input().split())
    if t-D < s:
        continue
    A[s] += 1
    A[t-D+1] -= 1

now, ans = 0, 0
for i in range(M):
    now += A[i]
    ans += now*(now-1)//2

print(ans)

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

int main(){
    int N, D, M = 1000010;
    cin >> N >> D;
    vector<int> A(M, 0);

    for (int i = 0; i < N; i++){
        int s, t;
        cin >> s >> t;
        if (t-D < s) continue;
        A[s]++;
        A[t-D+1]--;
    }

    long now = 0, ans = 0;
    for (int i = 0; i < M; i++){
        now += A[i];
        ans += now*(now-1)/2;
    }

    cout << ans << endl;
}

E問題 Alternating Costs

場合分け
X, Yはまず絶対値にしてもいいからする
A,Bの大小関係で場合分け

for _ in range(int(input())):
    A, B, X, Y = map(int, input().split())
    X, Y = abs(X), abs(Y)
    N, P = X+Y, (X+Y)%2

    if A > B:
        print(B*N+min(2*B, A-B)*abs(X-Y+P)//2)
    elif A == B:
        print(A*N)
    else:
        print(A*N+min(2*A, B-A)*abs(X-Y-P)//2)

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

int main(){
    int T;
    cin >> T;
    while (T--){
        long A, B, X, Y;
        cin >> A >> B >> X >> Y;
        X = abs(X), Y = abs(Y);
        int N = X+Y, P = (X+Y)%2;
        if (A > B) cout << B*N+min(2*B, A-B)*abs(X-Y+P)/2 << endl;
        else if (A == B) cout << A*N << endl;
        else cout << A*N+min(2*A, B-A)*abs(X-Y-P)/2 << endl;
    }
}