SCPC 2023 1차 예선 후기

2차는 가겠지?

대충 풀어도 2차는 간다고 해서 올솔하려는 노력을 들이진 않았다.

 

 

1. 증강현실 배달 안경

 

확장 유클리드를 쓰면 로그시간에 되지만, 범위가 작아 그냥 다 해봐도 된다.

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        int n, a, b, mx = 0; cin >> n >> a >> b;
        for(int i = 0; i <= n; i += a) if((n - i) % b == 0) mx = max(mx, i / a + (n - i) / b);
        cout << "Case #" << T << '\n' << mx << '\n';
    }
}

 

 

2. 딸기 수확 로봇

 

한번 이하로 방향을 바꾸는 것을 양쪽으로 시도해보면 된다.

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << '\n';
        int n, d, z = 0; cin >> n >> d;
        vector<int> a, b;
        while(n--) {
            int x; cin >> x;
            if(x < 0) a.push_back(-x);
            else if(x > 0) b.push_back(x);
            else z++;
        }
        int mx = 0;
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        for(int i = 0; i < a.size(); i++) {
            if(a[i] > d) break;
            mx = max(mx, i + 1);
            if(2 * a[i] < d) {
                int k = upper_bound(b.begin(), b.end(), d - 2 * a[i]) - b.begin();
                mx = max(mx, i + 1 + k);
            }
        }
        for(int i = 0; i < b.size(); i++) {
            if(b[i] > d) break;
            mx = max(mx, i + 1);
            if(2 * b[i] < d) {
                int k = upper_bound(a.begin(), a.end(), d - 2 * b[i]) - a.begin();
                mx = max(mx, i + 1 + k);
            }
        }
        cout << mx << '\n';
    }
}

 

 

3. 장난감

 

일단 모든 칸이 $1$ 이상이면 주기가 $1$이다. 그리고 $a_i$의 합이 $n$ 이상이면 언젠가 모든 칸이 채워질 것이라고 예상할 수 있다. 그렇지 않다면 모든 칸은 $0$ 또는 $1$이 될 것이고, 이때 반복되는 주기를 찾으면 된다.

먼저, $0$과 $1$로만 이루어진 모양을 찾아야 한다. 많은 예시를 시도해본 결과, 수가 다 펴지기까지 필요한 횟수는 $n-1$을 넘지 않는다. 구현의 편의를 위해 $n$번 이후의 모양을 찾자. 우선 1 이상의 수가 연속한 덩어리를 생각해보자. 덩어리에 2 이상의 수가 없다면 그냥 그대로 $n$번 밀어주면 된다. 그렇지 않은 경우를 관찰해보면, 2 이상의 수 중 가장 오른쪽에 있는 수가 결국 맨 왼쪽이 될 때까지 유지된다는 것을 알 수 있다. 이 관찰을 이용하면 이 덩어리가 다 펴질 때까지 얼마나 걸리는지, 그리고 $n$번 이동 후에는 어디에 위치하는지를 찾을 수 있다. 이를 모든 덩어리에 대해 처리해주면 된다.

어떤 수열에서 주기를 찾는 것은 KMP로 선형에 할 수 있음이 유명한데, 그냥 약수만 확인해줘도 돌 것 같아서 그렇게 구현했다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << '\n';
        int n; cin >> n;
        vector<ll> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        ll sum = accumulate(a.begin() + 1, a.end(), 0LL);
        if(!sum || sum >= n) { cout << 1 << '\n'; continue; }
        deque<pair<int, int>> dq;
        for(int i = 1; i <= n; i++) if(a[i]) {
            if(dq.empty() || dq.back().second + 1 < i) dq.push_back({i, i});
            else dq.back().second++;
        }
        vector<int> b(n + 1);
        if(a[1] && a[n]) {
            int l = dq.back().first, r = dq[0].second, x = 0, y = 0, z = 0;
            dq.pop_front(); dq.pop_back();
            for(int i = l; i <= n; i++) {
                x += a[i];
                if(a[i] > 1) z = i;
            }
            for(int i = 1; i <= r; i++) {
                x += a[i];
                if(a[i] > 1) z = i;
            }
            if(!z) {
                for(int i = l; i <= n; i++) b[i] = 1;
                for(int i = 1; i <= r; i++) b[i] = 1;
            }
            else if(r < z) {
                for(int i = l; i < z; i++) y += a[i];
                y += a[z] - 1;
                z = (z + n - y - 1) % n + 1;
                for(int i = 0; i < x; i++) b[(z + i - 1) % n + 1] = 1;
            }
            else {
                for(int i = l; i <= n; i++) y += a[i];
                for(int i = 1; i < z; i++) y += a[i];
                y += a[z] - 1;
                z = (z + n - y - 1) % n + 1;
                for(int i = 0; i < x; i++) b[(z + i - 1) % n + 1] = 1;
            }
        }
        for(auto &lr : dq) {
            int l = lr.first, r = lr.second, x = 0, y = 0, z = 0;
            for(int i = l; i <= r; i++) {
                x += a[i];
                if(a[i] > 1) z = i;
            }
            if(!z) {
                for(int i = l; i <= r; i++) b[i] = 1;
            }
            else {
                for(int i = l; i < z; i++) y += a[i];
                y += a[z] - 1;
                z = (z + n - y - 1) % n + 1;
                for(int i = 0; i < x; i++) b[(z + i - 1) % n + 1] = 1;
            }
        }
        for(int i = 1; i <= n; i++) if(n % i == 0) {
            bool flag = 1;
            for(int j = i + 1; j <= n; j++) if(b[j - i] ^ b[j]) flag = 0;
            if(flag) { cout << i << '\n'; break; }
        }
    }
}

 

 

4. 최적의 프로세스 수행 순서 (120점)

 

딱봐도 KMP 같은 문자열 알고리즘에 DP를 섞으면 풀리게 생겼다. 그러나 문자열 고민하기는 귀찮고 이미 커트는 넘은 것 같아서 대충 쉬운 DP 긁고 끝냈다. $O(N^3)$을 짠 것 같은데 120점을 받아서 당황했지만, 알고 보니 한쪽으로만 밀어주고 있어서 $O(N^2)$가 맞았다.

 

#include <bits/stdc++.h>
using namespace std;
string s, t;
int n, m, dp[10001][10001];
int f(int l, int r) {
    if(l > r) return 0;
    int &ret = dp[l][r];
    if(ret) return ret;
    ret = 1e9;
    for(int i = 0; i < m; i++) {
        if(l + i > r || s[l + i] ^ t[i]) break;
        ret = min(ret, f(l + i + 1, r) + 1);
    }
    return ret;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for(int T = 1; T <= tc; T++) {
        cout << "Case #" << T << '\n';
        cin >> s >> t;
        n = s.size(), m = t.size();
        if(n > 10000 || m > 10000) { cout << -1 << '\n'; continue; }
        s = '.' + s;
        for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) dp[i][j] = 0;
        int ans = f(1, n);
        cout << (ans < 1e9 ? ans : -1) << '\n';
    }
}