Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)

https://codeforces.com/contest/1591

Dashboard - Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) - Codeforces

 

나의 6번째 코포였다. (버츄얼 빼고)

원래 있는지도 몰랐고 시험기간이라 바빴는데, 어쩌다 보니 보게 되었다.

 

좋은 선배.jpg

 

암튼 12시 5분 시작인데, 12시 2분에 알게 되어서 미리 등록을 못했다. 결국 시작하고 10분 뒤에야 제출을 할 수 있었다. 10점 정도 날려먹은 듯 ㅠㅠ. 그래도 평소보다 더 잘 풀렸다. 점수가 꽤 오를 것으로 예상된다! ㅎㅎ

 

 

 

 

 

A.

열심히 구현하자. A번 중에서도 쉬운 편이었던 것 같다.

 

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

ll n, ans;
ll arr[101];

void solve() {
	bool can = true;
	cin >> n;
	ans = 1;
	for (ll i = 1; i <= n; i++) {
		cin >> arr[i];
		if (i == 1) {
			if (arr[i]) ans++;
		}
		else {
			if (arr[i] && arr[i - 1]) ans += 5;
			else if (arr[i] && !arr[i - 1]) ans++;
			else if (!arr[i] && !arr[i - 1]) {
				ans = -1;
				can = false;
			}
		}	
	}
	if (can) cout << ans << endl;
	else cout << -1 << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

 

 

B.

주어진 수열에서 끝에서 부터 볼 때, 최댓값까지 최소 계단(?)의 개수이다.

 

예를 들어 2 4 1 5 3 이면 끝에서부터 최댓값인 5까지 한 번 올라간다. (3->5)

즉, 답은 1이다.

 

5 3 2 4 1 이면 끝에서부터 최댓값인 5까지 2번 만에 올라갈 수 있다. (1->4->5)

답은 2이다.

 

1 1 1 1 이면 끝값이 이미 최대니까 그냥 0이다.

답은 0이다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
 
ll n, ans;
ll arr[200001];
ll maxi = 0, maxidx, cnt = 0;
 
void solve() {
	maxi = 0;
	maxidx = 0;
	cnt = 0;
	cin >> n;
	for (ll i = 1; i <= n; i++) {
		cin >> arr[i];
		if (arr[i] >= maxi) {
			maxidx = i;
			maxi = arr[i];
		}
	}
	
	if (arr[n] == maxi) {
		cout << 0 << endl;
		return;
	}
	ll tmp = arr[n];
	for (ll i = n - 1; i >= maxidx; i--) {
		if (arr[i] == maxi) {
			cout << cnt + 1 << endl;
			return;
		}
		if (arr[i] > tmp) {
			cnt++;
			tmp = arr[i];
		}
	}
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}
 
	return 0;
}

 

 

C.

그리디로 풀었다.

음수와 양수를 따로 계산했다.

일단 다 가능한 경로에 2를 곱하여(왕복이니까) 더한 다음에, 마지막에 가장 긴 경로 한 번을 빼줬다. (마지막에는 다시 0으로 돌아올 필요가 없으므로 가장 긴 경로를 마지막에 가는 게 답이다. 그러면 다시 돌아오는 경로는 포함되지 않기 때문에 빼주었다는 뜻)

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
 
ll n, k, x, ans = 0;
 
void solve() {
	ans = 0;
	cin >> n >> k;
	vector<ll> m;
	vector<ll> p;
	for (ll i = 0; i < n; i++) {
		cin >> x;
		if (x > 0) p.push_back(x);
		else if (x < 0) m.push_back(-x);
	}
	if (m.empty() && p.empty()) {
		cout << 0 << endl;
		return;
	}
	
	sort(p.begin(), p.end());
	sort(m.begin(), m.end());
	
	if (!p.empty()) {
		for (ll i = p.size() - 1; i >= 0; i -= k) {
			ans += 2 * p[i];
		}
	}
	if (!m.empty()) {
		for (ll i = m.size() - 1; i >= 0; i -= k) {
			ans += 2 * m[i];
		}
	}
    
    //여기서부터는 가장 긴 경로 한 번 빼주는 코드
	if (!m.empty() && !p.empty()) {
		ll big = max(m[m.size() - 1], p[p.size() - 1]);
		ans -= big;
	}
	else if (m.empty() && !p.empty()) {
		ans -= p[p.size() - 1];
	}
	else if (!m.empty() && p.empty()) {
		ans -= m[m.size() - 1];
	}
	
	cout << ans << endl;
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
	int tc = 1; cin >> tc;
	while (tc--) {
		solve();
	}
 
	return 0;
}

 

 

D.

한 50분 정도 고민했는데 못풀었다. 아무것도 떠올리지 못했다.

끝나고 효규가 웰노운이란다. https://www.acmicpc.net/problem/5000 랑 똑같다더라. 플래티넘2 문제다. 맞힌 사람이 133명이고 플래티넘2인데 어케 웰노운일까?

암튼 멋있다. 나도 얼른 고수가 되어 풀어내고 싶다.

 

 

 

 

---

 

내 주위 대학생들은 지난주 금요일에 종강을 했다. 너무 부럽다. 나는 21일에 종강한다. 이런. 시험기간이라 그런지 코포가 더 재밌었다. 내일까지 내야 하는 과제가 있다. 내일 나는 2개의 수업을 듣고, 알바를 간다. 낼 수 있을까? 하..

 

아 그리고 지금 그린인데 색이 너무 구려서 백준에 코포 아이디 연동을 해제해놨다. 민트가면 다시 달아야지.

빨리 민트 가고 싶다. 보내줘.