AtCoder Beginner Contest 423

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;
}