Codeforces Round 1051 (Div.2)

3솔을 빠르게 밀었고, 1시간 차에 D1을 해결.

D2를 30분, E를 30분 고민했는데 둘 다 애매해져서 5솔브를 못 하고 끝났다.

문제는 전반적으로 마음에 든다.

 

A. All Lengths Subtraction

$k=1,2,\ldots,n$에 대해 원하는 길이 $k$의 subarray를 잡아서 $1$을 빼주는 시행을 한 번씩 한다.

주어진 배열의 모든 원소를 $0$으로 만들 수 있는가?

 

풀이

$k$의 순서를 거꾸로 보면 좋다.

이미 $0$이 되어버린 부분들은 배열에서 제거한다고 했을 때, 왼쪽끝 또는 오른쪽 끝에 반드시 $1$이 존재하고, 그 $1$을 끝으로 포함하게 subarray를 잡아야만 한다.

 

따라서 양끝에서 $\ell$과 $r$을 좁히면서 확인하면 된다.

void solution(size_t tc) {
    ll n; cin >> n;
    ll a[n+1]; rep(i,1,n) cin >> a[i];
    
    ll l = 1, r = n, k = 1;
    
    for (ll k = 1; l <= r; k++) {
        if (a[l] == k) l++;
        else if(a[r] == k) r--;
        else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

B. Discounts

$n$개의 상품 가격 $a_1,a_2,\ldots, a_n$과, 할인 묶음 단위 $b_1, b_2, \ldots, b_k$가 주어진다.

할인 쿠폰 $i$의 사용법: $b_i$개의 상품을 골라, 그중 가장 싼 상품의 가격만큼을 안 내도 된다.

하나의 쿠폰은 최대 한 번만, 하나의 상품은 최대 하나의 할인 묶음 대상으로만 사용될 수 있다.

 

모든 물건을 구매하기 위한 최소 금액은?

 

풀이

금액이 큰 상품들부터 정렬하여, 작은 묶음 단위들로 타이트하게 묶어나가게 할인시키는 것이 최적이다.

간단하게 논증해보자면: 덜어낸 금액들을 모아봤을 때, 어떤 금액도 늘릴 수 없고, 더 많은 상품을 덜어낼 수도 없다. 당연히 최적.

 

그냥 구현하면 된다.

void solution(size_t tc) {
    ll n, k;
    cin >> n >> k;
    
    ll a[n+1]{};
    ll b[k+1]{};
    
    rep(i,1,n) cin >> a[i];
    rep(i,1,k) cin >> b[i];
    sort(a+1, a+n+1, greater<>());
    sort(b+1, b+k+1);
    
    ll ans = accumulate(a+1, a+n+1, 0ll);
    
    ll sum = 0;
    rep(i,1,k) {
        sum += b[i];
        if (sum <= n)
            ans -= a[sum];
    }
    
    cout << ans << '\n';
}

C. Max Tree

트리가 주어진다. 각 정점에는 가중치가 있다. 가중치 외에, 당신은 각 정점에 $1,2,\ldots,n$의 값을 배정할 것이다.

간선이 잇는 두 정점중 배정된 값이 더 큰 방향의 가중치를 간선의 가중치라고 하자. 가중치 총합을 최대화 하는 방법을 찾아라.

 

풀이

트리의 모든 간선에 방향성을 원하는대로 부여한다고 생각해도 무리가 없다. (사이클이 없기 때문에)

가중치가 큰쪽을 향하게 방향을 설정하고, 위상정렬을 한 뒤, order를 그대로 정점의 값으로 배정해주면 된다.

 

그냥 구현하면 된다.

void solution(size_t tc) {
    ll n;
    cin >> n;
    
    vi adj[n+1]{};
    ll deg[n+1]{};
    
    rep(i,2,n) {
        ll u, v, x, y;
        cin >> u >> v >> x >> y;
        if (x > y) adj[v].pb(u), deg[u]++;
        else adj[u].pb(v), deg[v]++;
    }
    
    queue<ll> Q;
    rep(i,1,n) if (deg[i] == 0) Q.push(i);
    
    ll p[n+1]{}, c = 0;
    
    while (!empty(Q)) {
        ll s = Q.front(); Q.pop();
        p[s] = ++c;
        for(auto u:adj[s]) if(--deg[u]==0) Q.push(u);
    }
    
    rep(i,1,n) cout << p[i] << ' ';
    cout << '\n';
}

D1. Inversion Graph Coloring (Easy)

수열로 inversion 쌍들을 간선으로 이어 만든 그래프가 2가지 색으로 채색될 수 있으면, 좋은 수열이라고 한다.

주어진 배열의 좋은 부분 수열의 개수를 구하라. ($n\leq 300$)

 

풀이

우선 Longest decreasing subsequence의 길이가 2 이하여야 한다는 말과 동치임을 이해하자.

 

$\mathrm{dp}(i,hi_1, hi_2):=1,2,\ldots, i$까지 구성했을 때, 가장 큰 값이 $hi_1$이고, 구성한 수열 내부에서 decreasing subsequence의 두 번째 원소가 될 수 있는 값들 중 가장 큰 값을 $hi_2$라고 하자.

 

매 인덱스마다, $a_{i+1}$를 subsequence에 추가하지 않는다면, $\mathrm{dp}(i,\cdot,\cdot)$의 값을 그대로 가져가면 된다.

추가한다면, $a_{i+1}$이 $hi_2$가 되는 경우, $a_{i+1}$이 $hi_1$이 되는 경우로 나눠서 전이를 시켜주면 된다.

 

void solution(size_t tc) {
    ll n; cin >> n;
    ll a[n+1]; rep(i,1,n) cin >> a[i];
    
    mi dp[n+1][n+1][n+1]{};
    dp[0][0][0] = 1;
    
    rep(i,0,n-1) rep(hi1,0,n) rep(hi2,0,n) {
        
        // case 1. use a[i+1]
        if(hi2 <= a[i+1]) {
            if(hi1 > a[i+1])
                dp[i+1][hi1][a[i+1]] += dp[i][hi1][hi2];
            else
                dp[i+1][a[i+1]][hi2] += dp[i][hi1][hi2];
        }
        
        // case 2. not use a[i+1]
        dp[i+1][hi1][hi2] += dp[i][hi1][hi2];
    }
    
    mi ans;
    rep(hi1,0,n) rep(hi2,0,n) {
        ans += dp[n][hi1][hi2];
    }
    
    cout << ans << '\n';
}

D2. Inversion Graph Coloring (Hard)

$n\leq 2\,000$으로 제한이 올랐다.

 

풀이

2차원 DP로 줄이고 뭔가 블록블록을 잘 설계하려고 노력했는데, 그런 방향이 아니었다..

 

DP식이 뿌려주기 형식이다 보니까 점화식을 간결하게 정리 못 할 거라고 생각하고 시도를 안 했는데, 범위를 잘 확인하면 생각보다 점화식이 간결하게 정리된다. 아쉽다.

 

정리된 점화식을 2차원에 놓고 확인하면 최적화 각을 바로 찾을 수 있다.

 

기존의 점화식은 세 가지 케이스였다.

1. $dp[i+1][h_1][a_{i+1}] += dp[i][h_1][h_2]$
   • $h_1 \in [a_{i+1}+1, n]$
   • $h_2 \in [0, a_{i+1}]$
2. $dp[i+1][a_{i+1}][h_2] += dp[i][h_1][h_2]$
   • $h_1 in [0, a_{i+1}]$
   • $h_2 in [0, a_{i+1}]$
3. $dp[i+1][h_1][h_2] += dp[i][h_1][h_2]$

전이 1과 전이 2의 모식

 

단순히 row와 col의 합을 관리하는 세그트리 $N$개씩을 만들어서 매 전이를 $O(N\log N)$에 처리하면 된다.

 

근본적으로 이런 최적화가 가능했던 이유는, 점화식의 $h_1$, $h_2$ 항 중 하나는 $a_{i+1}$로 고정되어 있어, $O(N)$개의 점만이 점화식에서 실질적인 업데이트를 가져갔기 때문이다.

 

void solution(size_t tc) {
    ll n; cin >> n;
    ll a[n+1]{}; rep(i,1,n) cin >> a[i];
    
    static fenwick_tree<N> row[N]{}, col[N]{};
    rep(i,0,n) row[i].set(n+1), col[i].set(n+1);
    
    row[0].add(0, 1);
    col[0].add(0, 1);
    
    rep(i,0,n-1) {
        mi R[n+1];
        mi C[n+1];
        
        rep(j,0,n) R[j] = row[j].sum(0, a[i+1]);
        rep(j,0,n) C[j] = col[j].sum(0, a[i+1]);
        
        rep(j,0,n) {
            if(j>a[i+1]) {
                col[a[i+1]].add(j, R[j]);
                row[j].add(a[i+1], R[j]);
            }
            
            if(j<a[i+1]) {
                row[a[i+1]].add(j, C[j]);
                col[j].add(a[i+1], C[j]);
            }
        }
    }
    
    mi ans;
    rep(i,0,n) {
        ans += row[i].sum(0, n);
    }
    
    cout << ans << '\n';
}

E. Make Good

"$(($"를 잡아 "$))$"로 변경하거나, "$))$"를 잡아 "$(($"로 변경하는 시행을 원하는 만큼 할 수 있다고 할 때, 주어진 괄호 문자열을 올바른 괄호 문자열로 만들어보자. 불가능하다면 $-1$을 출력하자.

 

풀이

$n$이 홀수라면 불가능하다.

일단 괄호는 보기 불편하므로 (,)를 0,1로 대응시켜서 표현하겠다.

 

$1010$은 불가능하다.

$101011\to 1010\color{red}{00} \to 101\color{red}{11}0 \to 10\color{red}{00}10 \to 1\color{red}{11}010 \to \color{red}{00}1010$ 이런 식으로 변환이 가능하겠다.

 

손으로 해보며 몇 가지 불변량을 관찰해보면, 우선 $0$개수 기우성과 $1$개수 기우성의 불변함을 알 수 있다.

따라서 $0$개수 기우성과 $1$개수 기우성이 모두 정확히 $n/2$와 같은 기우성을 갖지 않는다면, 불가능 판정을 내릴 수 있다.

 

$0101\ldots 01$ 꼴과 $1010\ldots 10$ 꼴은 어떤 시행도 먹일 수 없다. 둘을 제외한 모든 경우에는 적어도 하나의 $00$ 또는 $11$이 존재하여, 배열 전반을 $0$으로 밀거나 $1$로 미는 것이 가능하다. 일단 이 직관을 기억해두자.

 

불변량이 또 있다.

인접한 두 원소를 잡아 뒤집는 수많은 시행에서, (짝수 인덱스에서의 $x$ 개수) + (홀수 인덱스에서의 $x$ 개수)는 불변이다.

마찬가지로 이 문제에서도 그렇다.

 

$0$-인덱스 기준으로 설명하겠다.

일단, 일반성을 잃지 않고 $0$에 대한 속성들 위주로만 다루겠다.

$c_0 :=$ 짝수 인덱스에서 $0$의 개수, $c_1 :=$ 홀수 인덱스에서 $0$의 개수 라고 정의하자.

 

$(c_0,c_1) \to (c_0+1, c_1+1)$ 또는 $(c_0,c_1) \to (c_0-1, c_1-1)$이 가능하다.

 

$c_0 + c_1$이 $n/2$가 아니라면, 일단 개수가 안 맞으니까, 시행 전반에서, 개수 합이 맞을 때까지 변화할 것이다.

이건 그냥 while문으로 직접 바꾸면 된다.

 

만약, $c_0$가 이 작업 이후에 $0$이라면, 여는 괄호가 단 하나도 존재할 수 없다는 의미가 된다. 따라서 이 때는 불가능 판정을 날린다.

 

그렇지 않다면, 홀수 인덱스와 짝수 인덱스를 잘 분배하여 올바른 괄호 문자열을 만들 수 있다. 어떤식으로?

좀 어렵다.

 

$( \color{red}{()()() \cdots ()} ) \color{blue}{()()() \cdots ()}$ 형태로 구성하면 된다.

• 빨간괄호부분문자열은, 모든 $0$의 인덱스가 홀수이다. 길이는 $2\times c_1$이다.
• 파란괄호부분문자열은, 모든 $0$의 인덱스가 짝수이다. 길이는 $2\times (c_0-1)$이다.

이게 되는 이유를 다시 살펴보자면, 일단 검은괄호쌍을 갖다 박는게 어렵다. 근데 그냥 누가봐도 될 것 같지 않나? 스킵하자.

나머지 색깔 괄호들은, 앞에서부터 하나씩 안 맞으면 바꾸는 식으로 자연스럽게 만들어진다.

 

대단한 문제였다...

반례 찾기가 굉장히 힘들었다.

void solution(size_t tc) {
    ll n; cin >> n;
    string s; cin >> s;
    
    if (n % 2) {
        cout << -1 << '\n';
        return;
    }
    if (count(all(s), '(') % 2 != n/2 % 2) {
        cout << -1 << '\n';
        return;
    }
    
    ll c[2]{};
    rep(i,0,n-1) if(s[i]=='(') c[i%2]++;
    
    while(c[0]+c[1] < n/2) c[0]++, c[1]++;
    while(c[0]+c[1] > n/2) c[0]--, c[1]--;
    
    if (c[0] == 0) { cout << -1 << '\n'; return; }
    
    cout << "("; c[0]--;
    rep(i,1,c[1]) cout << "()";
    cout << ")";
    rep(i,1,c[0]) cout << "()";
    cout << '\n';
}