Codeforces Round #672 (Div. 2)

Codeforces Round #672 (Div. 2) 를 쳤다.

대충 5솔정도 했는데 내 생각으로는 난이도가 A < B < C1 < D < C2 인것 같다.

 

A - Cubes Sorting

 

순 내림차순인지 확인하고 맞으면 "NO" 아니면 "YES"를 출력하면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef long long ll;
int n,a[50005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		for(int i = 1;i <= n;i++) cin >> a[i];
		int ch = 1;
		for(int i = 2;i <= n;i++) {
			if(a[i-1] <= a[i]) ch = 0;
		}
		if(ch) cout << "NO\n";
		else cout << "YES\n";
	}
} 

 

B - Rock and Lever

 

만약 두 정수 $x$, $y$ 를 비교한다고 하자.

$x$ $xor$ $y$ > $x$ $and$ $y$ 일 조건이 최상위 비트가 같냐 다르냐에 차이에 따라 다르다는거를 알 수 있다.

 

$cnt[i]$ : 최상위 비트가 $2^{i-1}$ 인 정수의 개수

답은 $cnt[i]*cnt[i-1]/2$ 의 합이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef long long ll;
int n,a[100005];
int cnt[35];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n;
		memset(cnt,0,sizeof(cnt));
		for(int i = 1;i <= n;i++) cin >> a[i];
		for(int i = 1;i <= n;i++) {
			int x = a[i],cc = 0;
			while(x) {
				cc++;
				x /= 2;
			}
			cnt[cc]++;
		}
		ll ans = 0;
		for(int i = 1;i <= 31;i++) {
			ans += 1LL*cnt[i]*(cnt[i]-1);
		}
		cout << ans/2 << '\n';
	}
} 

 

C1 - Pokémon Army (easy version)

 

일단 맨 처음 생각한게 그리디 풀이인데 $a[i-1] < a[i]$ $and$ $a[i] > a[i+1]$ 인 것과 $a[i-1] > a[i]$ $and$ $a[i] < a[i+1]$ 인것을 각각 더하고 빼준다.

그리고 맨 마지막에 더하는 것으로 끝나는 것이 이득이기 때문에 맨 마지막에 빼는 것 이라면 마지막은 다시 더해준다.

이렇게 하면 easy버전은 쉽게 풀린다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef long long ll;
int n,Q,a[300005],b[300005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n >> Q;
		for(int i = 1;i <= n;i++) cin >> a[i], b[i] = 0;
		ll sum = 0;
		int cnt,la = 0;
		for(int i = 1;i <= n;i++) {
			if(a[i-1] > a[i]) {
				if(b[i-1] == -1) b[i-1] = 0;
				b[i] = -1;
			}
			else if(a[i-1] < a[i]) {
				if(b[i-1] == 1) b[i-1] = 0;
				b[i] = 1;
			}
		}
		for(int i = n;i >= 1;i--) {
			if(b[i] == 1) break;
			if(b[i] == -1) {
				b[i] = 0;
				break;
			}
		}
		for(int i = 1;i <= n;i++) {
			sum += b[i]*a[i];
		}
		cout << sum << '\n';
	}
} 

 

C2 - Pokémon Army (hard version)

 

여러가지 생각을 하다가 쿼리 처리하기도 좋은 방법을 떠올렸다.

일단 $a[0] = 0$이라 둔다.

만약 $a[i-1] < a[i]$ 이면 $ans = ans+a[i]-a[i-1]$ 을 한다.

그러면 답은 $ans$이다.

증명은 알아서 해보기 바란다. ^^

 

쿼리가 $x$, $y$ 로 들어온다고 하면

$a[x]$에 대한것을 지워버린다는 식으로 답에 $a[x]$연관이 되있는건 다 빼준다. $a[y]$도 마찬가지다.

이제  $a[x]$ 와 $a[y]$ 를 swap 하고 $a[x]$때문에 답에 더해지는걸 해준다.

 

여기서 $a[x]$ 가 연관이 있다는 거는 $a[x] < a[x+1]$ 인 경우와 $a[x-1] < a[x]$인 경우를 말한다.

 

추가로 x+1 = y인 경우가 있을땐 $a[x] < a[x+1]$ 인 경우와 $a[y-1] < a[y]$인 경우가 같기 때문에 중복으로 빼진다.

그래서 이건 따로 처리를 해줘야 한다. (더할 때도 중복으로 더해지는걸 처리해 줘야 한다.)

 

이렇게 짜면 시간 복잡도 $O(N+Q)$ 에 가능하다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef long long ll;
int n,Q,a[300005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> n >> Q;
		for(int i = 1;i <= n;i++) cin >> a[i];
		ll sum = 0;
		for(int i = 1;i <= n;i++) {
			if(a[i-1] < a[i]) sum += a[i]-a[i-1];
		}
		cout << sum << '\n';
		while(Q--) {
			int x,y; cin >> x >> y;
			if(a[x-1] < a[x]) sum -= a[x]-a[x-1];
			if(x != n&&a[x] < a[x+1]) sum -= a[x+1]-a[x];
 
			if(x+1 != y&&a[y-1] < a[y]) sum -= a[y]-a[y-1];
			if(y != n&&a[y] < a[y+1]) sum -= a[y+1]-a[y];
            
			swap(a[x],a[y]);
 
			if(a[x-1] < a[x]) sum += a[x]-a[x-1];
			if(x != n&&a[x] < a[x+1]) sum += a[x+1]-a[x];
 
			if(x+1 != y&&a[y-1] < a[y]) sum += a[y]-a[y-1];
			if(y != n&&a[y] < a[y+1]) sum += a[y+1]-a[y];
 
			cout << sum << '\n';
		}
	}
} 

 

D - Rescue Nibel!

 

스위핑 하듯이 추가되고 나가는 지점은 한 벡터에 넣고 정렬시킨다.

각 랜턴이 추가될때마다 추가된 랜턴은 무조건 사용하고 나머지 랜턴들로 $k-1$개를 뽑는 경우의 수를 더하면 되는데 

추가된 랜턴은 무조건 사용하고 아직 불이 들어온 랜턴들중 $k-1$개를 뽑는 경우의 수는 $cntCk-1$ 이다.

이걸 하면 된다.

 

조합 빨리 구하는 법은 제 블로그에 ^^

조합 글

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef long long ll;
int n,k;
pi a[300005];
vector <pi> v;
ll fact[300005],factInv[300005];
 
ll mpow(ll x,ll m) {
    if(!m) return 1;
    ll tmp = mpow(x,m/2);
    tmp = tmp*tmp % mod;
    if(m % 2) return tmp*x%mod;
    return tmp;
}
 
ll Com(ll x,ll r) {
    return fact[x]*factInv[r]%mod*factInv[x-r]%mod;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    fact[0] = 1;
    for(int i = 1;i <= 300000;i++) fact[i] = fact[i-1]*i%mod;
    factInv[300000] = mpow(fact[300000],mod-2);
    for(int i = 299999;i >= 0;i--) factInv[i] = factInv[i+1]*(i+1)%mod;
	cin >> n >> k;
	for(int i = 1;i <= n;i++) {
		int x,y; cin >> x >> y;
		v.pb({x,-1});
		v.pb({y,1});
	}
	sort(v.begin(),v.end());
	int cnt = 0;
	ll ans = 0;
	for(pi i : v) {
		if(i.y == -1) {
 
			if(cnt >= k-1) ans = (ans+Com(cnt,k-1))%mod;
		}
		cnt += -i.y;
	}
	cout << ans << '\n';
} 

 

E 몰라

끝