Good Bye 2021: 2022 is NEAR

Good Bye 2021! 

2021년 마지막 코포였다.

사연이 있습니다.

 

 

무려 61점이나 떨구면서 마무리했다. 

A, B를 맞추고 C를 못 풀었는데, 시스텟에서 B가 터져버리는 바람에 망해버렸다.

 

코포를 시작하고 첫 1솔이다 ㄷㄷ;

 

암튼 어제 코포 사이트 점검 때문에 오늘 B와 C를 업솔빙했다.

 

 

 

A.

양수든 음수든 바꾸면 같아지니까 절댓값을 취해서 같이 세었다. 0일 때는 조심해야 한다.

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

ll n, k;

void solve() {
	cin >> n;
	vector<ll> chk(101, 0);
	for (ll i = 1; i <= n; i++) {
		cin >> k;
		chk[abs(k)]++;
	}
	ll ans = 0;
	for (ll i = 0; i <= 100; i++) {
		if (i == 0) {
			if (chk[i] > 0) ans++;
		}
		else {
			if (chk[i] > 1) ans += 2;
			else if (chk[i] == 1) ans++;
		}
	}
	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;
}

 

 

 

B.

처음으로 문자열이 감소하지 않는 부분에 거울을 두면 된다. 

반례가 하나 있다. bba 같은 경우이다. 이 경우에는 b/b, bb/bb, bba/abb가 나올 수 있는데, bb가 bbbb보다 앞선다. 맨 처음 두 문자가 같으면 첫 문자를 2번 출력한 것이 답이다.

 

맨 앞이 아닌 곳에서 같은 문자가 나오는 경우에는 신경 안 써도 된다. cbba와 같은 것은 답이 cbbc가 아닌 cbbaabbc이다.

 

첫 코드에서는 while문이 있었는데, 그럴 필요가 없었다... 암튼 시스텟에서 TLE로 터졌다. 

 

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

ll n;
string s;

void solve() {
	cin >> n;
	cin >> s;
	if (n == 1) {
		cout << s[0] << s[0] << endl;
		return;
	}
	if (n >= 2 && s[0] == s[1]) {
		cout << s[0] << s[0] << endl;
		return;
	}
	ll idx = 0;
	for (ll i = 0; i < s.size() - 1; i++) {
		if (s[i] >= s[i + 1]) idx++;
		else break;
	}
	for (ll i = 0; i <= idx; i++) {
		cout << s[i];
	}
	for (ll i = idx; i >= 0; i--) {
		cout << s[i];
	}
	cout << endl;
}


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번 틀렸다. 그러다가 문제를 다시 읽어보니까 n이 70이더라. 그래서 아 이거 그냥 브루트포스로 되겠다 싶어서 풀었다. 예제는 다 돌아가는데, 내가 만든 예제가 돌아가지 않았다. i와 j를 고정하고 두 수가 포함되는 등차수열을 찾았었는데, 나는 항상 두 항 사이의 거리가 j-i라고 생각했었다. 근데 1 x x 3 x x x x x 7과 같은 경우도 있더라. 결국 못 풀었다.

 

오늘 업솔빙 했다. 마찬가지로 i와 j를 고정 한 뒤, 모든 항을 보면서 i, j와 등차수열을 이루지 않는 수의 개수를 세었다.

모든 경우에 대해 다 계산하였다. O(n^3)이다.

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

ll n, ans;
vector<ll> a;

void solve() {
    cin >> n;
    a.resize(n + 1);
    for (ll i = 1; i <= n; i++) cin >> a[i];
    if (n == 1 || n == 2) {
        cout << 0 << endl;
        return;
    }
    ans = n - 1;
    for (ll i = 1; i <= n - 1; i++) {
        for (ll j = i + 1; j <= n; j++) {
            ll d = a[j] - a[i];
            ll cnt = 0;
            for (ll k = 1; k <= n; k++) {
                if ((a[k] - a[i]) * (j - k) != (a[j] - a[k]) * (k - i)) cnt++;
            }
            ans = min(ans, cnt);
        }
    }
    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;
}

 

 

---

Good bye 2022에는 파란색 이상 달고 있었으면 좋겠다.

 

올해 뒤늦게 코드포스를 시작했는데, 참 어려운 것 같다. 시간제한이 있으면 확실히 엄청 어려워지는 것 같다. 확실히 점수제도가 있으니까 스트레스도 많이 받지만 재밌다. 롤 랭겜이랑 비슷한 것 같다ㅋㅋ