NYPC 2024 Round 1 / Round 2

Jinhuyk Mun

Student. CSE

Daily Study Algorithm PS

NYPC 2024 Round 1 / Round 2 - A / Round 2 -B

Sep 15, 2024

ps
NYPC

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;

}

루시드의 레이저 공격을 피해라!

선분교차 문제
선분이 축과 평행한 직선 또는 기울기가 1 또는 -1 인 직선 밖에 없으므로, binary_search 를 이용하여 문제를 풀 수 있음.
또한 기울기가 1 또는 -1 인 직선은 축을 45도 회전시켜, 직선처럼 만든 후에 풀 수 있음 (중요한 아이디어)
일반적인 선분교차로는 $O(QM)$ 으로 TLE
$O(Q \log M + M \log M)$ 이 걸리게 된다.

#include <bits/stdc++.h>
using namespace std;


struct Point{
	int X ,Y;
	Point operator - (const Point &p){return {X-p.X, Y - p.Y};}
	Point operator + (const Point &p){ return {X+p.X, Y+p.Y};}
	bool operator <(const Point &p){return tie(X,Y) < tie(p.X, p.Y);}
	bool operator >(const Point &p){return tie(X,Y) > tie(p.X, p.Y);}
	bool operator == (const Point &p){return tie(X,Y) == tie(p.X, p.Y);}
	bool operator >= (const Point &p){return tie(X,Y) >= tie(p.X, p.Y);}
	bool operator <= (const Point &p){return tie(X,Y) <= tie(p.X, p.Y);}
};

Point Rotate(Point p){
	return {p.X + p.Y , p.X - p.Y};
}

struct Line{
	Point p1,p2;
};


vector<bool> f(vector<Line> laser, vector<Line> query){

	vector<bool> ret(query.size(),1);
	vector<int> lx,ly;

	for(int i = 0; i<laser.size();i++){
		auto [p1,p2] = laser[i];
		if(p1.X == p2.X) lx.push_back(p1.X);
		if(p1.Y == p2.Y) ly.push_back(p1.Y);
	}
	sort(lx.begin() , lx.end());
	sort(ly.begin(), ly.end());

	auto _on = [&](Point p) -> bool {
		return binary_search(lx.begin(), lx.end(), p.X) || binary_search(ly.begin(),ly.end(), p.Y);
	};

	for(int i = 0; i<query.size();i++){
		auto [p1,p2] = query[i];

		if(_on(p1) || _on(p2)) ret[i] = false;
		if(p1.X != p2.X){
			int x1 = p1.X, x2 = p2.X;
			if(x1 > x2) swap(x1,x2);
			if(!(upper_bound(lx.begin(), lx.end(), x1) ==upper_bound(lx.begin(), lx.end(), x2))) ret[i] = false;
		}
		if(p1.Y != p2.Y){
			int y1 = p1.Y, y2 = p2.Y;
			if(y1 > y2) swap(y1,y2);
			if(!(upper_bound(ly.begin(), ly.end(), y1) ==upper_bound(ly.begin(), ly.end(), y2))) ret[i] = false;
		}
	}
	return ret;
}

int main(void){

	cin.tie(0)->sync_with_stdio(0);
	int N, M, Q; 
	cin >> N >> M >> Q;

	vector <Line> laser;
	vector <Line> query;
	for(int i = 0;i<M;i++){
		int x1,y1, x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		laser.push_back({ {x1,y1} , {x2,y2} });
	}
	for(int i = 0 ;i<Q;i++){
		int x1,y1, x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		query.push_back({ {x1,y1} , {x2,y2} } );
	}
	auto r1 = f(laser,query);

	for(auto &p : laser) {p.p1 = Rotate(p.p1); p.p2 = Rotate(p.p2);}
	for(auto &p : query) {p.p1 = Rotate(p.p1); p.p2 = Rotate(p.p2);}
	auto r2 = f(laser,query);

	for(int i = 0;i<Q;i++)
		cout << (r1[i] && r2[i]) <<"\n";
	

}