🔵

【ABC423】AtCoder Beginner Contest 423【C++】

に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 423

コンテストURL

https://atcoder.jp/contests/abc423

開催日

2025/09/14 21:00–22:40

A: Scary Fee

解法

  • 最大で何円まで引き出せるか昇順に調べる
ABC423A.cpp
#include <iostream>
using namespace std;

int main(){
    int x, c;
    cin >> x >> c;

    int ans = 0;
    for(int i=0; i<=x/1000; i++){
        int sum = 1000 * i + c * i;
        if(sum>x){
            break;
        }
        ans = 1000 * i;
    }

    cout << ans << endl;

    return 0;
}

B: Locked Rooms

解法

  • 問題文通りにシミュレーションする
ABC423B.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> L(n);
    for(int i=0; i<n; i++){
        cin >> L[i];
    }

    vector<int> V(n+1, 1);
    V[0] = 0;
    V[n] = 0;
    for(int i=0; i<n; i++){
        if(L[i]==0){
            V[i+1] = 0;
        }else{
            break;
        }
    }
    for(int i=n-1; i>0; i--){
        if(L[i]==0){
            V[i] = 0;
        }else{
            break;
        }
    }

    int cnt = 0;
    for(int i=0; i<n+1; i++){
        if(V[i]){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

C: Lock All Doors

解法

  • 部屋を左から右に並べたとき、左側の連続してすべての部屋のドアが閉まっている区間、中央の区間、右側の連続してすべての部屋のドアが閉まっている区間に分類する
  • 部屋 R が左側の連続してすべての部屋のドアが閉まっている区間、中央の区間、右側の連続してすべての部屋のドアが閉まっている区間のどこにあるかによって、 3 通りに場合分けする
  • 部屋 R が中央の区間にあるとき、最初に左側に移動しても、最初に右側に移動しても、開閉操作の回数は変わらないことに注意する
ABC423C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, r;
    cin >> n >> r;

    vector<int> L(n);
    for(int i=0; i<n; i++){
        cin >> L[i];
    }

    int left = -1, right = n + 1;
    for(int i=0; i<n; i++){
        if(L[i]==1){
            left = i;
        }else{
            break;
        }
    }
    for(int i=n-1; i>=0; i--){
        if(L[i]==1){
            right = i + 1;
        }else{
            break;
        }
    }

    if(left>=right){
        cout << 0 << endl;
        return 0;
    }

    int minv = 1e9;
    if(r<=left){
        int cnt1 = 0;
        
        cnt1 += (left-r+1) * 2;
        for(int i=left+1; i<right-1; i++){
            if(L[i]==1){
                cnt1++;
            }
            cnt1++;
        }

        minv = min(minv, cnt1);
    }else if(r>=right){
        int cnt2 = 0;
        
        cnt2 += (r-right+1) * 2;
        for(int i=right-2; i>left; i--){
            if(L[i]==1){
                cnt2++;
            }
            cnt2++;
        }

        minv = min(minv, cnt2);
    }else{
        int cnt3 = 0;
        for(int i=r-1; i>left; i--){
            if(L[i]==1){
                cnt3++;
            }
        }
        cnt3 += (r-left-1);
        for(int i=r; i<right-1; i++){
            if(L[i]==1){
                cnt3++;
            }
        }
        cnt3 += (right-r-1);

        minv = min(minv, cnt3);
    }

    cout << minv << endl;

    return 0;
}

D: Long Waiting

解法

  • priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> で現在、店内にいる団体客を管理する
ABC423D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;

int main(){
    long long int n, k;
    cin >> n >> k;

    long long int a, b, c;
    priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> Q;
    vector<long long int> ans(n);
    int sum = 0;
    long long int time = 0;
    for(int i=0; i<n; i++){
        cin >> a >> b >> c;

        time = max(time, a);

       while(sum+c>k){
            auto [x, y] = Q.top();
            Q.pop();

            time = max(time, x);
            sum -= y;
       }

       sum += c;
       Q.emplace(time+b, c);
       ans[i] = time;
    }

    for(int i=0; i<n; i++){
        cout << ans[i] << '\n';
    }

    return 0;
}

Discussion