Codeforces Round #672 (Div. 2)

A. Cubes Sorting

https://codeforces.com/contest/1420/problem/A

Problem - A - Codeforces

n개의 원소들이 있는 배열에서 $a_{i}$ 와 $a_{i+1}$를 교환할 수 있을때

그 교환횟수가 최대 $\frac{n\cdot(n-1)}{2} - 1$를 넘지 않게

오름차순으로 정렬이 가능하면 YES

불가능하면 NO를 출력하는 문제이다.

단순히 내림차순일때만 교환횟수가 부족하므로 내림차순일때만 NO를 출력하면 된다

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <string.h>
#include <iomanip>
#include <cmath>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define MAX 2001
#define INF 2147483640
typedef long long ll;
using namespace std;
 
int n, m, t, k;
int ans = 0;
int dr[] = { 0,-1,0,1 };
int dc[] = { 1,0,-1,0 };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> t;
	while (t--) {
		string a, b, c;
		cin >> a >> b >> c;
		bool ch = false;
		for (int i = 0; i < b.size(); i++) {
			if (b[i] != c[i] &&  a[i]!=c[i])
				ch = true;
				break;
			}
		}
		if (ch)
			cout << "NO" << '\n';
		else
			cout << "YES" << '\n';
	}
	return 0;
}

 

B. Rock and Lever

https://codeforces.com/contest/1420/problem/B

Problem - B - Codeforces

배열 a의 원소 중 i<j 인 원소 두개를 골라

$a_{i}$ & $a_{j} \geq a_{i} \oplus a_{j}$ 를 만족하는 페어의 개수를 구하는 문제이다.

AND 연산을 한 것이 XOR 연산보다 크거나 같으려면 최대 비트가 같기만 하면 된다.

왜냐하면 최대 비트가 다르면 xor이 무조건 더 크므로 조건이 성립하지 않고

같다면 XOR 연산은 최대 비트가 없어지므로 무조건 AND 연산이 크다.

따라서 각 원소들의 최대 비트에 따른 원소의 개수를 구해 각각 $szC_{2}$ 를 더하면 된다.

 

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define PQ priority_queue
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define MOD 1000000007 
#define MOD2 1000000021
#define MAXN 2000000
#define INF 1e9
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
 
ll m_pow(ll a, ll b, ll M = MOD) { ll res = 1; for (; b; b >>= 1, a = (a * a) % M)if (b & 1) res = (res * a) % M; return res; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
db dis(pii a, pii b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
 
int dr[] = { 0, 1, 0, -1, 1,1,-1,-1 };
int dc[] = { 1, 0, -1, 0, 1,-1,1,-1 };
 
int n, m, k, t;
 
string ansok[2] = { "NO","YES" };
int a[300001];
vi gra[200001];
int cnt[32];
int ps[33];
//set map ps seg dfs
int main()
{
	SYNC;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n; i++) cin >> a[i];
		ll ans = 0;
		for (int i = 0; i < 32; i++) {
			cnt[i] = 0;
		}
		for (int j = 0; j < n; j++) {
			for (int i = 31; i >= 0; i--) {
				if ((a[j] >> i) & 1) {
					cnt[i]++;
					break;
				}
			}
		}
		for (int i = 0; i <= 31; i++) {
			ans += 1LL*cnt[i] * (cnt[i] - 1) / 2;
		}
		// & >= ^ 라는건 가장 큰 공통되는비트가 두 수의 가장 큰 비트보다 크거나 같아야함
 
		cout << ans << '\n';
	}
	return 0;
}

 

C1. Pokémon Army (easy version)

https://codeforces.com/contest/1420/problem/C1

Problem - C1 - Codeforces

배열 a에서 1 $\leq b_{1} <b_{2}<⋯<b_{k} \leq n$ 를 골라서

$a_{b_{1}} − a_{b_{2}} + a_{b_{3}} − a_{b_{4}} +… $ 의 최댓값을 구하는 문제이다.

a[i-1] <= a[i] > a[i+1] 면 더하고

a[i-1] >= a[i] < a[i+1]  일 경우 빼면 최댓값이 구해진다.

이 식을 정리하면 if (a[i - 1] < a[i]) ans += a[i] - a[i - 1] 가 된다.

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define PQ priority_queue
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define MOD 1000000007 
#define MOD2 1000000021
#define MAXN 2000000
#define INF 1e9
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
 
ll m_pow(ll a, ll b, ll M = MOD) { ll res = 1; for (; b; b >>= 1, a = (a * a) % M)if (b & 1) res = (res * a) % M; return res; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
db dis(pii a, pii b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
 
int dr[] = { 0, 1, 0, -1, 1,1,-1,-1 };
int dc[] = { 1, 0, -1, 0, 1,-1,1,-1 };
 
int n, m, k, t;
 
string ansok[2] = { "NO","YES" };
int a[300001];
vi gra[200001];
int cnt[32];
int ps[33];
//set map ps seg dfs
int main()
{
	SYNC;
	cin >> t;
	while (t--) {
		int q;
		cin >> n >> q;
		for (int i = 1; i <= n; i++) cin >> a[i];
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i - 1] < a[i]) ans += a[i] - a[i - 1];
		}
		cout << ans << '\n';
	}
	return 0;
}

 

C2. Pokémon Army (hard version)

https://codeforces.com/contest/1420/problem/C2

Problem - C2 - Codeforces

C2에서는 쿼리문이 있어서 쿼리마다 $a_{i} 랑 a_{j}$를 스왑후 최댓값을 구한다.

스왑한 i, j 양옆의 구한 값에서 반대 값을 취한후 다시 더해주면 각각 쿼리마다의 정답이 된다.

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define PQ priority_queue
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define MOD 1000000007 
#define MOD2 1000000021
#define MAXN 2000000
#define INF 1e9
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
 
ll m_pow(ll a, ll b, ll M = MOD) { ll res = 1; for (; b; b >>= 1, a = (a * a) % M)if (b & 1) res = (res * a) % M; return res; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
db dis(pii a, pii b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
 
int dr[] = { 0, 1, 0, -1, 1,1,-1,-1 };
int dc[] = { 1, 0, -1, 0, 1,-1,1,-1 };
 
int n, m, k, t;
 
string ansok[2] = { "NO","YES" };
int a[300001];
vi gra[200001];
int cnt[32];
int ps[33];
//set map ps seg dfs
int main()
{
	SYNC;
	cin >> t;
	while (t--) {
		int q;
		cin >> n >> q;
		for (int i = 1; i <= n; i++) cin >> a[i];
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i - 1] < a[i]) ans += a[i] - a[i - 1];
		}
		cout << ans << '\n';
		while (q--) {
			int x, y; cin >> x >> y;
			if (a[x - 1] < a[x]) ans -= a[x] - a[x - 1];
			if (x != n && a[x] < a[x + 1]) ans -= a[x + 1] - a[x];
 
			if (x + 1 != y && a[y - 1] < a[y]) ans -= a[y] - a[y - 1];
			if (y != n && a[y] < a[y + 1]) ans -= a[y + 1] - a[y];
			swap(a[x], a[y]);
 
			if (a[x - 1] < a[x]) ans += a[x] - a[x - 1];
			if (x != n && a[x] < a[x + 1]) ans += a[x + 1] - a[x];
 
			if (x + 1 != y && a[y - 1] < a[y]) ans += a[y] - a[y - 1];
			if (y != n && a[y] < a[y + 1]) ans += a[y + 1] - a[y];
			cout << ans << '\n';
		}
 
	}
	return 0;
}

 

D. Pokémon Army (hard version)

https://codeforces.com/contest/1420/problem/D

Problem - D - Codeforces

n개의 램프들의 각각의 켜지는 시간과 꺼지는 시간을 알고있을때

k개의 램프가 켜질수 있는 램프의 경우의 수를 고르는 문제이다.

시작, 끝의 시간을 벡터에 나눠서 다 집어놓고 정렬을 한다음에 

켜진 램프의 개수를 구하여 k개 이상의 램프가 켜져있을때 

램프가 한개 꺼질때마다 꺼진 램프를 무조건 선택하여 고르면

$_{sz-1}C_{k-1}$가 된다. 이 경우의 수를 모두 합하여 답이 된다.

조합이 무척 크지만 MOD(998244353)를 하여 출력하고 MOD가 소수이므로 

페르마의 소정리를 사용하여 $a^{MOD-2}$ 의 역원을 통해 조합을 빠르게 구할 수 있다.

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define PQ priority_queue
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353 
#define MOD2 1000000021
#define MAXN 2000000
#define INF 1e9
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
 
ll m_pow(ll a, ll b, ll M = MOD) { ll res = 1; for (; b; b >>= 1, a = (a * a) % M)if (b & 1) res = (res * a) % M; return res; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
db dis(pii a, pii b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
 
int dr[] = { 0, 1, 0, -1, 1,1,-1,-1 };
int dc[] = { 1, 0, -1, 0, 1,-1,1,-1 };
 
int n, m, k, t;
 
string ansok[2] = { "NO","YES" };
int a[300001];
vi gra[200001];
int cnt[32];
int ps[33];
//set map ps seg dfs
 
ll f[300010];
ll inv[300010];
 
int mpow(int n, int p) {
	if (p == 1) return n;
	int ret = mpow(n, p / 2);
	ret = (long long)ret * ret % MOD;
	if (p % 2) ret = (long long)n * ret % MOD;
	return ret;
}
void make_com() {
	inv[0] = inv[1] = f[0] = f[1] = 1;
	for (int i = 2; i < 300010; i++) {
		f[i] = (long long)f[i - 1] * i % MOD;
	}
	for (int i = 2; i < 300010; i++) {
		inv[i] = (long long)inv[i - 1] * mpow(i, MOD - 2) % MOD;
	}
}
ll C(int n, int r) {
	return (long long)f[n] * inv[r] % MOD * inv[n - r] % MOD;
}
 
int main()
{
	SYNC;
	make_com();
	ll ans = 0;
	cin >> n >> k;
	//켜고 꺼지는 시간들을 다 알고있다.
	//k개가 모두 같은 시간을 공유하는 경우의 수를 고르기
	//하나씩 빠질때마다 mC(k-1)합
	vector<pii> v;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		v.push_back({ l,0 });
		v.push_back({ r,1 });
	}
	sort(all(v));
	int sz = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i].y == 0) {
			sz++;
		}
		else {
			if (sz >= k) {
				ans += C(sz - 1, k - 1);
				sz--;
			}
			else {
				sz--;
			}
		}
	}
	cout << ans % MOD << '\n';
	return 0;
}