Problem Solving/Contest

Codeforces: Hello 2024

PS리버싱마크해커박종휘TV 2024. 1. 7. 03:54

딱히 잘 한 것 같진 않은데, 무려 101점이나 올라서 승급하였다!!

 

Figure I. Result

 

민트를 복구했다. 2년 만의 복구이다. 사실 안 한 게 맞지만, 안 했음에도 지난 날의 퍼포먼스를 뛰어 넘은 것이 두개골이 확장된 것 같아 기분이 좋다.

 

A - Wallet Exchange

 

만약 총 남은 개수가 짝수 개라면, 결국에 Bob의 턴에 누구든지 1개의 Wallet이 남는다. 따라서 Bob이 이기는 것은 자명하다. 마찬가지로 홀수 개라면 Alice의 턴에 누구든지 1개의 Wallet이 남는다. 따라서 Alice가 이긴다.

 

더보기
#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int A, B; cin >> A >> B;
    if ((A + B) % 2 == 1) {
        cout << "Alice" << '\n';
    } else {
        cout << "Bob" << '\n';
    }
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
}

 

B - Plus-Minus Split

 

이건 증명을 못 했다. 하지만 직관적으로 예시를 보며 |('+'의 개수) - ('-'의 개수)| 가 답이라는 것을 알 수 있다. 그리고 가장 명확한 증거는, A랑 푼 사람의 수가 거의 같아서 예측하고 Solved by AC를 받을 수 있다.

 

더보기
#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int n; string s; cin >> n >> s;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '+') {
            cnt += 1;
        } else {
            cnt -= 1;
        }
    }
    cout << abs(cnt) << '\n';
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
}

 

C - Grouping Increases

 

그리디 알고리즘 문제이다. 어짜피 모든 원소가 한 번씩 각각 하나의 배열 안에 소속되어야 하니, 처음부터 돌면서 최적으로 스택에 쌓아주면 된다.

 

더보기
#include <bits/stdc++.h>

using namespace std;
#define int long long

int arr[200001];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    stack<int> a, b;
    int ans = 0;
    a.push(9876543212345678); b.push(9876543212345678);
    for (int i = 1; i <= n; i++) {
        if (arr[i] > a.top() && arr[i] > b.top()) {
            if (a.top() > b.top()) {
                b.push(arr[i]);
            } else {
                a.push(arr[i]);
            }
            ans += 1;
        } else if (arr[i] <= a.top() && arr[i] <= b.top()) {
            if (a.top() > b.top()) {
                b.push(arr[i]);
            } else {
                a.push(arr[i]);
            }
        } else if (arr[i] <= a.top() && arr[i] > b.top()) {
            a.push(arr[i]);
        } else {
            b.push(arr[i]);
        }
    }

    cout << ans << '\n';
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
}

 

후기

 

D도 거의 다 풀었는데, 구현 이슈 때문에 풀지 못했다. 또한 C도 빨리 제출해 더 많은 레이팅을 받고 싶어 성급히 제출했다가 함정에 빠졌다. 다음 번엔 모든 문제를 꼼꼼히 읽어서 블루까지 가야 할 것이다.

'Problem Solving > Contest' 카테고리의 다른 글

ABC 285  (0) 2023.01.16