Codeforces Round #515 (Div. 3)

Codeforces Round #515 (Div. 3) 버츄얼을 돌았다!

간단간단하게 풀이를 적겠다.

 

Vova and Train

 

$[L/v]-([r/v]-[(l-1)/v])$ 가 답이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
 
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		int L,v,l,r;
		cin >> L >> v >> l >> r;
		cout << L/v - (r/v-(l-1)/v) << '\n';
	}
}

 

Heaters

 

$l : $ $l-1$까지 히터가 닿는다 라고 가정하면 우리는 1로 되어있는 인덱스$-r+1$ 중 $l+2r-1$ 보다 작거나 같지만 가장 큰 인덱스를 고르면 된다.

만약 두번 연속 같은 인덱스면 불가능하다는게 자명하다.

 

이걸 계속 하면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
int n,r;
int a[1005];
vector <int> v;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> r;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		if(a[i]) v.push_back(i-r+1);
	}
	int l = 1,la = -1,ans = 0;
	for(;l <= n;) {
		int w = upper_bound(v.begin(),v.end(),l)-v.begin()-1;
		if(w == -1||la == w) {
			cout << -1;
			return 0;
		}
		ans++;
		la = w;
		l = v[w]+2*r-1;
	}
	cout << ans;
}

 

Books Queries

 

나는 deque에 이분탐색을 박았는데 다른사람은 훨씬 쉽게 풀었다. 내 풀이를 보는건 비추다.

deque를 정의할때 {값,추가된 시각} 으로 정의해 준다.

쿼리 'L' : 왼쪽에 {값,추가된 시각} 추가

쿼리 'R' : 오른쪽에 {값,추가된 시각} 추가

쿼리 '?' : 첫번째 'L' 또는 'R' 쿼리의 인덱스 $idx$를 미리 저장해 둔다. 그러면 $idx$를 기준으로 왼쪽, 오른쪽으로 나눠보면 왼쪽은 시각이 오름차순, 오른쪽은 시각이 내림차순이다. 이 시각을 이용하여 왼쪽에서 찾아보고 오른쪽에서 찾아보는 식으로 한 다음, 위치를 찾았으면 $min(index,deque.size-index-1)$를 출력하면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
int Q;
deque <pair<int,int>> dq;
int t[200005],st = 0;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> Q;
	for(int i = 1;i <= Q;i++) {
		char w; int x;
		cin >> w >> x;
		if(w == 'L') {
			if(i != 1) st++;
			dq.push_front({x,i});
			t[x] = i;
		}
		if(w == 'R') {
			dq.push_back({x,i});
			t[x] = i;
		}
		if(w == '?') {
			int n = dq.size();
			int l = 0,r = st;
			while(l < r) {
				int mid = (l + r) >> 1;
				if(dq[mid].y > t[x]) l = mid+1;
				else r = mid;
			}
			if(dq[l].x == x) cout << min(l,n-l-1) << '\n';
			else {
				l = st+1,r = n-1;
				while(l < r) {
					int mid = (l + r) >> 1;
					if(dq[mid].y < t[x]) l = mid+1;
					else r = mid;
				}
				if(dq[l].x == x) cout << min(l,n-l-1) << '\n';
				else return 1;
			}
		}
	}
}

 

Boxes Packing

 

당근 이분탐색이다.

$x$ : $x$부터 물건을 채우기 시작할때 채울 수 있나?

이걸 가지고 이분탐색을 돌리면 끝이다.

시간복잡도는 $O(nlogn)$이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
int n,m,k;
int a[200005];
 
bool isok(int x) {
	int nam = 0,use = 1;
	for(int i = x;i <= n;i++) {
		if(nam+a[i] > k) {
			use++;
			nam = 0;
		}
		nam += a[i];
	}
	return (use <= m);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++) cin >> a[i];
	int l = 1,r = n;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(!isok(mid)) l = mid+1;
		else r = mid;
	}
	cout << n-l+1;
}

 

Binary Numbers AND Sum 

 

B가 한자리씩 줄어드므로 각 자리에 1이 몇개씩 들어가는지 세줄 수 있다.

만약 어떤 인덱스 $i$에 대해, $a[i] = 1$이라면 $sum[i]*2^{n-i}$를 더해주면 된다.

두 이진수의 자리수를 맞춰줘야 가능하다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
int n,m;
char a[200005],b[200005],in[200005];
ll ans,sum[200005],g = 1,mod = 998244353;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	cin >> in+1 >> b+1;
	for(int i = 1;i <= m-n;i++) a[i] = '0';
	for(int i = max(m-n+1,1);i <= m;i++) a[i] = in[i-(m-n)];
	for(int i = 1;i <= m;i++) sum[i] = sum[i-1]+b[i]-'0';
	for(int i = m;i >= 1;i--) {
		if(a[i] == '1') ans = (ans+g*sum[i])%mod;
		g = g*2%mod;
	}
	cout << ans;
}

 

Yet another 2D Walking

 

일단 알고리즘은 동적 계획법 이다.

각 레벨에 따라 분리해보면 각 레벨의 가장 왼쪽을 지났다가 가장 오른쪽 점을 지나거나 가장 오른쪽을 지났다가 가장 왼쪽 점을 지나는 경우가 최적임을 알 수 있다.

그래서 우린 $DP$ 식을 세워줄 수 있다.

$DP[i][j]$ :  $i$레벨까지 모두 방문했고, 마지막 위치가 $j$일때 최소 길이 ($j=0$일때는 가장 왼쪽, $j=1$일때는 가장 오른쪽)

이러면 점화식을 세워줄 수 있다.

긴 식

참 점화식이 길다. 조금더 간결하게 줄여보면

조금 짧아진 식

이다.

하지만 레벨이 $10^{9}$까지이기 때문에 좌표압축을 한다.

시간복잡도는 $O(nlogn+m)$이다. ($m$은 서로 다른 레벨의 개수)

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
int n,m;
ll d[200005][2];
pi po[200005][2];
vector <int> rev;
vector <pi> g[200005];
 
struct Point {
	int x,y,lv;
}a[200005];
 
ll dist(pi x,pi y) {
	return abs(x.x-y.x)+abs(x.y-y.y);
}
 
bool cmp(pi x,pi y) {
	if(x.x == y.x) return x.y > y.y;
	return x.x < y.x;
}
 
void go(int x) {
	if(x == 0) return;
	if(d[x][0] != -1) return;
	go(x-1);
	d[x][0] = min(d[x-1][0]+dist(po[x-1][0],po[x][1])+dist(po[x][1],po[x][0]) , d[x-1][1]+dist(po[x-1][1],po[x][1])+dist(po[x][1],po[x][0]));
	d[x][1] = min(d[x-1][0]+dist(po[x-1][0],po[x][0])+dist(po[x][0],po[x][1]) , d[x-1][1]+dist(po[x-1][1],po[x][0])+dist(po[x][0],po[x][1]));
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	memset(d,-1,sizeof(d));
	d[0][0] = d[0][1] = 0;
	for(int i = 1;i <= n;i++) {
		cin >> a[i].x >> a[i].y;
		a[i].lv = max(a[i].x,a[i].y);
		rev.push_back(a[i].lv);
	}
	sort(rev.begin(),rev.end()); rev.erase(unique(rev.begin(),rev.end()),rev.end());
	m = rev.size();
	for(int i = 1;i <= n;i++) {
		a[i].lv = lower_bound(rev.begin(),rev.end(),a[i].lv)-rev.begin()+1;
		g[a[i].lv].push_back({a[i].x,a[i].y});
	}
	po[0][0] = po[0][1] = {0,0};
	for(int i = 1;i <= m;i++) {
		sort(g[i].begin(),g[i].end(),cmp);
		po[i][0] = g[i].front(), po[i][1] = g[i].back();
	}
	go(m);
	cout << min(d[m][0],d[m][1]);
}