[앳코더] AtCoder Beginner Contest 240(비기너 240) 풀이

https://atcoder.jp/contests/abc240/tasks

Tasks - AtCoder Beginner Contest 240

 

A - Edge Checker

풀이

• 작은 수 + 1 == 큰 수 임을 체크한다.
• 작은 수 1 , 큰 수 10 케이스에 주의

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int a, b;
    cin >> a >> b;

    if (a > b) swap(a, b);

    if (a == 1 && b == 10) {
        cout << "Yes\n";
    } else if (a + 1 == b) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

 

B - Count Distinct Integers

풀이

• distinct 원소 개수 구하기
• set 에 insert

코드

• 시간복잡도: $O(NlogN)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;
    set<int> s;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        s.insert(num);
    }
    cout << s.size() << '\n';
}

 

 

C - Jumping Takahashi

풀이

• $dp[i][j]: i$번 점프후 $j$위치에 있는 것이 가능하면 $1$ 아니면 $0$
• $dp[i][j] = 1$ 이면 $dp[i + 1][j + a[i + 1]] = dp[i + 1][j + b[i + 1]] = 1$

코드

• 시간복잡도: $O(NX)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N, X;
    cin >> N >> X;

    vector<vector<long long> > dp(N, vector<long long> (100 * 100 + 1, - 1));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        if (i == 0) {
            dp[i][a] = 1;
            dp[i][b] = 1;
            continue;
        }
        for (int j = 0; j <= 100 * 100; ++j) {
            if (dp[i - 1][j] == -1) continue;
            dp[i][j + a] = dp[i][j + b] = 1; 
        }
    }

    if (dp[N - 1][X] == 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

 

D - Strange Balls

풀이

• 스택으로 {번호, 갯수} 를 관리
• top 과 같은 번호 들어오면 지울지 말지 결정
• 다른 번호들어오면 push

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;

    stack<pair<int, int> > st;
    int answer = 0;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;

        if (st.size()) {
            if (st.top().first == num) {
                if (st.top().second == num - 1) {
                    st.pop();
                    answer -= num - 1;
                } else {
                    int tmp = st.top().second;
                    st.pop();
                    st.push({num, tmp + 1});
                    ++answer;
                }
            } else {
                st.push({num, 1});
                ++answer;
            }
        } else {
            st.push({num, 1});
            ++answer;
        }
        cout << answer << '\n';
    }
}

 

E - Ranges on Tree

풀이

• dfs 하면서 리프 노드(간선이 부모랑밖에 없는 노드) 의 L = R = seq++
• 리프 노드가 아니면 자식노드들의 구간 모두 포함하게 구성

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;
    vector<vector<int> > adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> L(N + 1, 0), R(N + 1, 0);
    int seq = 1;
    function<void(int, int)> f = [&](int cur, int p) {
        if (adj[cur].size() == 1 && adj[cur][0] == p) {
            L[cur] = R[cur] = seq++;
            return;
        }
        int l = 1e9;
        int r = -1e9;
        for (auto e: adj[cur]) {
            if (e == p) continue;
            if (!L[e] && !R[e]) {
                f(e, cur);
            }
            l = min(l, L[e]);
            r = max(r, R[e]);
        }
        L[cur] = l;
        R[cur] = r;
    };

    f(1, 0);
    for (int i = 1; i <= N; ++i) {
        cout << L[i] << ' ' << R[i] << '\n';
    }
}

 

F - Sum Sum Max

풀이

• 각 원소 반복의 끝, 또는 그 부분의 B 값이 양수이면 B 값이 음수 직전까지 의 A 값이 최대이다

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int TC; cin >> TC;
    while (TC--) {
        long long N, M;
        cin >> N >> M;
        vector<pair<long long, long long> > C(N);
        vector<long long> A(N, -1e9), B(N, -1e9);
        for (int i = 0; i < N; ++i) {
            long long x, y;
            cin >> x >> y;
            C[i] = {x, y};
            B[i] = x * y;
            if (i) B[i] += B[i - 1];
            A[i] = x * y * (y + 1) / 2;
            if (i) A[i] += A[i - 1] + B[i - 1] * y;
        }

        long long answer = C[0].first;
        for (int i = 0; i < N; ++i) {
            if (i < N - 1 && C[i + 1].first < 0 && B[i] > 0) {
                long long k = B[i] / abs(C[i + 1].first);
                k = min(k, C[i + 1].second);
                answer = max(answer, A[i] + k * B[i] + k * (k + 1) * C[i + 1].first / 2);
            } else {
                answer = max(answer, A[i]);
            }
        }
        cout << answer << '\n';
    }
}