ABC463の記録

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

1.感想

A問題
比例式だな
B問題
比較的実装かんたんめ
C問題
ソート
D問題
にぶたん
E問題
ダイクストラ
F問題
わからんて
G問題
$\frac{1}{2^N}\sum_{k=0}^{N}\left(\begin{array}{c}N\ k\end{array}\right)|2k-N-X|$
これでTLEでそこからわからん

2.結果

AJLが心配

3.解説

A問題 16:9

$X:Y=16:9 \Leftrightarrow 9X=16Y$
これを判断する

X, Y = map(int, input().split())
print("Yes" if 9*X == 16*Y else "No")

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

int main(){
    int X, Y;
    cin >> X >> Y;
    if (9*X == 16*Y) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B問題 Train Reservation

Aだったら0,Bだったら1という感じでやる

N, X = input().split()
N = int(N)
S = [input() for _ in range(N)]
a = ord(X)-ord('A')

ok = False
for i in range(N):
    if S[i][a] == 'o':
        ok = True

print("Yes" if ok else "No")

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

int main(){
    int N;
    char X;
    cin >> N >> X;
    vector<string> S(N);
    for (auto& s : S) cin >> s;

    int a = X-'A';
    bool ok = false;
    for (int i = 0; i < N; i++){
        if (S[i][a] == 'o'){
            ok = true;
        }
    }

    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C問題 Tallest at the Moment

suffixmaxをとって二分探索

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

int main(){
    int N;
    cin >> N;
    vector<int> H(N), L(N);
    for (int i = 0; i < N; i++) cin >> H[i] >> L[i];

    vector<int> S(N);
    S[N-1] = H[N-1];
    for (int i = N-2; i >= 0; i--) S[i] = max(S[i+1], H[i]);

    int Q;
    cin >> Q;
    while (Q--){
        int t;
        cin >> t;
        auto it = upper_bound(L.begin(), L.end(), t)-L.begin();
        cout << S[it] << endl;
    }
}

D問題 Maximize the Gap

にぶたんをする

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

int main(){
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> A(N);
    for (auto& [r, l] : A) cin >> l >> r;
    sort(A.begin(), A.end());

    auto F = [&](int d){
        vector<int> pre(N+1, 0);
        for (int i = 0; i < N; i++){
            auto [r, l] = A[i];
            auto p = upper_bound(A.begin(), A.end(), make_pair(l-max(d, 1), 1<<30))-A.begin();
            pre[i+1] = max(pre[i], pre[p]+1);
        }
        return pre[N];
    };

    if (F(0) < K){
        cout << -1 << endl;
        return 0;
    }
    int lo = 0, hi = 2e9;
    while (hi-lo > 1){
        int mid = (lo+hi)/2;
        if (F(mid) >= K) lo = mid;
        else hi = mid;
    }
    cout << lo << endl;
}

E問題 Roads and Gates

頂点Nを拡張してiからNにX[i],NからiにX[i]+Yの辺を繋げてダイクストラ

#include <bits/stdc++.h>
using namespace std;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

template<typename S, typename T> vector<T> dijkstra(const vector<vector<pair<S, T>>>& G, int root){
    vector<T> dist(G.size(), numeric_limits<T>::max());
    pqg<pair<T, int>> Q;
    dist[root] = 0;
    Q.push({0, root});
    while (!Q.empty()){
        auto [d, p] = Q.top();
        Q.pop();
        if (dist[p] < d) continue;
        for (auto [u, v] : G[p]){
            if (dist[u] > d+v){
                dist[u] = d+v;
                Q.push({dist[u], u});
            }
        }
    }
    for (auto &x : dist) if (x == numeric_limits<T>::max()) x = -1;
    return dist;
}

int main(){
    int N, M, Y;
    cin >> N >> M >> Y;
    vector<vector<pair<int, long>>> G(N+1);
    for (int i = 0; i < M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    for (int i = 0; i < N; i++){
        int x;
        cin >> x;
        G[i].emplace_back(N, x);
        G[N].emplace_back(i, x+Y);
    }

    auto dist = dijkstra(G, 0);
    for (int i = 1; i < N; i++) cout << dist[i] << ' ';
    cout << endl;
}