NYPC 2024문제풀이
채점 및 문제는 BIKO를 통해 확인할 수 있다.
초밥
-
범위는 [1, min(A,B)] 이고, 탐색 범위가 크기 때문에 이분탐색을 떠올림
-
Binary jumping (추후 알고리즘에서 다룰 예정) 기법을 이용하여 문제풀이
#include <bits/stdc++.h>
using namespace std;
int check(int A, int B, int i){
return A+B <=4*i;
}
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T;
while(T--){
int A,B;
cin >> A >> B;
int l = 0, r = min(A,B);
for(int k = r; k >=1;k>>=1){
while(l+k <= r && !check(A,B,l+k)) l += k;
}
cout << (l+1 > min(A,B) ? -1 : l+1)<<"\n";
}
return 0;
}
무한길이 물풍선
- 2개의 물풍선을 비교하는 경우에 $O(N^2)$가 걸리게 되는데, 이는 TLE
- Set을 이용하여 중복이 되는 경우에 답을 담는 set에 다시저장
- 위 방식은 $O(N\log N)$
#include <bits/stdc++.h>
using namespace std;
int main(void){
set <int> X,Y,ansX, ansY;
int N; cin >> N;
while(N--){
int x,y; cin >> x >> y;
if(X.find(x) == X.end()) X.insert(x);
else{
ansX.insert(x);
}
if(Y.find(y) == Y.end()) Y.insert(y);
else ansY.insert(y);
}
cout << ansX.size()+ansY.size() <<"\n";
return 0;
}
커닝시티 헤어샵
- D[i] : i번째까지의 최소 시간
- $D[i] = min(D[i-1]+ t[i], D[i-2] + max(t[i],t[i-1]))$
- 정수의 범위를 벗어날수 있으므로, long long 타입을 사용해야함..!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll D[505050];
ll t[505050];
int main(void){
cin >> N;
for(int i = 1;i<=N;i++) cin >> t[i];
D[1] = t[1];
for(int i = 2; i<=N;i++){
D[i] = min(D[i-1]+t[i], D[i-2]+ max(t[i],t[i-1]));
}
cout <<D[N]<<"\n";
return 0;
}
게임
- 핑크빈의 목표는 가장 앞에있는 1을 없애서 작은값으로
-
블랙빈의 목표는 가장 앞에있는 0을 없애서 큰값으로
- Deque를 이용하여 front 또는 back를 접근할수 있다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N, K;
deque <int> Z[2];
string s;
cin >> N >> K >> s;
for(int i = 0;i<N;i++) Z[s[i]-'0'].push_back(i);
while(K--){
if(!Z[1].empty()) Z[1].pop_front();
else Z[0].pop_back();
if(!Z[0].empty()) Z[0].pop_front();
else Z[1].pop_back();
}
for(int i = 0;i <N;i++){
if(s[i] == '0' &&!Z[0].empty() && Z[0].front() == i) {cout << '0'; Z[0].pop_front();}
if(s[i] == '1' &&!Z[1].empty() && Z[1].front() == i){cout << '1'; Z[1].pop_front();}
}
}
골드리치의 비밀금고
- Mo’s Algorithm과 Bitset을 이용하여 풀수 있음.
- cnt[x] 로 개수를 세주면서 1이 될때만 체크할수 있고,
- _Find_first() 로 첫번째 1이 되는 순간을 찾을 수 있다.
-$O(Q \times (\sqrt N + N/32))$ 의 시간복잡도를 얻을 수 있다.
-
Set이나 Priority_queue를 이용하여 구현해볼려했으나, $(O\log N \sqrt N)$ 으로 TLE가 나게 된다.
-
bitset이 생각보다 효율이 좋다는 것을 알게됨.
#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long ll;
int sz;
const int M = 300000;
struct Q{
int i,s,e;
bool operator < (Q &x){
if(s/sz != x.s/sz) return s/sz < x.s/sz;
return e < x.e;
}
};
vector<Q> query;
int v[303030],ans[303030], cnt[300001];
bitset<M> r;
void add(int x){
cnt[x]++;
if(cnt[x] == 1) r[x] = 1;
if(cnt[x] != 1) r[x] = 0;
}
void del(int x){
cnt[x]--;
if(cnt[x] == 1) r[x] = 1;
if(cnt[x] != 1) r[x] = 0;
}
int main(void){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n ;
sz = sqrt(n);
for(int i = 1; i<=n;i++) cin >> v[i];
int q; cin >> q;
for(int i = 0; i<q;i++){
int s,e; cin >> s >> e;
query.push_back({i,s,e});
}
sort(query.begin(), query.end());
int s = query[0].s, e = query[0].e;
for(int i = s ; i<=e;i++) {
add(v[i]);
}
ans[query[0].i] = r._Find_first();
for(int i = 1; i<q;i++){
while(s < query[i].s) del(v[s++]);
while(s > query[i].s) add(v[--s]);
while(e < query[i].e) add(v[++e]);
while(e > query[i].e) del(v[e--]);
ans[query[i].i] = r._Find_first();
}
for(int i = 0; i<q;i++) cout << (ans[i] == M ? 0 : ans[i]) <<"\n";
}
장비교체
- D[i]의 총합과 각 i 마다의 U[i]와 total을 비교하면서 최대한 장비 업그레이드를 할수 있는 방향으로 그리디하게 구현이 가능하다.
- $O(N)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll U[505050], D[505050], M[505050], N , total;
char ans[505050];
int main(void){
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for(int i = 1; i<=N;i++) cin >> U[i];
for(int i = 1; i<=N;i++) cin >> D[i];
for(int i = 1; i<=N;i++) M[i] = max(0LL, D[i]);
for(int i = N; i>=1;i--) M[i] += M[i+1];
for(int i = 1; i<=N;i++) ans[i] = '0';
for(int i = 1;i<=N;i++){
if(U[i] != -1 && total+U[i] <= M[i+1]) {ans[i] = '+'; total += U[i];}
else if (D[i] != -1 && total > M[i+1]){ans[i] = '-'; total -= D[i];}
}
cout << ans+1;
}