Good Bye, BOJ! 후기

백준 인생 마지막 대회가 끝났다. 백준 섭종에 대한 소회는 조만간 안 바빠지면 풀어보도록 하겠다.

A. Good Bye, 별 찍기!
예쁘게 짜줬다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    string s = string(4 * n + 2, ' ');
    vector<string> v;
    for (int i = 0; i < 2 * n; i++) v.push_back(s);
    for (int i = 0; i < 2 * n; i++) v[2 * n - 1 - i][i] = '*';
    int x = n - 1, y = 4 * n + 1;
    for (int i = 0; i < n; i++) v[x--][y--] = '*';
    for (int i = 0; i < n; i++) v[++x][--y] = '*';
    x++;
    for (int i = 0; i < n; i++) v[x++][y++] = '*';
    for (int i = 0; i < n; i++) v[--x][++y] = '*';
    for (auto &w : v) cout << w << '\n';
}

B. Good Bye, 설탕 배달!
대충 이렇게 하면 되는 것 같다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    while (tc--) {
        int n; cin >> n;
        ll x = 0, y = 0, z = 0, flag = 1;
        for (int i = 0; i < n; i++) {
            ll a, b, c, p; cin >> a >> b >> c >> p;
            x = max(x, a), y = max(y, b), z = max(z, c);
            if (x + y + z + i >= p) flag = 0;
        }
        cout << (flag ? "YES" : "NO") << '\n';
    }
}

C. Good Bye, 토마토!
1개 또는 2개 뽑는 것만 보면 되고, 각각 정렬한 뒤 투포인터를 써줬다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, d, ans = 0; cin >> n >> d;
    vector<pair<int, int>> v(n), w(n);
    for (int i = 0; i < n; i++) {
        int t, a, b; cin >> t >> a >> b;
        v[i] = {t, a}, w[i] = {t, b};
        ans = max(ans, a + b);
    }
    sort(v.begin(), v.end());
    sort(w.begin(), w.end());
    for (int i = 1; i < n; i++) v[i].second = max(v[i - 1].second, v[i].second);
    for (int i = n - 1, j = 0; j < n; j++) {
        while (i >= 0 && v[i].first + w[j].first > d) i--;
        if (i < 0) break;
        ans = max(ans, v[i].second + w[j].second);
    }
    cout << ans << '\n';
}

E. Good Bye, Scenery!
뒤부터 보면서 set을 이용해 가야 하는 최적의 자리를 정해줄 수 있다. 이후는 인버전 카운팅을 하면 되는데, 나름 내 시그니처인(였던) pbds를 사용해 풀었다.

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    while (tc--) {
        int n; cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        set<int> st;
        for (int i = 1; i <= n; i++) st.insert(i);
        ordered_set ts;
        ll ans = 0;
        for (int i = n; i >= 1; i--) {
            auto it = st.upper_bound(a[i]);
            if (it == st.begin()) { ans = -1; break; }
            it = prev(it);
            ans += ts.order_of_key(*it);
            ts.insert(*it);
            st.erase(it);
        }
        cout << ans << '\n';
    }
}

J. Good Bye, BOJ!

잘가요, 백준. 나의 모든 것.