Codeforces Round #627 (Div. 3) 후기 + 풀이

Div3지만 코포에서 라운드 시간 중에 올솔브 성공한건 처음인것 같다. :dhk:

---

A. Yet Another Tetris Problem

$2 \times 1$ 블록을 아무리 세워도 각 열의 홀짝성을 바꿀 수 없다. 반대로, 홀짝성이 같다면 높이 쌓는것에는 문제가 없으므로 엄청 높이 쌓으면 전부 지울 수 있다. 따라서, 홀수와 짝수 중 한종류만 있으면 YES, 아니면 NO.

---

B. Yet Another Palindrome Problem

길이가 3 이상인 Palindromic subsequence 가 있는지 확인하는 문제. Substring이 아닌 Subsequence이므로, 

- 어떤 수 $x$ 가 두번 이상 나오고,

- 그 수가 나오는 최소 위치와 최대 위치가 두칸 이상 떨어져 있다면 (즉, $xx$가 아닌 $xyx$ 형태) 

반드시 그 사이에 있는걸 이용해서 Palindromic Subsequence를 만들 수 있다. 반대로 그렇지 않다면 불가능.

---

C. Frog Jumps 

R에서 더 오른쪽에 있는 R로 갈 수 있어야 한다. 그렇지 않다면 전혀 진전이 없으므로...

따라서, 서로 인접한 R들 간의 거리 중 가장 먼 것을 뛰어넘을 수 있어야 함을 알 수 있다.

---

D. Pair of Topics

$a_i + a_j > b_i + b_j$ 인 Pair $i, j$ 개수 세는 문제. 

$a_i - b_i$ 를 모든 $i$에 대해 계산해 놓고 나면, 일반성을 잃지 않고, $i = 1$일 때, 2번부터 $n$번까지 중 몇개가 되는지 빠르게 알 수 있으면 충분하다. 미리 모든 $a-b$ 값을 넣어놓고, $a_j - b_j$ 가 $-(a_i - b_i)$ 보다 크기만 하면 되므로, 이 값은 upper bound 함수를 이용해서 (그리고 자기 자신을 빼야 한다는 예외 처리) 쉽게 구할 수 있다. 

성공하는 Pair를 2번씩 세었으므로 /2.

---

E. Sleeping Schedule

$n\times h$ DP 테이블을 만들고, 하루마다 가능한 모든 시간을 갱신하는 식으로 접근하면 쉽게 해결할 수 있다. 

$\texttt{dp[i][j]}$ 는 $i$일 째 $j$시간에 자는 경우에, 얻을 수 있는 지금까지 "Good sleep" 의 횟수로 정의한다. 그러면 $i-1$ 번째의 값 하나가 $i$번째의 값 두개 ($a_i, a_i-1$ 더하기) 에 영향을 미친다. 따라서, 총 $O(nh)$ 에 해결할 수 있다.

---

F. Maximum White Subtree

Tree 가 주어졌는데, 이때 어떤 subgraph를 따낼 수 있다. 각 정점에는 White 와 Black 중 색이 정해져 있고, Subgraph의 값은 그 Subgraph의 [흰색인 정점 개수] - [검은색인 정점 개수] 이다. 

각 정점별로 그 정점을 포함하는 subgraph의 값 중 최대인 것을 고르는 문제.

Subtree라고 해서 어떤 Rooted tree에서 쭉 내려가는걸 생각했는데 문제의 정의를 잘 읽어보면 그냥 Subgraph였다. 왜 정의를 이렇게 했는지는 잘 모르겠다...

 

기본적으로는 트리 DP 인데, 편의상 1번 정점을 루트로 잡고 "내려가는" 경우만 생각하자. 즉, 이 간선의 점수는 "이 간선을 타고 내려가는 경우, 얻을 수 있는 최대 Subgraph 값" 이다. 이 값은 DFS를 타고 내려간 다음, 다시 거꾸로 올라오면서 (DFS Stack에서 빠지는 순서대로) 갱신하면 갱신할 수 있다.

 

그 다음, 각 정점의 최대 값을 계산하기 위해서는 각 간선을 기준으로, 이 간선을 타고 "올라가서 도착하는 점" 의 값을 이용해서 갱신해야 한다. 코드로 보면 그렇게 어렵지 않은데 도저히 설명은 못하겠다 ㅋㅋ

 

대부분의 사람들이 DFS 두번에 뚝딱하던데 나는 뭔가 생각이 잘 안나서인지, DFS 한번에 BFS 한번으로 풀었다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define all(x) ((x).begin()),((x).end())
#define eps 1e-6
using pii = pair<int, int>;
int n;
vector <int> G[202020];
int color[202020];
int down_cnt[202020], out_total[202020], up_cnt[202020];
int par[202020];
queue <int> q;
bool vst[202020];
void dfs(int r, int p, int* cnt)
{
    par[r] = p;
    for (auto it:G[r])
        if (it!=p)
            dfs(it, r, cnt);
    if (cnt[r]>0)
        cnt[p]+=cnt[r];
}
int32_t main()
{
    usecppio
    cin >> n;
    memset(par, -1, sizeof(par));
    for (int i = 1; i<=n; i++)
    {
        cin >> color[i];
        color[i] = color[i]==1?1:-1;
        down_cnt[i] = color[i];
    }
    for (int i = 1; i<n; i++)
    {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0, down_cnt);
    q.push(1);
    vst[1] = true;
    for (auto it:G[1])
        out_total[1] += max(down_cnt[it], 0ll);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for (auto it:G[x])
        {
            if (!vst[it])
            {
                up_cnt[it] = out_total[x]+color[x];
                if (down_cnt[it]>0)
                    up_cnt[it] -= down_cnt[it];
                vst[it] = true;
                q.push(it);
                for (auto itt:G[it])
                    if (itt!=par[it])
                        out_total[it] += max(down_cnt[itt], 0ll);
                out_total[it] += max(up_cnt[it], 0ll);
            }
        }
    }
    for (int i = 1; i<=n; i++)
        printf("%lld ",out_total[i]+color[i]);
    printf("\n");
}

---

Div3 치고도 조금 쉬운 라운드였던것 같다.

그래도 트리DP에 익숙하지 않아서 한시간정도 걸렸는데, 오렌지 정도 되는 사람들 보니까 20~30분만에 뚝딱하는거 같다. DP 너무 어려워요... ㅇㅁㅇ