딱히 주간은 아닌 회고록

많이 밀려버렸지만 그래도 공부를 위해 그동안 풀었던 문제들 중 인상 깊었던 문제들 위주로 정리를 해보려 합니다.

 

/<18288> + /<18289> 팀연습 / 팀연습 더

여러 조건이 복합적으로 엮여 있는 상태 전이를 다루는 DP 문제입니다. 모든 경우의 수를 한번에 고려한 하나의 점화식을 바로 만들기는 어려워 보이니 문제에 주어진 조건을 최대한 많이 상태 공간으로 옮겨서 점화식의 상태 전이를 단순하게 해봅시다. 저는 다음과 같이 나눴습니다.

 

$ A_{i, true/false, m} = A$가 $($ $i$ 번째 문제를, $C$가 문제를 풀거나/안 풀은 상태에서, $m = A$가 푼 문제수$\mod K$ $)$ 일때, 푸는 경우의 수.

$B$, $C$도 비슷하게 정의 가능합니다. 이렇게 하면 초항과 상태 전이 또한 다음과 같이 정의 가능합니다. 길이가 좀 있으니 코드로 대체합니다.

 

for(int i=0; i<K; i++){
            A[1][0][i] = ((i==1 || K==1) ? 1 : 0);
            B[1][0][i] = (i==0 ? 1 : 0);
            C[1][1][i] = (i==0 ? 1 : 0);
        }
        for(int i=2; i<=N; i++){
            for(int k=0; k<K; k++){
                A[i][0][k] = 
                A[i-1][0][((k-1)+K)%K] + 
                B[i-1][0][((k-1)+K)%K];

                A[i][1][k] = 
                A[i-1][1][((k-1)+K)%K] +
                B[i-1][1][((k-1)+K)%K] +
                C[i-1][1][((k-1)+K)%K];

                B[i][0][k] = 
                A[i-1][0][k];

                B[i][1][k] =
                A[i-1][1][k] + C[i-1][1][k];

                C[i][1][k] = 
                A[i-1][0][k] + A[i-1][1][k] +
                B[i-1][0][k] + B[i-1][1][k] +
                C[i-1][1][k];

                A[i][0][k] %= MOD;
                A[i][1][k] %= MOD;
                B[i][0][k] %= MOD;
                B[i][1][k] %= MOD;
                C[i][0][k] %= MOD;
                C[i][1][k] %= MOD;
            }
        }
        cout << ((A[N][1][0]%MOD) + 
        (B[N][1][0] % MOD) +
        (C[N][1][0] % MOD)) % MOD;

 

다만 $K = 0$인 입력이 존재함으로 이에 대한 예외 처리를 해줘야 합니다. 크게 어렵지는 않습니다. 그냥 $A$는 문제를 안 푼다 생각하고 $B$랑 $C$에 대한 문제만으로 생각하면 되니까요.

그리고 나면 이 점화식이 선형 점화식이라는 점을 사용해 행렬 제곱을 통해 $N$ 번째 항을 구할 수 있습니다. 이렇게 하면 팀 연습 더 (현 시점 P2) 까지 해결 가능합니다. 의외로 코드는 더 깔끔합니다.

 

Matrix res(5*K, 1); Matrix m(5*K, 5*K);

        for(int i=0; i<K; i++){
            res.Mat[K + i][0] = ((i==1 || K==1) ? 1 : 0);
            res.Mat[K*3 + i][0] = (i==0 ? 1 : 0);
            res.Mat[K*4 + i][0] = (i==0 ? 1 : 0);
        }
        //A
        for(int i=0; i<K; i++){
            m.Mat[i][((i-1)+K)%K] = 1;
            m.Mat[i][2*K +((i-1)+K)%K] = 1;
            m.Mat[i][4*K +((i-1)+K)%K] = 1;
        }
        //A'
        for(int i=0; i<K; i++){
            m.Mat[K+i][K+((i-1)+K)%K] = 1;
            m.Mat[K+i][3*K +((i-1)+K)%K] = 1;
        }
        //B
        for(int i=0; i<K; i++){
            m.Mat[2*K+i][i] = 1;
            m.Mat[2*K+i][4*K + i] = 1;
        }
        //B'
        for(int i=0; i<K; i++){
            m.Mat[3*K+i][K+i] = 1;
        }
        //C
        for(int i=0; i<K; i++){
            m.Mat[4*K+i][i] = m.Mat[4*K+i][K+i] = m.Mat[4*K+i][2*K+i] = m.Mat[4*K+i][3*K+i] = m.Mat[4*K+i][4*K+i] = 1;
        }
        N -= 1;
        Matrix ret = m.exp(N) * res;
        cout << (ret.Mat[0][0] + ret.Mat[2*K][0] + ret.Mat[4*K][0])%MOD;

 

/<2515> 전시장

G2치고는 쉽다고 느꼈던 문제인데 그래도 발상 과정을 정리해보려고 포함했습니다. 일단 문제 지문이 뭔가 그림들을 높이 기준으로 정렬을 해보고 싶게 만듭니다. 높이가 더 낮은 그림을 뒤에 배치 하면 가격이 얼마든 못 팔게 되니까요.

일단 어떤 특정 부분 집합을 생각하긴 어려우니 $i$ 번째 그림을 무조건 팔때 얻을 수 있는 최대 이익을 계산하는 방법을 생각 해봅시다 (이하 $dp_i$. 어라 이거 스폰가?).

$i$ 번째 그림의 높이를 $H_i$라고 하면, 높이가 $H_i - S$ 이하인 그림 $j$를 앞에 둠으로서 $i$ 번째 그림을 팔때 이익을 늘릴 수 있습니다 (팔 수 있는걸 굳이 안 팔면 손해라는 느낌?). 그러면 $dp_i = C_i + max(dp_j)\; H_j \le H_i - S$ 라는 결론을 도출 가능합니다.

그러면 $max(dp_j)$를 빠르게 찾을 방법이 필요한데 점화식의 구조상 높이가 낮은 그림들에 대한 결과가 먼저 계산되야 하기 때문에 (부분 문제가 이미 해결 되었음을 보장하려면) 앞서 언급했듯이 그림들을 높이에 대한 정렬을 해볼 수 있습니다. 그러면 $H_j \le H_i - S$인 가장 큰 $j$를 이진 탐색을 통해 구할 수 있고. $max(dp_j)$는 그 $j$까지의 누적 $max$ 값으로 관리 해줄 수 있으니 문제를 $N log N$시간에 해결 가능합니다.

int N; ll S; cin >> N >> S;
    vector<pll>v(N+1); for(int i=1; i<=N; i++){
        cin >> v[i].fr >> v[i].sc;
    } sort(all(v));

    vector<ll>H(N + 1, 0), C(N + 1, 0); for(int i=1; i<=N; i++){
        H[i] = v[i].fr, C[i] = v[i].sc;
    }
    vector<ll>sum(N + 1), prmax(N + 1);
    sum[0] = 0, prmax[0] = 0;

    ll ans = 0;
    for(int i=1; i<=N; i++) {
        ll target = v[i].fr - S;
        int it = upper_bound(all(H), target) - H.begin() - 1;
        // cout << i << ' ' << it << endl;
        sum[i] = prmax[it] + C[i];
        prmax[i] = max(prmax[i-1], sum[i]);
        ans = max(ans, sum[i]);
    } cout << ans;

 

/<24240> Doomsday

예전에 유사한 문제를 동아리 내전에 출제한 적이 있어서 쉽게 풀었습니다. 물을 모은 상태와 음식을 모은 상태를 각각 다른 비트로 저장하면 비트마스킹을 통해 상태를 쉽게 저장 가능합니다. 나머지는 그냥 다익스트라입니다.

 

https://project-ps.com/problem/65

Project PS

많관부 :blobthumbsup:

 

/<24240> Parcel

 

모든 수가 서로 다르다는 점을 사용하면 어떤 두 수의 합이 $S$라 했을 때 더해서 $S$가 나오는 쌍이 여러개 있다면 이 쌍들에 속한 수는 전부 다르다는 것을 알 수 있습니다.

모든 $(i, j)$ 쌍에 대해 $A_i + A_j$가 몇번 나왔는지 저장해 둡니다. 이 때 두번 이하 나온 합들에 대해서는 정확히 어떤 쌍이 그 합을 만들었는지도 중요하니 이 또한 같이 저장합니다.

다시 모든 $(i, j)$ 쌍을 돌며 $W - (A_i + A_j)$가 몇번 만들어졌는지 확인 합니다. 두번보다 많이 만들어 졌다면 첫 줄로 인해 $i$와 $j$를 모두 포함하지 않은 쌍이 무조건 존재 했을 것이니 YES. 아니라면 $W - (A_i + A_j)$를 만든 조합 중 $i$와 $j$를 모두 안 쓴 조합이 존재하는지 체크하면 됩니다.

 

처음엔 익명의 12월 17일생 때문에 배열을 $N/2$크기 두개로 나눠서 $(4, 0), (1, 3), (2, 2)$로 경우를 나눴는데 그럴 필요는 없었네요 (물론 결론적으로 두개씩 나눈다는 발상이 중요하긴 했다).

 

 

팀 연습 후기도 써야 하는데 언제 쓰지.