SCPC 2023 본선 후기

 

실력 부족, 연습 부족이라 그렇게 아쉽지는 않다. 다만 2번을 건드리지 않았으면 어땠을까 하는 생각...

 

 

1. 돌 게임

 

1번은 뭐 그런디 수를 구하라고 하진 않겠지라는 믿음으로 보면 홀짝성이 중요하다는 것을 알 수 있다. 10분 정도 걸렸다.

 

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

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    int cnt = 0;
    for(int i = 1; i <= n; i++) if(a[i] & 1) cnt++;
    cnt += n - 1;
    cout << (cnt & 1 ? "1st" : "2nd") << '\n';
}

int 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. 협동로봇

 

1번을 풀자마자 2번을 잡았다. 대충 식을 열심히 정리하면 DP 식이 나오고, 이걸 쿼리마다 CHT를 써서 $O(QNlogN)$에 해결하는 풀이를 떠올렸다. 이걸 2시간 30분 넘게 열심히 짰는데 0점을 받고 멘탈이 나갔다. 딱히 놓친 부분도 없고 코딩 실수도 없어서 풀이가 틀렸다는 결론을 내리고 4번으로 넘어갔다. 그런데 대회 끝나고 들은 풀이와 같은 것 같다..

 

 

4. 그릇

 

일단 많이 풀렸으니까 쉽다는 믿음을 가지고 시작했다. DP이긴 할텐데, 문제를 그대로 옮기려면 답이 없다. 그런데 그릇 쌍의 수를 구하는 과정을 생각해 보면 $K$가 $2N-3$을 넘을 수 없다. 상태가 한 차원 줄었으니 이제 상태를 정의할 수 있다. 그러나 일반적으로 떠올리는 큰 거를 추가하는 식으로 짜면 전이가 답이 없다. 그래서 반대로 작은 거를 추가한다고 생각해 보면 전이가 굉장히 쉬워진다. 메모리가 빠듯해 보여서 토글링을 했는데 그럴 필요가 없었다고 한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 5001;

ll dp[2 * N], pd[2 * N];

void solve() {
    int n, k; cin >> n >> k;
    if(k < n - 1 || k > 2 * n - 3) return cout << 0 << '\n', void();
    dp[1] = 2;
    for(int i = 2; i < n; i++) {
        for(int j = i - 1; j <= 2 * i - 3; j++) {
            pd[j + 1] = (pd[j + 1] + 2 * dp[j]) % mod;
            pd[j + 2] = (pd[j + 2] + (i - 1) * dp[j]) % mod;
        }
        for(int j = i; j < 2 * i; j++) dp[j] = pd[j], pd[j] = 0;
    }
    cout << dp[k] << '\n';
}

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

 

 

3. 트리 해체

 

보자마자 트리 색칠이 생각 안 날 수가 없는데 20분 남은 상황에서 당연히 짤 자신은 없고, 섭태나 긁으려 했는데 그마저 의문의 시간초과를 받으며 0점으로 끝났다.