Codeforces Round #772 (Div. 2)

민트다

다시 민트로 올라왔다!

84점 올렸다 ㅎㅎ

 

오늘 무려 31분 만에 3솔을 했다 ㄷㄷ;

그리고 D번 문제도 방향이 크게 다르지 않은 것 같아서 기분이 좋다.

 

 

3솔한 직후에는 무려 퍼플 퍼포가 떴었다 ㅋㅋ

너무 신나서 찍어놨다 ㅋㅋ

ㄷㄷ

 

최근 전적

 

요즘엔 버츄얼 포함해서 2솔하는 날보다 3솔하는 날이 더 많아진 것 같다! 실력이 늘은 건가?

 

다시는 그린으로 가고 싶지 않다!

---

A.

수열의 두 원소 ai와 aj를 x와 y로 바꿀 수 있다. (횟수 제한 X)

단, ai | aj == x | y 여야 한다.

 

결과적으로 수열의 모든 원소의 합을 최소가 되게 해야 한다.

or 연산의 특성상 2진수의 1은 없앨 수 없다.

 

이걸 통해서 잘 생각해보면 답은 a1부터 an까지 or 연산한 값이다.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n;

void solve() {
	cin >> n;
	vector<ll> a(n + 1);
	for (ll i = 1; i <= n; i++) cin >> a[i];
	ll ans = a[1];
	for (ll i = 2; i <= n; i++) ans |= a[i];
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

 

B.

수열이 주어진다.

수열의 원하는 값을 원하는 숫자로 바꿀 수 있다.

 

최소한으로 바꿔서 극댓값이 없게 만들어야 한다.

 

3번 인덱스부터 n번 인덱스까지 보자.

i가 인덱스 번호다.

if (a[i - 2] < a[i - 1] && a[i - 1] > a[i]) {
	a[i] = max(a[i - 1], a[i + 1]);        
}

위처럼 자기를 포함하여 앞의 3개를 볼 때, 극댓값이 있으면 그 값을 양 쪽의 값 중 큰 걸로 바꿔주면 된다.

 

a[n+1]을 가장 큰 값으로 설정해두고 풀면 인덱스 조심할 필요도 없다.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n;

void solve() {
	cin >> n;
	vector<ll> a(n + 2);
	for (ll i = 1; i <= n; i++) cin >> a[i];
	a[n + 1] = 1000000000;
	ll cnt = 0;
	for (ll i = 3; i <= n; i++) {
		if (a[i - 2] < a[i - 1] && a[i - 1] > a[i]) {
			a[i] = max(a[i - 1], a[i + 1]);
			cnt++;
		}
	}
	cout << cnt << endl;
	for (ll i = 1; i <= n; i++) cout << a[i] << ' ';
	cout << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

 

C.

수열이 주어진다.

i<j<k를 만족하는 세 수를 골라서 ai를 aj-ak로 만들 수 있다.

이 과정을 n번 이하로 해서 수열을 감소하지 않는 수열로 만들어야 한다.

 

맨 끝 2개는 바꿀 수 없기 때문에 먼저 맨 끝 두 개가 감소하면 -1을 출력하자.

 

이제 뒤에서 3번째 원소부터 역순으로 보자.

 

지금 보고 있는 원소의 인덱스를 x라고 하면 i=x, j=i+1, k=n을 골라서 연산을 하자.

연산을 하면서 감소하는 구간이 나오면 -1 출력하고 끝내자.

 

 

j=i+1, k=n을 골라야 하는 이유는 다음과 같다.

j=i+1, k=n이어야 aj-ak가 가장 크니까 주어진 작업을 했을 때, 가장 이득이다.

예를 들어 j를 i+1보다 큰 값을 하면 aj-ak가 더 커진다. 그러면 오름차순이 안 될 가능성이 높아지니까 굳이 그럴 필요가 없다.

가장 이득이 되게 하려면 j=i+1, k=n이어야 한다.

 

 

정당성을 설명하는 게 정말 어려운 것 같다. ㅠㅠ

 

그냥 위에 설명대로 해보면 왜 그런지 쉽게 알 수 있을 것이라고 생각된다...!

 

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct x {
	ll a, b, c;
};

ll n;

void solve() {
	cin >> n;
	vector<ll> a(n + 1);
	for (ll i = 1; i <= n; i++) cin >> a[i];
	if (a[n - 1] > a[n]) {
		cout << -1 << endl;
		return;
	}
	vector<x> v;
	for (ll i = n - 2; i >= 1; i--) {
		if (a[i] <= a[i + 1]) continue;
		a[i] = a[i + 1] - a[n];
		v.push_back({ i,i + 1,n });

		if (a[i] > a[i + 1]) {
			cout << -1 << endl;
			return;
		}
	}
	cout << v.size() << endl;
	for (ll i = 0; i < v.size(); i++) {
		cout << v[i].a << ' ' << v[i].b << ' ' << v[i].c << endl;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

 

D.

90분동안 본 문제이다.

방향은 대충 맞은 것 같다.

 

이건 풀이말고 그냥 복기...이다.

 

 

 

문제 서술에서 뭔가 bit를 사용하여 접근해야 할 것 같았다.

2배+1은 이진수를 왼쪽으로 한 칸 쉬프트하고 1을 더하는 연산.

4배는 이진수를 왼쪽으로 두 칸 쉬프트하는 연산.

이라고 보았다.

 

이걸 알고 보니까 수열의 원소들을 이진수로 표현했을 때, 앞부분이 겹치고 뒷부분을 00과 1로만 이용해서 똑같이 만들 수 있는 게 아니면 2x+1이나 4x를 반복해도 절대 같은 수를 만들 수 없더라.

 

그래서 위와 같은 수가 아니면 2의P승 이하의 수들을 세는 것이 어렵지 않다.

피보나치수열+누적합을 이용해서 쉽게 계산할 수 있었다.

 

그런데 10111001과 10111과 같은 경우에는 10111로 10111001을 만들 수 있다. 그러니까 그냥 10111001은 보지 않아도 된다. 왜냐하면 10111에서 다 계산되기 때문이다.

 

그래서 정렬을 하고 작은 원소부터 순서대로 보았다. 만약 10111001을 보고 있는데 앞에서 10111이나 101과 같은 것들이 있었다면 이번에는 계산하지 않아도 된다. 10111001로 만들 수 있는 모든 수는 10111이나 101과 같은 것들로 만들 수 있기 때문이다.

 

그래서 뭐 set을 이용해서 어찌저찌 구현을 했는데, 뒷부분에 00과 1만 이용해서 붙인 수가 큰 수와 같은지 확인하는 것이 어려워서 실패했다.

 

---

아 점수가 무척 달다. 기분이 좋다...