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