AtCoder Beginner Contest 245（ABC245）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 245での成績：2855位
パフォーマンス：894相当
レーティング：1559→1508 (-51) :(#AtCoder #ABC245 https://t.co/3qng9Zy2Lh

— ボンド@競プロ (@bond_cmprog) March 26, 2022

A - Good morning

分に直して比較をする

提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if(60*A+B < 60*C+D+1) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Mex

配列で出現した値を管理する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(2020);
    REP(i,N){
        int a;
        cin >> a;
        A[a]++;
    }
    REP(i,2020) if(A[i] == 0){
        cout << i << endl;
        return;
    }
}

C - Yamanote Line Game

DPをする

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N),B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    map<int, int> mp;
    mp[A[0]] = 1;
    mp[B[0]] = 1;
    REP(i,1,N){
        map<int, int> nxt;
        for(auto [k, v] : mp){
            if(abs(k - A[i]) <= K) nxt[A[i]]++;
            if(abs(k - B[i]) <= K) nxt[B[i]]++;
        }
        swap(mp, nxt);
    }
    if(mp.size() > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

D - Polynomial division

上の桁から決めていく

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N+1), B(M+1), C(N+M+1);
    REP(i,N+1) cin >> A[i];
    REP(i,N+M+1) cin >> C[i];
    for(int i=M;i>=0;i--){
        B[i] = C[i+N] / A[N];
        REP(j,N+1) C[i+j] -= B[i] * A[j];
    }
    REP(i,M+1) cout << B[i] << " ";
    cout << endl;
}

E - Wrapping Chocolate

箱とチョコレートを同じ配列に入れ、縦の降順にソートを行う
このとき、縦が同じなら箱が手前に来るようにソートをする
縦の降順に見ていき、箱なら横の長さをmultisetなどで管理し、チョコレートなら $ B_i $ 以上の箱で一番小さい値の箱を使う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(N), C(M), D(M);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    REP(i,M) cin >> C[i];
    REP(i,M) cin >> D[i];
    vector<tuple<int, int, int>> vs;
    REP(i,N) vs.emplace_back(-A[i], 1, B[i]);
    REP(i,M) vs.emplace_back(-C[i], -1, D[i]);
    sort(ALL(vs));
    multiset<int> ms;
    for(auto [h, c, w] : vs){
        if(c == -1) ms.insert(w);
        else{
            auto itr = ms.lower_bound(w);
            if(itr == ms.end()){
                cout << "No" << endl;
                return;
            }
            ms.erase(itr);
        }
    }
    cout << "Yes" << endl;
}

F - Endless Walk

強連結成分分解を行ったグラフ上でDPを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    StronglyConnectedComponents scc(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        scc.make_edge(--u, --v);
    }
    scc.solve();
    auto g = scc.topological_sort();
    auto edge = scc.edge;
    int ans = 0;
    vector<int> dp(N);
    for(int i=(int)g.size()-1;i>=0;i--){
        if(g[i].size() == 1) for(auto nv : edge[g[i][0]]) dp[i] |= dp[scc.getLabel(nv)];
        else dp[i] = 1;
        if(dp[i]) ans += g[i].size();
    }
    cout << ans << endl;
}