[AtCoder] ABC 355 (2024-05-25)

AtCoder Beginner Contest 355 (https://atcoder.jp/contests/abc355)

 

---

 

A . Who Ate the Cake?

 

https://atcoder.jp/contests/abc355/tasks/abc355_a

 

//C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    vector<bool> p = vector<bool>(4, true);

    for (int i = 0; i < 2; i++) {
        int x;
        cin >> x;
        p[x] = false;
    }

    int cnt = 0;
    int ans;

    for (int i = 1; i < 4; i++) {
        if (p[i]) {
            cnt++;
            ans = i;
        }
    }

    if (cnt == 1) {
        cout << ans << '\n';
    }
    else {
        cout << -1 << '\n';
    }

}

(정답)

 

---

 

B. Piano 2

 

https://atcoder.jp/contests/abc355/tasks/abc355_b

 

//C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> b = vector<int>(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int aidx = 0;
    int bidx = 0;
    int cnt = 0;
    bool ans = false;

    while (aidx < n && bidx < m) {
        if (a[aidx] < b[bidx]) {
            aidx++;
            cnt++;
        }
        else {
            bidx++;
            cnt = 0;
        }
        if (cnt == 2) {
            ans = true;
            break;
        }
    }

    if (aidx < n - 1) {
        ans = true;
    }

    if (ans) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

하.. 삽질을 좀 했다. C에서 인접한 두 원소가 A에서 왔을 때, A에서도 인접했던 원소들이어야 하는 줄 알고... 아 그리고 분할 정복 하듯이 풀었는데, B를 다 봐서 A만 남아있는 상태를 고려하지 못해서 틀렸었다. (오답) 마지막에 if (adix < n - 1) 부분을 추가하여 맞혔다. (정답)

 

---

 

C - Bingo 2

 

https://atcoder.jp/contests/abc355/tasks/abc355_c

 

//C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<bool>> b;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, t;
    cin >> n >> t;

    b = vector<vector<bool>>(n, vector<bool>(n, false));
    bool chk;
    int ans;

    for (int tnum = 1; tnum <= t; tnum++) {
        int x;
        cin >> x;
        x--;
        int r = x / n;
        int c = x % n;
        b[r][c] = true;

        chk = true;
        for (int i = 0; i < n; i++) {
            if (!b[r][i]) {
                chk = false;
                break;
            }
        }
        if (chk) {
            ans = tnum;
            break;
        }

        chk = true;
        for (int i = 0; i < n; i++) {
            if (!b[i][c]) {
                chk = false;
                break;
            }
        }
        if (chk) {
            ans = tnum;
            break;
        }

        chk = true;
        for (int i = 0; i < n; i++) {
            if (!b[i][i]) {
                chk = false;
                break;
            }
        }
        if (chk) {
            ans = tnum;
            break;
        }

        chk = true;
        for (int i = 0; i < n; i++) {
            if (!b[i][n - i - 1]) {
                chk = false;
                break;
            }
        }
        if (chk) {
            ans = tnum;
            break;
        }
    }

    if (chk) {
        cout << ans << '\n';
    } else {
        cout << -1 << '\n';
    }
}

문제에서 주어진 대로 구현만 하면 됐던 문제. (정답)

 

---

 

D - Intersecting Intervals

 

https://atcoder.jp/contests/abc355/tasks/abc355_d

 

//C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<pair<int, int>> itv (n);
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        itv[i].first = l;
        itv[i].second = r;
    }

    sort(itv.begin(), itv.end());

    for (int i = 0; i < n - 1; i++) {
        int l = i;
        int r = n;
        int m;
        while (l < r) {
            m = (l + r) / 2;
            if (itv[m].first <= itv[i].second) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        ans += (l - 1 - i);
    }

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

보자마자 뭔가 정렬한 다음에 이분 탐색으로 풀어야겠다는 느낌을 받았다. 튜플 벡터를 l에 대해서 오름차순으로 정렬하고 튜플들을 위에서 하나씩 보며 자신보다 아래에 있는 튜플들 중 자신의 r보다 l값이 처음으로 커지는 튜플을 찾아서 개수를 계산하였다. 로직은 전부 맞게 풀었는데 자꾸 답이 이상하게 나와서 결국 대회 시간 안에는 못 풀었다... 아쉽.. (오답)

대회 끝나고 보니 r을 exclusive하게 잡았는데 초기화를 n이 아닌 n-1로 해서 계속 틀리게 나왔던 것이었다. 그리고 튜플의 쌍은 int의 범위를 넘어갈 수 있기 때문에 ans의 자료형을 long long으로 해주어야 한다. 이 두 부분을 고쳤더니 맞았다. (정답)

 

---

 

4솔 할 수 있을 줄 알았는데 아쉽게 3솔로 마무리.. 다음은 4솔이다..!!!!!!