Codeforces Global Round 18

크리스마스다! 기념으로 코포를 쳤다.

나한테는 매우 어려웠다.

그래도 점수가 올랐다. ㄱㅇㄷ 항상 긍정적으로 생각하자.

B번까지 풀고 90분을 C번에 박았는데 못 풀었다. ㅠㅠ


A.
(총합%n)이 0이면 최대, 최소의 차이는 0이다.
나머지 경우는 최대, 최소의 차이를 1로 만들 수 있다.

#include <bits/stdc++.h> #define endl '\n' using namespace std; using ll = long long; ll n, sum = 0; ll arr[101]; void solve() { sum = 0; cin >> n; for (ll i = 1; i <= n; i++) { cin >> arr[i]; sum += arr[i]; } if (sum % n == 0) cout << 0 << 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.
처음에 A를 풀고 B를 읽었을 때가 한 4분? 지난 때였는데 학교 선배님이 벌써 B를 푸셨더라. 그래서 쉬운 줄 알았는데 오래 걸렸다. ㅠㅠ 처음에는 l부터 r까지 돌면서 각 자리 비트수를 저장하는 식으로 풀었는데, TLE가 났다.

그러다가 예전에 백준에서 x부터 y까지의 모든 수를 이진수로 나타냈을 때, 1의 개수의 총합을 구하는 문제를 보았던 기억이 났다. 대충 누적합으로 전처리해주고 풀었던 기억이 있어서 전처리하고 난 뒤, 계산하였다.

#include <bits/stdc++.h> #define endl '\n' using namespace std; using ll = long long; ll l, r; ll sum[200001][19]; ll func(ll a, ll b) {// 거듭제곱 구하는 함수 if (b == 0) return 1; ll res = func(a, b / 2); if (b % 2 == 1) return res * res * a; else return res * res; } void solve() { cin >> l >> r; ll one = 0; for (ll i = 0; i <= 18; i++) { one = max(one, sum[r][i] - sum[l - 1][i]); } cout << r - l + 1 - one << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //1의 개수 누적합 미리 구해두기 for(ll i = 0; i <= 18; i++) { ll pivot = func(2, i); ll now = pivot; ll chk = 0; ll b = 1; while (now <= 200001) { if (b) { sum[now][i] = sum[now - 1][i] + 1; chk++; } else { sum[now][i] = sum[now - 1][i]; chk++; } if (chk == pivot) { chk = 0; b = (b + 1) % 2; } now++; } } int tc = 1; cin >> tc; while (tc--) { solve(); } return 0; }

C.
대회 때 90분을 박고 못 풀었다. 코포에 이런 형식의 문제가 많이 나오는 것 같은데, 아직 어렵다 ㅠ.
끝나고 스터디에서 풀이를 들었는데, 나랑은 조금 다르게들 푸신 것 같았다. 내 풀이도 맞다고 생각해서 업솔빙 했는데, 맞았다! 다 풀고 나니까 다른 분들이랑 결국 같은 풀이인 것 같다.

일단, 문자열의 1의 개수와 0의 개수를 각각 m개, n개라고 하면 홀수번 작업하면 각각 n+1개, m-1개가 되고, 짝수번 작업하면 m개, n개로 유지되는 것을 이용하여 풀었다.

(1) 짝수번 작업하는 경우는 문자열 a,b의 각 자릿수가 다른 것의 개수만큼 작업하면 된다. 왜냐하면 1011이랑 0111에서 처음에 1번 인덱스, 두 번째에 2번 인덱스를 선택하면 두 위치를 바꾼 거와 마찬가지이기 때문이다. 1과 0의 위치가 바뀐다! 즉, 2번만 작업하면 된다.

(2) 홀수번 작업하는 경우는 (1번 + 짝수번) 작업한다고 생각하면 편하다.
위에서 설명했듯이 홀수번 작업하면 0, 1의 개수가 바뀌는데, 이를 만족하면 a와 b가 같은 개수만큼이 답이다.

예외도 잘 처리해주자.

대회 중에는 (1), (2) 중 하나만 되는 줄 알았다. 그리고 (2)의 코드도 조금 틀렸었고... 암튼 업솔빙 성공했다!!!

#include <bits/stdc++.h> #define endl '\n' using namespace std; using ll = long long; ll n; string a; string b; string tmp; void solve() { cin >> n; cin >> a >> b; if (a == b) { //예외 cout << 0 << endl; return; } ll acnt = 0, bcnt = 0; //0의 개수 for (ll i = 0; i < n; i++) { if (a[i] == '0') acnt++; if (b[i] == '0') bcnt++; } if (acnt == n) { //예외 cout << -1 << endl; return; } ll ans = 9876543210; ll cnt = 0; for (ll i = 0; i < n; i++) { if (a[i] != b[i]) cnt++; } if (acnt == bcnt) { ans = min(ans, cnt); } if (n == acnt + bcnt + 1) { ans = min(ans, n - cnt); } if (ans == 9876543210) cout << -1 << endl; else 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; }

---

2솔밖에 못했지만 다행히 점수가 떨어지지 않는다. 다행이다. 아직 너무 어렵다. 3솔을 하고 싶다.



아, 새해맞이 이벤트로 코드포스 핸들 색 바꾸기가 가능하다.

나는 신이다!

괜히 누텔라 해봤다가 현타가 밀려오는 새벽이다. 젠장.