SCPC 2023 2차 예선 후기

본선 제발

 

대회 날짜를 전날에 알았는데, 대회와 시간이 정확히 겹치는 일정이 두 개나 있었다(...)

하나는 어찌어찌 뺐고 하나는 4시간 정도를 잡아먹었다.

 

 

1. 타이젠 윷놀이

 

첫 문제부터 머리가 지끈거린다. 각 상황을 flag 변수 두 개를 이용하여 나타내고 단순화시켜서 시뮬레이션하면 된다. 그런데 범위가 커서 이동을 메모이제이션하는 과정이 필요하다. 그런데 답이 int 범위를 넘어서 롱롱을 사용해야 한다. 답이 크다는 것을 놓쳐서 코드가 틀린 줄 알고 막 런전처하는 새로운 풀이 짜다가 한 시간 넘게 허비했다.

 

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

void solve()
{
    int n, k; cin >> n >> k;
    vector<int> a(n + 1), b(k + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    int x = 0, f1 = 0, f2 = 0;
    map<tuple<int, int, int>, tuple<int, int, int, int>> mp;
    for(int j = 1; j <= k; j++) {
        if(mp.count({x, f1, f2})) {
            auto [p, q, r, s] = dp[{x, f1, f2}];
            b[j] = p, x = q, f1 = r, f2 = s;
        }
        else {
            int px = x, pf1 = f1, pf2 = f2;
            for(int i = 1; i <= n; i++) {
                x += a[i];
                if(x == 5) f1 = 1;
                if(f1 && x == 8) f2 = 1;
                if(!f1 && x == 10) f2 = 1;
                if(f1 && f2 && x > 11) b[j]++, x = f1 = f2 = 0;
                if(f1 && !f2 && x > 16) b[j]++, x = f1 = f2 = 0;
                if(!f1 && f2 && x > 16) b[j]++, x = f1 = f2 = 0;
                if(!f1 && !f2 && x > 20) b[j]++, x = f1 = f2 = 0;
            }
            mp[{px, pf1, pf2}] = {b[j], x, f1, f2};
        }
        b[j] += b[j - 1];
    }
    cout << b[k] << '\n';
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << '\n';
        solve();
    }
}

 

 

2. 괄호 문자열

 

그냥 어렵다. 소괄호만 있는 거 먼저 풀려고 구글링했더니 코포 오렌지 분이 열심히 세그 쓰는 풀이를 소개해주길래 풀태는 더 어려울 거라 생각했다. 근데 세그 쓰는 것도 상수가 커서 돌지 않았고, 스파스 테이블로 바이너리 리프팅하면서 상수도 줄이고 빠른 입출력도 쓰고 별 짓을 다했는데 부분 점수를 못 긁었다. 풀태는 소괄호만 있을 때와 같이 특별한 규칙이 없어서 스택을 쓰겠다는 느낌은 있었는데, 세그에 매몰되어서 선형 풀이를 찾지 못했다. 아래는 터진 코드

 

#include <bits/stdc++.h>
using namespace std;
#define nm (nl + nr >> 1)
typedef long long ll;
const int N = 1e6 + 2;

string s;
int n, a[N], nxt[N][20], mn[N][20];
vector<int> mp[N << 1];

void init() {
    for(int i = 1; i <= n; i++) nxt[i][0] = i + 1, mn[i - 1][0] = a[i];
    nxt[n + 1][0] = n + 1, mn[n][0] = mn[n + 1][0] = 1e9;
    for(int j = 1; j < 20; j++) for(int i = 1; i <= n + 1; i++) {
        nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
		mn[i][j] = min(mn[i][j - 1], mn[nxt[i][j - 1]][j - 1]);
    }
}

void solve()
{
    cin >> n >> s; s = '.' + s;
    if(n <= 200) {
        int cnt = 0;
        for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) {
            stack<int> st;
            bool flag = 1;
            for(int k = i; k <= j; k++) {
                if(s[k] == '(') st.push(1);
                else if(s[k] == '{') st.push(2);
                else if(st.empty()) { flag = 0; break; }
                else if(s[k] == ')' && st.top() == 2) { flag = 0; break; }
                else if(s[k] == '}' && st.top() == 1) { flag = 0; break; }
                else st.pop();
            }
            if(st.size()) flag = 0;
            cnt += flag;
        }
        cout << cnt << endl;
    }
    else {
        for(int i = 1; i <= n; i++) a[i] = a[i - 1] + (s[i] == '(' ? 1 : -1);
        init();
        for(int i = 1; i <= n; i++) mp[a[i] + N].push_back(i);
        ll cnt = 0;
        for(int i = 1; i < n; i++) if(s[i] == '(') {
            // a[i - 1] == a[j] && min(a[i], ..., a[j]) >= a[i - 1]
            int r = i;
            for(int i = 19; i >= 0; i--) if(mn[r][i] >= a[i - 1]) r = nxt[r][i];
            const auto &v = mp[a[i - 1] + N];
            cnt += upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), i);
        }
        cout << cnt << endl;
        for(int i = 1; i <= n; i++) mp[a[i] + N].pop_back();
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << endl;
        solve();
    }
}

 

 

3. 루머

 

첫 관찰은 초기 집합에 없는 팔랑귀가 아닌 사람은 전파를 하지 못한다는 것이다. 이런 사람이 루머를 믿으려면 양쪽에서 루머를 들어야 하는데, 그럼 양쪽이 다 막히기 때문이다. 그러니 $t$를 처음에 다 써버리고 왼쪽으로 얼마나 전파할 수 있는지를 저장해주자. 그러면 이제 각 사람이 덮을 수 있는 구간이 주어진 평범한 디피 꼴에, 팔랑귀가 아닌 사람을 덮으려면 양쪽에서 모두 덮어야 한다는 조건이 추가된 문제를 풀면 된다. 이는 아래처럼 상태를 잡고, 전파를 최대한으로 할 수 있도록 전이해주되 팔랑귀가 아닌 사람을 초기 집합에 넣는 것을 고려해주었다. 아래처럼 짠 후 틀리길래 열심히 스트레스 돌려서 디버깅했고, 대회 종료 3분 전에 극적으로 맞았다. 메모는 불완전한 부분이 있으니 코드를 참고하자.

 

 

#include <bits/stdc++.h>
using namespace std;
const int N = 5001;

int a[N], l[N] = {0, 1}, dp[N][N][2];

int solve()
{
    int n, m, k, mx = 1; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> m >> k;
    for(int i = 2; i <= n; i++) l[i] = a[i - 1] ^ 1 ? i - 1 : max(l[i - 1], i - k);
    for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) dp[i][j][0] = dp[i][j][1] = -1e9;
    for(int i = 0; i <= n; i++) dp[i][0][0] = 0; dp[1][1][0] = 1;
    for(int i = 2; i <= n; i++) for(int j = 1; j <= m; j++) {
        dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
        const int &p = l[l[i]];
        if(a[i] ^ 2) {
            if(a[p] ^ 2) dp[i][j][0] = max(dp[i][j][0], max(dp[p - 1][j - 1][0], dp[p - 1][j - 1][1]) + i - p + 1);
            else dp[i][j][0] = max(dp[i][j][0], max(max(dp[p - 1][j - 1][0], dp[p - 1][j - 1][1]), dp[p][j - 1][1] + 1) + i - p);
        }
        else {
            if(a[l[i]] ^ 2) dp[i][j][0] = max(dp[i][j][0], max(dp[l[i] - 1][j - 1][0], dp[l[i] - 1][j - 1][1]) + i - l[i] + 1);
            else dp[i][j][0] = max(dp[i][j][0], max(max(dp[l[i] - 1][j - 1][0], dp[l[i] - 1][j - 1][1]), dp[l[i]][j - 1][1] + 1) + i - l[i]);
            if(a[p] ^ 2) dp[i][j][1] = max(dp[p - 1][j - 1][0], dp[p - 1][j - 1][1]) + i - p;
            else dp[i][j][1] = max(max(dp[p - 1][j - 1][0], dp[p - 1][j - 1][1]), dp[p][j - 1][1] + 1) + i - p - 1;
        }
        mx = max({mx, dp[i][j][0], dp[i][j][1]});
    }
    return mx;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << endl;
        cout << solve() << '\n';
    }
}

 

 

4. 막대기 연결

 

섭태는 적당히 긁어도 180점이나 준다. 풀태는 생긴 게 굉장히 간단한데, 식을 정리해보면 완전 monotone queue optimization처럼 생겼다. 그런데 이거보다 요구하는 게 한 차원 더 많아서 계속 고민해보았지만 방법을 찾지 못했다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3001;

ll x[N], h[N], a[N][N], b[N][N];

void solve()
{
    int n; cin >> n;
    if(n > 3000) {
        int x, y, q;
        while(n--) cin >> x >> y;
        for(cin >> q; q--; ) {
            int l, r; cin >> l >> r;
            cout << 0 << endl;
        }
        return;
    }
    for(int i = 1; i <= n; i++) cin >> x[i] >> h[i];
    for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) a[i][j] = (x[j] - x[i]) * (h[i] + h[j]);
    for(int i = 1; i < n; i++) b[i][i] = 9e18;
    for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) b[i][j] = min(b[i][j - 1], a[i][j]);
    int q; cin >> q;
    while(q--) {
        int l, r; cin >> l >> r;
        ll mn = 9e18;
        for(int i = l; i < r; i++) mn = min(mn, b[i][r]);
        cout << mn << endl;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << endl;
        solve();
    }
}

 

 

5. 스마트 아파트 건설

 

60점 달다

 

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

void solve()
{
    int n, m, k, cnt = 0; cin >> n >> k >> m;
    vector<int> a(n), u(m), v(m);
    iota(a.begin(), a.end(), 1);
    for(int i = 0; i < m; i++) cin >> u[i] >> v[i], u[i]--, v[i]--;
    do {
        bool flag = 1;
        for(int i = 0; i < m; i++) if(a[u[i]] + a[v[i]] > k) flag = 0;
        cnt += flag;
    } while(next_permutation(a.begin(), a.end()));
    cout << cnt << endl;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << endl;
        solve();
    }
}