Codeforces Round #763 (Div. 2)

오늘도 코포가 있어서 응시했다. ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

 

지난 2번의 contest에서 16점을 올렸다. 그리고 오늘 41점을 까먹었다ㅠ. 어렵다...

우선 A, B를 푸는 데 많은 시간이 걸린다. 그러다 보니 C번에 쓸 시간이 많이 없고, C번도 못 푼다. ㅠ

 

암튼 최근에 오기가 생겨서 코포에 많은 시간을 투자해보려고 한다. 최소 2일에 한 번 응시하려고 한다. 하루는 업솔빙해야 하니까...

생각해보니 노력도 안하고 점수가 올라가길 바랐던 것 같다. 실력이 오르면 점수는 따라오겠지.. ㅎㅇㅌ

 

 

A.

나만 그런건지 모르겠는데 시작하자마자 코포가 터졌다. A번 문제가 열리질 않았다. 한 4분 정도를 날린 것 같다.

 

목적지가 있는 행과 열을 기준으로 1, 2, 3, 4 사분면으로 나누어 풀었다. 1 사분면과 3 사분면에서 하나를 놓쳐서 1번 틀렸다. ㅠㅠ

 

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

ll n, m, a, b, c, d;

void solve() {//a,b시작 c,d도착
	cin >> n >> m >> a >> b >> c >> d;
	if (a == c || b == d) {
		cout << 0 << endl;
		return;
	}
	if (a < c && b < d) {//2사분면
		cout << min(c - a, d - b) << endl;
	}
	if (a < c && b > d) {//1사분면
		cout << min(c - a, m - b + m - d) << endl;
	}
	if (a > c && b < d) {//3사분면
		cout << min(d - b, n - a + n - c) << endl;
	}
	if (a > c && b > d) {//4사분면
		cout << min(n - a + n - c, m - b + m - d) << 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,2]와 같은 구간이면 무조건 2를 선택한 것을 알 수 있기 때문. 구간이 [a, b]이면 a와 b 중 아직 선택하지 않은 수를 선택해주었다. 그리고 제출하였는데 틀렸다. 예제를 다시 확인해보니 마지막, 그러니까 [1, n] 구간에서는 양 끝 값이 아닌 값이 선택될 수 있더라. 그래서 선택한 수들을 체크한 뒤, 맨 마지막엔 선택되지 않은 수를 선택해서 출력하였다.

 

아 여담으로, 이거 문제에서 순서가 상관 없다는 말을 놓쳐서 초반에 삽질을 많이 했다.  ㅠㅠ

 

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

ll n, a, b;
ll chk[1001];

bool cmp(pair<ll, ll> x, pair<ll, ll> y) {
	ll xdif = x.second - x.first;
	ll ydif = y.second - y.first;
	return xdif < ydif;
}

void solve() {
	memset(chk, 0, sizeof(chk));
	cin >> n;
	vector<pair<ll, ll>> vec(n);
	for (ll i = 0; i < n; i++) cin >> vec[i].first >> vec[i].second;
	sort(vec.begin(), vec.end(), cmp);
	for (ll i = 0; i < n; i++) {
		ll u = vec[i].first;
		ll v = vec[i].second;
		if (u == v) {
			cout << u << ' ' << v << ' ' << u << endl;
			chk[u] = 1;
		}
		else {
			if (chk[u] && chk[v]) {
				for (ll j = u + 1; j <= v - 1; j++) {
					if (!chk[j]) {
						cout << u << ' ' << v << ' ' << j << endl;
						chk[j] = 1;
					}
				}
			}
			else if (chk[u]) {
				cout << u << ' ' << v << ' ' << v << endl;
				chk[v] = 1;
			}
			else if(chk[v]) {
				cout << u << ' ' << v << ' ' << u << endl;
				chk[u] = 1;
			}
		}
	}
}


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

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

	return 0;
}

 

 

 

 C.

B를 풀고 70분이 남았다. 한 40분이 남았을 즈음에 parametric search로 해결할 수 있음을 알았다. 구현을 시작했는데, 잘 안되더라. 열심히 노력했는데, 결국 다 구현을 못하고 끝났다. 10초만 더 있었으면 제출할 수 있었다.

 

결과적으로 제출했어도 틀렸다.

풀이는 맞았다고 생각해서 엄청 아쉬워했었는데, 풀이도 틀렸었다 ㅋㅋ ㅠ

 

그래서 끝나고 업솔빙했다.

parametric search을 통해 최솟값의 최댓값을 찾는 식으로 풀었다.

대회 중에는 앞에서부터 보았는데, 그렇게 하면 문제의 마지막 테케에 걸린다. 

 

엄청 고민했는데 결국 모르겠어서 선배들의 코드를 조금 봤더니 다들 뒤에서부터 보더라.

그래서 뒤에서부터 보았다.

 

뒤에서부터 볼 때 주의점이 있다. 문제에서는 앞에서부터 보기 때문에 절대 나올 수 없는 숫자가 나올 수 있다. 따라서 그러지 않게 코드를 작성해야 한다.

 

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

ll n;
ll h[200005];

bool can(ll minim) {
	vector<ll> vec(n + 1);
	for (ll i = 1; i <= n; i++) vec[i] = h[i];
	for (ll i = n; i >= 3; i--) {
		if (vec[i] < minim) return false;
		ll sur = min(h[i], vec[i] - minim) / 3;
		vec[i - 1] += sur;
		vec[i - 2] += 2 * sur;
		vec[i] -= sur * 3;
	}
	if (vec[1] < minim || vec[2] < minim) return false;
	return true;
}

void solve() {
	cin >> n;
	for (ll i = 1; i <= n; i++) cin >> h[i];
	ll low = 0;
	ll high = (ll)1e10;
	ll ans = 0;
	while (low <= high) {
		ll mid = (low + high) / 2;
		if (can(mid)) {
			low = mid + 1;
			ans = max(ans, mid);
		}
		else {
			high = mid - 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;
}

 

---

뭔가 코포에 parametric search 문제가 되게 자주 나오는 것 같다. 당분간 백준은 parametric search 문제 위주로 풀어야지.