https://codeforces.com/contest/1631
Dashboard - Codeforces Round #768 (Div. 2) - Codeforces
codeforces.com
오랜만의 라이브 코포
벌써 3일이 지나 글을 써야 하는 날이 됐다.
다른 내용을 쓰려고 했는데 상황이 마땅치 않아서 오늘 코포를 치고 후기 글을 적기로 했다.
학회 코포 스터디 단톡방에서 했던 이야기인데
INFP 특) 사소한 걱정이 많다.
그래도 걱정을 한 김에 적어보자면, 많은 분들이 계시는 곳인데 몇몇 사람들만 아는 이야기를 해서 죄송했다.
애초에 이런 사담에 관심이 없으셔서 괜찮으셨을 수도 있지만, 그래도 누군가 이걸 보고 무슨 이야기를 하는 걸까 라는 생각을 조금이라도 한 분이 있으시다면 죄송합니다.
A.
라이브가 너무 오랜만이라 긴장해서 문제 잘못 읽는 바람에 초반에 말렸다.
a 원소랑 b 원소는 인덱스 관계없이 swap할 수 있는 줄 알았다.
그게 아니라 swap a(i) with b(i)니까 결국 a랑 b 중 한쪽에는 작은 것들을, 다른 한쪽에는 큰 것들을 저장해두고, a, b 배열에서 각각의 최댓값을 곱하면 답이다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
}
cout << *max_element(a.begin(), a.end()) * *max_element(b.begin(), b.end()) << kEndl;
}
}
B.
이걸 한 번에 풀어서 좀 뿌듯하다.
문제에서 말하는 operation을 반복해서 배열의 원소가 모두 같아질 때, 그때의 값은 결국 배열의 맨 마지막 인덱스의 값과 같다.
풀이는
우선 배열의 인덱스가 감소하는 방향으로 살펴보면서 값이 같은 원소가 몇 개인지를 저장한다 (이를 저장하는 변수를 same_as_last_cnt로 뒀다).
그리고 값이 다른 원소가 나타나면 operation을 하게 되는데, 그 결과 same_as_last_cnt는 2배가 된다.
이후에도 동일하게 또다시 배열의 어디까지가 마지막 원소와 같은 값인지를 체크하고, 값이 다른 원소가 나타나면 또 operation을 해야 하는 상황인 것이므로 same_as_last_cnt가 2배가 되고, ... 이를 반복하면 된다.
주의할 점은
10
0 0 0 0 0 0 1 1 0 1
이런 케이스도 있으므로, 마지막 원소와 같은 값을 갖는 원소가 연속하여 몇 개인지를 계속 확인해야 한다는 거다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int same_as_last_cnt = 0;
int ans = 0;
for (int i = n - 1; i >= 0; ) {
if (arr[i] == arr[n - 1]) {
++same_as_last_cnt;
--i;
}
else {
++ans;
i -= same_as_last_cnt;
same_as_last_cnt *= 2;
}
}
cout << ans << kEndl;
}
}
C.
험난했다.
우선 처음에 틀린 이유는 k == n - 1일 때 무조건 -1인줄 알았다.
그러다가 n == 4일 때만 그렇다는 걸 깨달아서 다시 풀었는데,
내가 잘못 생각한 게 n - 1을 이진수로 바꾼 거에서 각각의 1을 모두 다른 sum에서 가져오려고 했다.
예를 들어 n = 16일 때 0001 + 0010 + 0100 + 1000 + 0000 + .... + 0000 이런 식으로.
근데 이 풀이는 AND 연산 결과 1이 하나씩 있도록 하는 각각의 쌍을 구하는 것도 복잡하고, 나머지 수들에 대해 AND 연산한 결과를 모두 0이 되는 쌍을 찾는 것도 복잡하다.
동가스의 풀이를 보니 1...10 + 0...01 + 0...00 + ... + 0...00 이런 식으로 (n - 1) + 1 + 0 (나머지)로 하면 됐다. 1을 몰아넣을 생각을 전혀 못 했다. 동가스 그는 신인가?
내가 대회 때 짠 코드는 너무 복잡해서 그냥 동가스 풀이대로 내가 끝나고 다시 짠 코드를 올린다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n, k; cin >> n >> k;
if (k == n - 1) {
if (n == 4) {
cout << -1 << kEndl;
continue;
}
cout << n - 2 << ' ' << n - 1 << kEndl;
cout << 1 << ' ' << 3 << kEndl;
cout << 0 << ' ' << n - 4 << kEndl;
for (int i = 0; i < n / 2; ++i) {
if (i == 0 || i == 1 || i == 3) {
continue;
}
cout << i << ' ' << n - 1 - i << kEndl;
}
}
else {
cout << k << ' ' << n - 1 << kEndl;
if (k != 0) {
cout << n - 1 - k << ' ' << 0 << kEndl;
}
for (int i = 0; i < n / 2; ++i) {
if (i == k || i == n - 1 - k || i == 0) {
continue;
}
cout << i << ' ' << n - 1 - i << kEndl;
}
}
}
}