0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

AtCoder Beginner Contest 423

Last updated at Posted at 2025-09-15

A - Scary Fee

問題文

O(1)

ans + ans \times \frac{c}{1000} <= x

は式の変形によって、

1000 \times ans + ans \times c <= 1000 \times x
ans \times (1000 + c) <= 1000 \times x
ans <= 1000 \times \frac{x}{1000 + c}

とすることができます。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int x, c;
    cin >> x >> c;
    int ans = x / (1000 + c) * 1000;
    cout << ans << endl;
    return 0;
} 

B - Locked Room

問題文

全探索でシミュレーションしましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n;
    cin >> n;
    vector<int> l(n), room(n+1);
    rep(i, n) cin >> l[i];
    room[0] = 1;
    room[n] = 1;
    rep(i, n){
        if(l[i] == 0 && room[i] == 1 && room[i+1] == 0){
            room[i+1] = 1;
        }else{
            break;
        }
    }
    for(int i=n-1; i>=0; i--){
        if(l[i] == 0 && room[i+1] == 1 && room[i] == 0){
            room[i] = 1;
        }else{
            break;
        }        
    }
    int ans = 0;
    rep(i, n+1){
        if(room[i] == 0) ans++;
    }
    cout << ans << endl;
    return 0;
} 

C - Lock All Doors

問題文

rの部屋から左右を見ます。
空いている扉を+1
空いている扉とrの間にある閉じている扉を+2
として扱います。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, r;
    cin >> n >> r;
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    int ans = 0;
    bool isOpen = false;
    rep(i, r){
        if(l[i] == 0){
            isOpen = true;
            ans++;
        }else if(l[i] == 1 && isOpen){
            ans+=2;
        }
    }
    isOpen = false;
    for(int i=n-1; i>=r; i--){
        if(l[i] == 0){
            isOpen = true;
            ans++;
        }else if(l[i] == 1 && isOpen){
            ans+=2;
        }
    }
    cout << ans << endl;
    return 0;
} 

D - Long Waiting

問題文

プライオリティーキューの問題です。
退店時間をキーにしてプライオリティーキューへ追加していきます。
人数がkを超えるタイミングで、プライオリティーキューからpopして、
現在の人数から引いていきます。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n, k;
    cin >> n >> k;
    vector<tuple<ll, ll, ll, ll>> customer;
    rep(i, n){
        ll a, b, c;
        cin >> a >> b >> c;
        customer.emplace_back(a, b, c, i);
    }
    sort(customer.begin(), customer.end(), [](const tuple<ll, ll, ll, ll>& a, const tuple<ll, ll, ll, ll>& b){
        return get<0>(a) < get<0>(b);
    });
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> queue;
    ll human = 0;
    ll now = 0;
    vector<ll> ans(n);
    auto available = [&](ll cc) -> ll {
        while(queue.size()){
            auto [time, num] = queue.top();
            queue.pop();
            human -= num;

            if(human + cc < k){
                return time;
            }
        } 
        return now;
    };

    rep(i, n){
        auto [a, b, c, d] = customer[i];
        if(human + c > k){
            now = available(c);
        }
        queue.emplace(max(now, a)+b, c);
        human += c;
        ans[d] = max(now, a);
    }
    rep(i, n){
        cout << ans[i] << endl;
    }
    return 0;
} 
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?