JusticeHui가 PS하는 블로그

총평
1, 2, 3, 4번 모두 작년/재작년보다 훨씬 어려워졌습니다. 많은 구현을 요구하는 1번을 풀고 나면 전형적인 문제일지 애드혹일지 감이 잡히지 않아 오만 가지 생각이 다 드는 2번과 3번 문제가 머리를 때리고, 뒤쪽 문제를 읽어보겠다고 4~5번으로 넘어가면 만점자가 한 자리 수인 문제들이 반겨줍니다. 4번과 5번은 만점자가 한 자리 수이고 풀 태스크를 제외한 모든 서브태스크를 긁는 건 쉽기 때문에 별로 문제가 안 되었지만, 3번이 정말… 힘들었습니다. 1차가 쉬웠던 이유가 2차에 어려운 문제를 몰아넣어서 그런 건가? 올해는 오랜만에 3번을 안 풀고도 본선에 진출하는 사람이 나올 것 같기도 합니다.
문제
      점수
      제출 횟수
    
1. 타이젠 윷놀이
      100/100
      1 (100)
    
2. 괄호 문자열
      200/200
      2 (0 → 200)
    
3. 루머
      300/300
      3 (90 → 180 → 300)
    
4. 막대기 연결
      180/400
      1 (180)
    
5. 스파트 아파트 건설
      60/400
      1 (60)
    
총점
      840/1400
      8
    
타이젠 윷놀이
말 하나를 이용해 윷놀이를 한다. 윷을 $N$번 던진 결과가 차례대로 주어지고, 이 $N$번의 행동을 $K$번 반복해서 총 $N\times K$번 말을 움직일 때, 말이 몇 바퀴 도는지 구하는 문제
$T \leq 87;$ $N,K \times 10^5;$ 백도는 주어지지 않음
다음과 같이 윷놀이 판의 각 칸에 번호를 붙입시다. 29는 한 바퀴를 온전히 돌았다는 것을 표시하기 위한 칸입니다.
15 - 14 - 13 - 12 - 11 - (10)
|  \                   /  |
16   24             25    9
|       \         /       |
17        23   26         8
|          (22)           |
18        27   21         7
|       /         \       |
19   28             20    6
|  /                   \  |
(0) - 1 -  2 -  3 -  4 - (5)
ㄴ 29
5번, 10번, 22번 칸은 그냥 지나가는 것과 멈추는 것을 다르게 취급해야 하므로 두 개의 점으로 분리해서 생각해야 합니다. 또한, 0번 칸은 시작점의 역할과 도착점의 한 칸 전의 역할을 모두 수행하기 때문에 0번 칸도 두 개의 점으로 분리해서 생각해야 합니다. 따라서 총 34개의 정점을 이용해 윷놀이 판을 관리합니다.
$v$번 정점의 다음 칸을 $\text{next}(v)$는 정점 개수에 비례하는 시간에 전처리할 수 있고, 이를 이용하면 $v$에서 $k (1 \leq k \leq 5)$칸 이동한 결과인 $\text{move}(v, k)$도 $5 \times$ (정점 개수) 정도에 전처리할 수 있습니다.
실제 문제의 정답을 구하는 것은, 각 칸에서 $N$번 이동했을 때 도착점에 가는 횟수와 종료 상태를 구하면 됩니다. 유효한 정점은 34개로 상수 개이므로 $O(N)$ 시간에 모두 전처리할 수 있고, $K$번 반복해서 이동한 결과는 전처리한 정보를 이용해 $O(K)$ 시간에 구할 수 있습니다.
int ID(int i, int j){ return i * 2 + j; }
bool IsStart(int v){ return v != ID(5,0) && v != ID(10,0) && v != ID(22,0) && Next[v] != -1; }
void Init(){
    memset(Next, -1, sizeof Next);
    S = ID(0,0); T = ID(29,0);
    for(int i=0; i<19; i++) Next[ID(i,0)] = ID(i+1,0);
    Next[ID(19,0)] = ID(0,1);
    Next[ID(5,1)] = ID(20,0); Next[ID(24,0)] = ID(15,0);
    for(int i=20; i<24; i++) Next[ID(i,0)] = ID(i+1,0);
    Next[ID(10,1)] = ID(25,0); Next[ID(25,0)] = ID(26,0);
    Next[ID(26,0)] = ID(22,1); Next[ID(22,1)] = ID(27,0);
    Next[ID(27,0)] = ID(28,0); Next[ID(28,0)] = ID(0,1);
    Next[ID(0,1)] = ID(29,0); Next[ID(29,0)] = ID(29,0);
    for(int i=0; i<61; i++){
        for(int j=0; j<5; j++){
            int v = i;
            for(int k=0; k<=j; k++) v = Next[v];
            Go[i][j] = v ^ !IsStart(v);
        }
    }
}
void Solve(){
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i];
    int move[61], get[61];
    for(int i=0; i<61; i++){
        if(!IsStart(i)) continue;
        int now = i, cnt = 0;
        for(int j=1; j<=N; j++){
            now = Go[now][A[j]-1];
            if(now == T) cnt++, now = S;
        }
        move[i] = now; get[i] = cnt;
    }
    long long now = S, res = 0;
    for(int i=0; i<K; i++) res += get[now], now = move[now];
    cout << res << "\n";
}
괄호 문자열
소괄호와 중괄호로 구성된 괄호 문자열이 주어지면, 올바른 괄호 문자열인 부분 문자열의 개수를 구하는 문제
$N \leq 10^6;$ $\sum N \leq 42 \times 10^6$
처음 문제를 보면 별의별 생각이 다 듭니다. 처음에는 끝점을 고정한 다음, 문자열의 prefix를 쪼갤 수 없는 괄호 문자열들로 분할해서 가능한 시작점의 개수를 세는 방식으로 접근했지만, 별다른 소득을 얻지 못했습니다. 구체적으로, 문자열의 분할을 incremental하게 관리할 방법도 잘 안 보였고, 관리할 수 있다고 하더라도 선형 시간에 하기는 어려울 것 같아서 포기했습니다.
문자열을 maximal한 올바른 괄호 문자열들로 분할하면, 각 그룹을 독립적으로 생각해도 된다는 것을 알 수 있습니다. 서로 다른 두 그룹에 모두 걸쳐 있는 올바른 괄호 문자열이 있다면 maximal한 문자열들로 분할한 것이 아니기 때문입니다. 따라서 스택을 이용해 maximal한 올바른 괄호 문자열로 분리한 다음, 각각의 올바른 괄호 문자열에서의 답을 선형 시간에 구하면 문제를 해결할 수 있습니다. 분할된 각 문자열은 올바른 괄호 문자열이기 때문에 소괄호와 중괄호의 구분을 신경 쓰지 않아도 되므로 구현이 쉬워집니다.
bool Match(char a, char b){ return a == '(' && b == ')' || a == '{' && b == '}'; }
bool Open(char c){ return c == '(' || c == '{'; }
ll Go(const string &s){
    ll res = 0;
    vector<ll> val{0};
    for(auto c : s){
        if(Open(c)) val.push_back(0);
        else{
            res += val.back() * (val.back() + 1) / 2;
            val.pop_back(); val.back() += 1;
        }
    }
    res += val.back() * (val.back() + 1) / 2;
    return res;
}
vector<string> Tokenizer(const string &s){
    int n = s.size();
    vector<string> res;
    vector<int> idx(n, -1), stk;
    for(int i=0; i<n; i++){
        if(Open(s[i])) stk.push_back(i);
        else if(!stk.empty() && Match(s[stk.back()], s[i])){
            idx[stk.back()] = i; idx[i] = stk.back(); stk.pop_back();
        }
        else stk.clear();
    }
    for(int i=0, j=0; i<n; i=j){
        if(idx[i] == -1){ j++; continue; }
        while(j < n && idx[j] != -1) j++;
        res.push_back(s.substr(i, j-i));
    }
    return res;
}
ll Solve(const string &s){
    ll res = 0;
    for(const auto &i : Tokenizer(s)) res += Go(i);
    return res;
}
루머
$N$명의 사람이 일렬로 서있다. 시간 $t$에 $i$번째 사람과 인접한 사람 중 $A_i$명 이상이 루머를 믿고 있으면, $t+1$ 이후부터 $i$번째 사람도 루머를 믿는다. $t = 0$인 시점부터 루머를 믿는 사람을 최대 $M$명 선택할 수 있을 때, $T$ 시간이 지난 후 루머를 믿는 사람의 최댓값을 구하는 문제
$M,T \leq N \leq 5\,000;$ $1 \leq A_i \leq 2$
이 문제도 다양한 시도를 했습니다. 처음에는 그래프로 접근해서 위상 정렬 같은 느낌으로 풀려고 했지만 실패했습니다. 그다음에는 $C(i, j) :=$ $[i,j]$ 구간을 활성화하는 데 필요한 최소 선택 횟수로 정의한 테이블을 어떻게든 계산한 다음, $D(i, k) := $ $[1, i]$ 구간을 $k$명으로 시작해서 활성화할 수 있는 최대 칸 개수 같은 것을 계산하려고 했고, 이 방법으로도 아무 소득도 얻지 못했습니다.
그다음 접근은 효과가 있었는데, $D(i, j) :=$ $i$명을 선택했고, 그중 마지막으로 선택한 사람이 $j$일 때 활성화되는 칸 개수의 최댓값으로 정의해서 계산하는 것이었습니다. 편의상 $L_i,R_i$를 $i$의 왼쪽/오른쪽에 있는 가장 가까운 2번 칸의 인덱스, $S_i = \max(i-t,L_i+1)$, $E_i=\min(i+t, R_i-1)$으로 정의합시다. $D(i, j)$는 항상 정확히 $E_i$까지 활성화하기 때문에, 이후에 선택하는 위치에 따라 2번 칸의 활성화 여부를 어렵지 않게 추적할 수 있습니다. 구체적으로, $D(i+1,k) \leftarrow D(i,j)$ 형태의 상태 전이는 다음과 같이 8가지로 나눠서 계산할 수 있습니다.
$j$와 $k$의 담당 구간이 겹치지 않는 경우 ($j+2t < k \leq N$)
    
$D(i+1,k) \leftarrow D(i,j) + E_k - S_k + 1$
$j$와 $k$의 구간이 겹치지만 서로의 위치를 포함하진 않는 경우 ($j+t < k \leq j+2t$)
    
$j$의 오른쪽, $k$의 왼쪽에 2번 칸이 없는 경우 ($R_j = \infty \text{ and } L_k = -\infty$)
        
$D(i+1,k) \leftarrow D(i,j) + E_k - E_j$
2번 칸이 존재하지만, 두 구간의 교집합이 아닌 위치에 하나 이상 존재하는 경우 ($R_j < k-t \text{ or } j+t < L_k$)
        
$D(i+1,k) \leftarrow D(i,j) + E_k - \max(S_k, E_j+1) + 1$
1개의 2번 칸이 두 구간의 교집합에 위치하는 경우 ($R_j = L_k$)
        
$D(i+1,k) \leftarrow D(i,j) + E_k - E_j$
2개 이상의 2번 칸이 두 구간의 교집합에 위치하는 경우
        
$D(i+1,k) \leftarrow D(i,j) + E_k - S_k + 1$
$j$와 $k$의 구간이 서로의 위치를 포함하는 경우 ($j < k \leq j+t$)
    
$j$와 $k$ 사이에 2번 칸이 없는 경우 ($k \leq R_j \text{ or } L_k \leq j$)
        
$D(i+1,k) \leftarrow D(i,j) + E_k - E_j$
$j$와 $k$ 사이에 2번 칸이 정확히 1개 있는 경우 ($R_j = L_k$)
        
$D(i+1,k) \leftarrow D(i,j) + E_k - E_j$
$j$와 $k$ 사이에 2번 칸이 2개 이상 있는 경우
        
$D(i+1,k) \leftarrow D(i,j) + E_k - S_k + 1$
이 상태 전이를 naive하게 구현하면 $O(N^3)$ 시간에 문제를 풀어 90점을 받을 수 있습니다.
inline int GetL(int x){ return max(L[x]+1, x-T); }
inline int GetR(int x){ return min(R[x]-1, x+T); }
inline int Only(int x){ return GetR(x) - GetL(x) + 1; }
void Init(){
    fill(L+1, L+N+1, 0);
    fill(R+1, R+N+1, N+1);
    for(int i=1; i<=N; i++) for(int j=i-1; j>=max(1,i-T); j--) if(A[j] == 2) { L[i] = j; break; }
    for(int i=1; i<=N; i++) for(int j=i+1; j<=max(N,i+T); j++) if(A[j] == 2) { R[i] = j; break; }
}
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    cin >> M >> T;
    Init();
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) D[i][j] = nINF;
    for(int i=1; i<=N; i++) D[1][i] = Only(i);
    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            for(int k=j+1; k<=N; k++){
                // case 1. no intersect (j+t < k-t)
                if(j + T < k - T) D[i+1][k] = max(D[i+1][k], D[i][j] + Only(k));
                // case 2. intersect, but not contain
                else if(j + T < k){
                    // case 2-1. no two
                    if(R[j] == N+1 && L[k] == 0) D[i+1][k] = max(D[i+1][k], D[i][j] + GetR(k) - GetR(j));
                    // case 2-2. exist two, but outside
                    else if(R[j] == N+1 || L[k] == 0 || R[j] < k-T || j+T < L[k]) D[i+1][k] = max(D[i+1][k], D[i][j] + GetR(k) - max(GetL(k), GetR(j)+1) + 1);
                    // case 2-3. exist only one two, inside
                    else if(R[j] == L[k]) D[i+1][k] = max(D[i+1][k], D[i][j] + GetR(k) - GetR(j));
                    // case 2-4. exist at least two twos
                    else D[i+1][k] = max(D[i+1][k], D[i][j] + Only(k));
                }
                // case 3. intersect, and contain
                else{
                    // case 3-1. not between
                    if(k <= R[j] || L[k] <= j) D[i+1][k] = max(D[i+1][k], D[i][j] + GetR(k) - GetR(j));
                    // case 3-2. exist only one two, inside
                    else if(R[j] == L[k]) D[i+1][k] = max(D[i+1][k], D[i][j] + GetR(k) - GetR(j));
                    // case 3-3. exist at least two twos
                    else D[i+1][k] = max(D[i+1][k], D[i][j] + Only(k));
                }
            }
        }
    }
    cout << *max_element(D[M]+1, D[M]+N+1) << "\n";
}
이제 이 풀이를 $O(N^2 \log N)$, 더 나아가 $O(N^2)$으로 최적화시켜 봅시다. $O(N^3)$보다 빠르게 풀 때는 $D(i,j)$의 값을 $D(i+1,k)$로 뿌려주는 방식이 아닌, $D(i, k)$의 값을 계산할 때 $D(i-1, j)$의 값을 가져오는 방식으로 구현하는 것이 편합니다.
각 $k$마다 위에서 다룬 8가지 경우를 이루는 $j$들이 구간을 이룬다는 것은 직관적으로 유추할 수 있습니다. 사실 증명은 못 했고, $N \leq 16$인 모든 데이터에서 assert를 이용해 구간을 이룬다는 것을 확인했습니다. 앞으로 언급하는 구간에 대한 모든 내용은 이런 방식으로 증명(?)했음을 미리 밝힙니다. 아무튼 각 경우마다 고려해야 하는 $j$들이 구간을 이룬다고 믿고, 세그먼트 트리를 이용해 점화식을 계산하면 $O(N^2 \log N)$ 시간에 문제를 해결해 180점을 받을 수 있습니다.
하지만 8가지 경우를 모두 고려하는 것은 귀찮고 세그먼트 트리를 8개씩 들고 다니는 것도 힘들기 때문에 저는 다음과 같이 케이스를 5가지로 줄였고, 이렇게 해도 각 경우에서 고려하는 $j$가 구간을 이룬다는 것을 확인했습니다.
$j+2t < k \leq N$. 즉, $1 \leq j < k-2t$
    
$D(i,k) \leftarrow D(i-1,j) + E_k - S_k + 1$
$j+t < k \leq 2+2t$. 즉, $k-2t \leq j < k-t$
    
2번 칸이 교집합에 정확히 1개 존재하는 경우. 즉, $R_j = L_k$
        
$D(i, k) \leftarrow D(i-1, j) + E_k - E_j$
그렇지 않은 경우. 즉, $R_j \neq L_k$
        
$D(i,k) \leftarrow D(i-1,j) + E(k) - \max(S_k, E_j+1) + 1$
$j < k \leq j+t$. 즉, $k-t \leq j < k$
    
$j$와 $k$ 사이에 2개 이상의 2번 칸이 존재하는 경우. 즉, $R_j < L_k$
        
$D(i,k) \leftarrow D(i-1,j) + E_k - S_k + 1$
그렇지 않은 경우. 즉, $R_j \geq L_k$
        
$D(i,k) \leftarrow D(i-1,j) + E_k - E_j$
여기까지 오면 연산의 종류가 2가지밖에 없다는 사실을 알 수 있습니다. 세그먼트 트리를 사용하는 $O(N^2 \log N)$ 풀이를 $O(N^2)$으로 줄이기 위해서는 세그먼트 트리 대신 슬라이딩 윈도우로 RMQ를 처리하거나, 아니면 기상천외한 아이디어를 이용해 새로운 풀이를 만들어 내는 방법밖에 없습니다. 후자였다면 30명 이상 풀었을 리가 없기 때문에 제 감을 믿고 전자의 방식으로 접근하기 시작했습니다.
위에서 나눈 5가지 경우를 이용해 $k$마다 각 $j$가 두 가지 연산 방식 중 어떤 것으로 $D(i, k)$에 반영되는지 표시했더니 놀랍게도 두 연산을 수행하는 구간이 나뉘어 있다는 것을 확인했고, 심지어 구간의 시작점과 끝점에 단조성이 있음을 함께 확인했습니다. 따라서 세그먼트 트리 대신 덱을 이용해서 RMQ를 처리할 수 있고, 시간 복잡도는 $O(N^2)$이 되어서 300점을 받을 수 있습니다.
int N, M, T, A[5050], L[5050], R[5050], D[5050][5050];
inline int GetL(int x){ return max(L[x]+1, x-T); }
inline int GetR(int x){ return min(R[x]-1, x+T); }
inline int Only(int x){ return GetR(x) - GetL(x) + 1; }
int Type[5050][5050];
vector<tuple<int,int,int>> Interval[5050];
void Init(){
    fill(L+1, L+N+1, 0);
    fill(R+1, R+N+1, N+1);
    for(int i=1; i<=N; i++) for(int j=i-1; j>=max(1,i-T); j--) if(A[j] == 2) { L[i] = j; break; }
    for(int i=1; i<=N; i++) for(int j=i+1; j<=min(N,i+T); j++) if(A[j] == 2) { R[i] = j; break; }
    for(int k=1; k<=N; k++){
        for(int j=1; j<k; j++){
            if(1 <= j && j < k - 2 * T) Type[k][j] = 1;
            else if(k - 2 * T <= j && j < k - T){
                if(R[j] == L[k]) Type[k][j] = 2;
                else if(GetL(k) > GetR(j) + 1) Type[k][j] = 1;
                else Type[k][j] = 2;
            }
            else{
                if(R[j] < L[k]) Type[k][j] = 1;
                else Type[k][j] = 2;
            }
        }
        Interval[k].clear();
        for(int i=1, j=1; i<k; i=j){
            while(j < k && Type[k][i] == Type[k][j]) j += 1;
            Interval[k].emplace_back(Type[k][i] - 1, i, j-1);
        }
    }
}
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    cin >> M >> T;
    Init();
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) D[i][j] = 0xc0c0c0c0;
    for(int i=1; i<=N; i++) D[1][i] = Only(i);
    for(int i=2; i<=M; i++){
        // type 0: D[i-1][j] + GetR(k) - GetL(k) + 1
        // type 1: D[i-1][j] - GetR(j) + GetR(k)
        deque<pair<int,int>> Q[2];
        auto f = [&](int type, int v){ return D[i-1][v] - (type ? GetR(v) : 0); };
        auto g = [&](int type, int k){ return Q[type].front().first + (type ? GetR(k) : Only(k)); };
        int lst[2] = {1, 1};
        for(int k=1; k<=N; k++){
            for(auto [type,l,r] : Interval[k]){
                while(!Q[type].empty() && Q[type].front().second < l) Q[type].pop_front();
                for(; lst[type]<=r; lst[type]++){
                    int v = lst[type];
                    while(!Q[type].empty() && Q[type].back().first <= f(type, v)) Q[type].pop_back();
                    Q[type].emplace_back(f(type, v), v);
                }
                D[i][k] = max(D[i][k], g(type, k));
            }
        }
    }
    cout << *max_element(D[M]+1, D[M]+N+1) << "\n";
}
막대기 연결
2차원 좌표 평면에 $N$개의 점 $(X_i,Y_i)$가 주어진다. 쿼리로 $l,r$이 주어지면 $l \leq a < b \leq r$를 만족하는 $(X_b-X_a) \times (Y_a+Y_b)$의 최솟값을 구하는 문제
$N,Q \leq 10^5;$ $1 \leq X_i,Y_i \leq 10^9;$ $X_{i-1} < X_i$
전혀 모르겠어서 풀 태스크 바로 아래 단계인 $N,Q \leq 3\,000$인 부분 문제를 풀었습니다. DP와 비슷한 느낌으로 $O(N^2)$ 시간에 모든 쿼리에 대한 답을 전처리하면, 각 쿼리에 대한 답을 상수 시간에 구할 수 있습니다. 자세한 방법은 글로 설명하는 것보다는 코드를 보는 것이 좋을 것 같습니다.
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> X[i] >> H[i];
    cin >> Q;
    for(int i=1; i<=Q; i++) cin >> L[i] >> R[i];
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++) D[i][j] = (X[j] - X[i]) * (H[i] + H[j]);
    for(int d=2; d<=N; d++){
        for(int i=1, j=d+1; j<=N; i++, j++){
            D[i][j] = min({D[i][j], D[i+1][j], D[i][j-1]});
        }
    }
    for(int i=1; i<=Q; i++) cout << D[L[i]][R[i]] << "\n";
}
스마트 아파트 건설
간선으로 연결된 두 정점의 가중치 합이 $K$ 이하가 되도록 정점에 $1$부터 $N$까지의 가중치를 정확히 한 번씩 배정하는 문제
$T \leq 610;$ $N \leq 20$
이 문제도 전혀 모르겠어서 풀 태스크 바로 아래 단계인 $N \leq 8$인 부분 문제를 풀었습니다. $O(N^2 \times N!)$ 시간에 브루트포스를 하면 됩니다.
void Solve(){
    cin >> N >> K >> M; R = 0;
    vector<pair<int,int>> E(M);
    for(auto &[u,v] : E) cin >> u >> v, u--, v--;
    vector<int> O(N); iota(O.begin(), O.end(), 1);
    do{
        bool flag = true;
        for(auto [u,v] : E) if(O[u] + O[v] > K){ flag = false; break; }
        R += flag;
    }while(next_permutation(O.begin(), O.end()));
    cout << R << "\n";
}

2023 SCPC 2차예선 풀이

댓글