본문 바로가기

대회/Atcoder

ARC 121 후기 및 풀이

이번 앳코더 ARC에서 6문제를 다 풀어 전체 5등, Rated 중 1등을 하였습니다. 간단한 후기와 문제 풀이를 해볼까 합니다.

A. 2nd Greatest Distance

구현과 케이스처리가 매우 복잡한, 400점짜리 문제 치고는 어려운 문제입니다. 다만 아래와 같은 관찰을 통해 구현을 편리하게 줄일 수 있습니다.

 

각 정점을 x좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점과,

y좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점만이 필요하다.

 

만약 2번째로 긴 체비셰프 거리가 위 정점들로 이루어지지 않는다면, 두 양끝점 중 하나를 위에서 뽑아낸 (최대 8개의) 점들로 대체했을 때 더 긴 해를 얻을 수 있음이 보장되기 때문입니다. 따라서 위와 같이 8개의 점의 후보를 얻어내고, 나이브하게 2번째로 긴 거리를 찾아 출력하면 됩니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
struct dat{
    int x, y, idx;
    dat(){}
    dat(int x, int y, int idx): x(x), y(y), idx(idx){}
};
 
int n;
dat arr[200002];
dat arr2[200002];
bool chk[200002];
 
vector<int> vec;
vector<int> dvec;
 
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].x, &arr[i].y);
        arr[i].idx = i;
    }
 
    for(int i=1; i<=n; i++) arr2[i] = arr[i];
    sort(arr2+1, arr2+n+1, [&](dat &a, dat &b){
        return a.x<b.x;
    });
    for(int i=1; i<=2; i++) chk[arr2[i].idx] = 1, chk[arr2[n+1-i].idx] = 1;
 
    for(int i=1; i<=n; i++){
        arr2[i] = arr[i];
    }
    sort(arr2+1, arr2+n+1, [&](dat &a, dat &b){
        return a.y<b.y;
    });
    for(int i=1; i<=2; i++) chk[arr2[i].idx] = 1, chk[arr2[n+1-i].idx] = 1;
 
    for(int i=1; i<=n; i++){
        if(chk[i]) vec.push_back(i);
    }
    for(int i=0; i<(int)vec.size(); i++){
        for(int j=i+1; j<(int)vec.size(); j++){
            dvec.push_back(max(abs(arr[vec[i]].x - arr[vec[j]].x), abs(arr[vec[i]].y - arr[vec[j]].y)));
        }
    }
    sort(dvec.rbegin(), dvec.rend());
    printf("%d", dvec[1]);
}

 

B. RGB Matching

빨간 강아지의 수를 $r$, 초록 강아지의 수를 $g$, 파란 강아지의 수를 $b$로 두면, 이 셋의 홀짝성에 따라 일반성을 잃지 않고 케이스를 두 가지로 나눌 수 있습니다.

 

  • $r$, $g$, $b$가 모두 짝수인 경우
    • 같은 색의 강아지끼리만 항상 매칭을 시켜줄 수 있고, 이때의 답이 0입니다. 따라서 최적해는 항상 0입니다.
  • $r$은 짝수, $g$와 $b$가 홀수인 경우
    • 아래와 같은 두 가지 해 중 하나가 최적해임이 보장됩니다. (다른 방법이 존재한다면, 항상 답이 더 작거나 같은 해를 찾아줄 수 있습니다.)
    • Case 1) 초록색(G) 강아지와 파란색(B) 강아지 한 마리씩을 잇고(G-B), 나머지는 같은 색 강아지끼리 잇는다.
    • Case 2) 빨간색 강아지 두 마리(RR)를 각각 초록색(G), 파란색(B) 강아지 한 마리와 잇고(R-G, R-B), 나머지를 같은 색 강아지끼리 잇는다.
    • Case 1의 경우 초록색과 파란색 강아지의 $a_i$를 모두 정렬해 두고, 가장 가까운 두 수를 찾아주면 되는데 이는 이분 탐색이나 투 포인터를 이용하면 풀 수 있습니다.
    • Case 2의 경우 모든 초록색 / 파란색 강아지 각각에 대해 가장 $a_i$가 가까운 빨간색 강아지까지의 $a_i$의 차이를 구한 뒤, 이 둘을 더하면 됩니다. 이 두 강아지가 겹치는 경우에는 어떻게 하냐고 생각하실 수 있는데, 이 경우 아래와 같은 두 가지 경우가 있습니다. 둘 모두 초록색 강아지와 파란색 강아지를 직접 이어주는 더 작거나 같은 해가 존재하기 때문에 상관없습니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int n;
vector<ll> R, G, B;
ll ans = LLONG_MAX;
 
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n*2; i++){
        ll x; char c;
        scanf("%lld %c", &x, &c);
        if(c=='R') R.push_back(x);
        if(c=='G') G.push_back(x);
        if(c=='B') B.push_back(x);
    }
 
    if(R.size() % 2 == 0 && G.size() % 2 == 0 && B.size() % 2 == 0){
        printf("0\n");
        return 0;
    }
    if(G.size() % 2 == 0) R.swap(G);
    if(B.size() % 2 == 0) R.swap(B);
 
    sort(R.begin(), R.end());
    sort(G.begin(), G.end());
    sort(B.begin(), B.end());
 
    for(auto x: G){
        auto it = lower_bound(B.begin(), B.end(), x);
        if(it != B.end()) ans = min(ans, *it - x);
        if(it != B.begin()) ans = min(ans, x - *prev(it));
    }
 
    ll gMin = 1e18, bMin = 1e18;
    for(auto x: G){
        auto it = lower_bound(R.begin(), R.end(), x);
        if(it != R.end()) gMin = min(gMin, *it - x);
        if(it != R.begin()) gMin = min(gMin, x - *prev(it));
    }
    for(auto x: B){
        auto it = lower_bound(R.begin(), R.end(), x);
        if(it != R.end()) bMin = min(bMin, *it - x);
        if(it != R.begin()) bMin = min(bMin, x - *prev(it));
    }
 
    ans = min(ans, gMin + bMin);
    printf("%lld", ans);
}

 

C. Odd Even Sort

정렬에서 swap할 수 있는 횟수가 매우 널널하기 때문에 별 생각 없이 구현해도 정답이 나옵니다. 저와 같은 경우는 아직 제자리에 있지 않은 가장 작은 수 $x$를 찾은 뒤, $x$와 그 왼쪽 수를 지금 교환할 수 있으면 교환하고, 아니라면 교환할 수 있는 쌍 중에서 교환하기 가장 적합한 것을 교환했습니다. 만약 $a_{i} > a_{i+1}$이고 현재 교환할 수 있는 $(i, i+1)$ 쌍이 있다면 교환하고, 아니라면 교환할 수 있는 최대한 오른쪽에 있는 쌍을 교환합니다. 자세한 풀이는 코드를 참조하시기 바랍니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int t;
int n;
int arr[502];
 
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%d", &arr[i]);
        }
 
        vector<int> ans;
        int odd = 1;
        while(1){
            int tmp = -1;
            for(int i=1; i<=n; i++){
                if(arr[i] != i){
                    tmp = i;
                    break;
                }
            }
            if(tmp == -1) break;
 
            for(int i=1; i<=n; i++){
                if(arr[i] == tmp){
                    tmp = i;
                    break;
                }
            }
            if((tmp-1 + odd) % 2 == 0){
                ans.push_back(tmp-1);
                swap(arr[tmp-1], arr[tmp]);
            }
            else{
                bool swapped = 0;
                for(int i=n-1; i>=1; i--){
                    if(arr[i] > arr[i+1] && (i+odd) % 2 == 0){
                        swapped = 1;
                        ans.push_back(i);
                        swap(arr[i], arr[i+1]);
                        break;
                    }
                }
                if(!swapped){
                    if((n-1 + odd) % 2 == 0){
                        ans.push_back(n-1);
                        swap(arr[n-1], arr[n]);
                    }
                    else{
                        ans.push_back(n-2);
                        swap(arr[n-2], arr[n-1]);
                    }
                }
            }
            odd = !odd;
        }
 
        printf("%d\n", (int)ans.size());
        for(auto x: ans) printf("%d ", x);
        puts("");
    }
}

 

D. 1 or 2

풀이가 틀렸는데 데이터가 약해서 맞은 것 같습니다. 정해는 아래와 같은 관찰이 필요합니다.

  • 사탕 하나를 혼자 먹는 것은 맛이 0인 사탕과 함께 먹는 것과 정확히 동치이다.

따라서 사전에 맛이 0인 사탕 몇 개를 추가해 준 뒤, 매 순간별로 가장 맛이 좋은 사탕과 나쁜 사탕을 먹는 것을 반복해 주면 $O(N^2)$ 풀이가 완성됩니다.

 

최적해는 아래와 같은 종류라는 것을 관찰할 수 있습니다.

  • Step 1. 혼자 먹을 사탕의 집합을 위에서부터 $x$개 고르거나, 아래에서부터 $x$개 고른다. ($0 \le x \le N$)
  • Step 2. 아래의 작업을 $c$번 시행한다. (단, $0 \le 2c \le N-x$)
    • 남아 있는 가장 맛이 좋은 / 나쁜 사탕을 확인한 뒤, 그 둘을 한 번에 먹는다.
  • Step 3. 남은 사탕은 모두 따로 먹는다.

Step 1로 가능한 $O(N)$ 가지 경우를 모두 시험해 보며, 남은 사탕들에 Step 2를 한 번씩 적용해 가며 지금 현재 Step 3으로 넘어갔을 때 나오는 해들 중 최적해를 모두 구해 주면 $O(N^2)$에 문제를 풀 수 있습니다. 역시 구현이 간단하니 코드를 참고하시기 바랍니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int n;
ll arr[5002];
ll ans = LLONG_MAX;
 
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
    }
 
    sort(arr+1, arr+n+1);
 
    for(int i=n; i>=1; i--){
        ll tMax = LLONG_MIN, tMin = LLONG_MAX;
        for(int j=i+1; j<=n; j++){
            tMax = max(tMax, arr[j]);
            tMin = min(tMin, arr[j]);
        }
        for(int a=1, b=i; a<=b; a++, b--){
            ans = min(ans, max(tMax, arr[b]) - min(tMin, arr[a]));
            ll weight = a==b ? arr[a] : arr[a] + arr[b];
            tMax = max(tMax, weight);
            tMin = min(tMin, weight);
        }
        ans = min(ans, tMax - tMin);
    }
 
    for(int i=1; i<=n; i++){
        ll tMax = LLONG_MIN, tMin = LLONG_MAX;
        for(int j=1; j<i; j++){
            tMax = max(tMax, arr[j]);
            tMin = min(tMin, arr[j]);
        }
        for(int a=i, b=n; a<=b; a++, b--){
            ans = min(ans, max(tMax, arr[b]) - min(tMin, arr[a]));
            ll weight = a==b ? arr[a] : arr[a] + arr[b];
            tMax = max(tMax, weight);
            tMin = min(tMin, weight);
        }
        ans = min(ans, tMax - tMin);
    }
 
    printf("%lld", ans);
}

 

E. Directed Tree

$DP[i][j]$: $i$번 정점을 루트로 가지는 서브트리의 정점 중 $j$개에서 자신의 자식을 고를 때, 겹치지 않게 고르는 방법의 수로 정의합시다. 이때 크기가 $A$와 $B$인 두 서브트리의 결과를 $O(AB)$에 합칠 수 있으므로, DP 배열을 $O(N^2)$에 얻어낼 수 있습니다. (KOI 2019 검은 돌 참고)

 

포함과 배제의 원리를 이용하면 답은 $\sum_{i=0}^{n} (-1)^i (n-i)! \times DP[0][i]$로 구할 수 있습니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const ll MOD = 998244353;
 
ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y&1) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}
 
int n;
int par[2002];
vector<int> link[2002];
 
ll fact[2002], factInv[2002];
ll DP[2002][2002];
ll tmpDP[2002];
int sz[2002];
ll ans;
 
void dfs(int x, int par = -1){
    DP[x][0] = 1;
    for(auto y: link[x]){
        dfs(y, x);
        int xL = sz[x], yL = sz[y];
        for(int i=0; i<=xL+yL; i++){
            tmpDP[i] = 0;
        }
 
        for(int i=0; i<=xL; i++){
            for(int j=0; j<=yL; j++){
                tmpDP[i+j] = (tmpDP[i+j] + DP[x][i] * DP[y][j]) % MOD;
            }
        }
        for(int i=0; i<=xL+yL; i++){
            DP[x][i] = tmpDP[i];
        }
        sz[x] += sz[y];
    }
 
    for(int i=sz[x]; i>=0; i--){
        DP[x][i+1] += DP[x][i] * (sz[x] - i) % MOD;
        DP[x][i+1] %= MOD;
    }
    sz[x]++;
}
 
int main(){
    fact[0] = 1;
    for(int i=1; i<=2000; i++) fact[i] = fact[i-1] * i % MOD;
    factInv[2000] = mpow(fact[2000], MOD-2);
    for(int i=1999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;
 
    scanf("%d", &n);
    for(int i=2; i<=n; i++){
        scanf("%d", &par[i]);
        link[par[i]].push_back(i);
    }
 
    dfs(1);
 
    int sign = 1;
    for(int i=0; i<=n; i++){
        ans += DP[1][i] * fact[n-i] % MOD * sign;
        ans = (ans + MOD) % MOD;
        sign *= -1;
    }
    printf("%lld", ans);
}

 

F. Logical Operations on Tree

모든 정점과 간선에 0/1이나 OR/AND를 쓴 상태이고, 여기서 1을 만들 수 있는 지 생각해 봅시다. AND가 쓰여 있는 간선의 경우 양쪽 모두 1이어야 1이 되므로, 1을 만들기가 쉽지 않습니다. 따라서 1을 만들 여지를 남겨 두기 위해서는 먼저 AND가 쓰여 있는 간선부터 모두 합쳐준 후 OR 간선을 합쳐 주는 것이 이득일 것입니다. 

 

어떤 배치에서 "1을 만들 수 있다"의 반대는 "0밖에 만들 수 없다"입니다. 0밖에 만들 수 없는 배치는 모든 AND 게이트로 연결된 컴포넌트에 0이 적어도 하나 쓰여 있는 경우입니다.

 

아래와 같이 DP 식을 정의합시다.

 

$DP[i][0]$: 현재 $i$번 노드가 연결된 컴포넌트에 0이 하나도 쓰여 있지 않은 경우

$DP[i][1]$: 현재 $i$번 노드가 연결된 컴포넌트에 0이 하나라도 쓰여 있는 경우

 

$DP[i][0]$을 구하기 위해서는 $i$번 노드와 자식 노드 $c$가 무슨 게이트로 연결되어 있는지를 살펴봐야 합니다. 일단 $i$번 노드에는 무조건 1이 쓰여 있어야 하고, $i$번 노드와 AND 게이트로 연결된 노드의 경우 $DP[c][0]$을 (0이 쓰여 있지 않아야 하므로), OR 게이트로 연결된 노드의 경우 $DP[c][1]$을 (정점 $c$가 속한 연결 성분에는 0이 적어도 하나 있어야 하므로) 취해야 합니다. 따라서 $DP[i][0]$은 모든 자식 노드 $c$에 대해 $DP[c][0] + DP[c][1]$의 곱입니다.

 

$DP[i][1]$을 구하기 위해서는 $i$번 정점에 0이 쓰인 경우와 1이 쓰인 경우로 나눌 수 있습니다. 0이 쓰인 경우는 $i$번 정점과 $c$번 정점을 올바르게 연결만 하면 되는데, 이 둘이 AND 게이트로 연결된 경우 $DP[c][0] + DP[c][1]$가지 경우의 수가, OR 게이트로 연결된 경우 $DP[c][1]$가지 경우의 수가 존재하게 됩니다.

 

만약 $i$번 정점에 1이 쓰여 있다면 AND 게이트로 연결된 자식 노드 중 적어도 하나의 컴포넌트에 0이 쓰여 있어야 하는데, 이는 바로 윗 문단에서 구한 경우의 수에서 $DP[i][0]$을 빼서 구할 수 있습니다.

 

답은 $2^{2N-1} - DP[1][1]$이 됩니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const ll MOD = 998244353;
 
ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y%2) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}
 
int n;
vector<int> link[100002];
ll DP[100002][2];
 
void dfs(int x, int par = -1){
    DP[x][0] = 1;
    ll case1_0 = 1, case1_1 = 1;
    for(auto y: link[x]){
        if(y == par) continue;
        dfs(y, x);
 
        DP[x][0] *= (DP[y][0] /* AND 할 경우 안 만들어진 것*/ + DP[y][1] /* OR 할 경우 만들어진 것 */) % MOD;
        DP[x][0] %= MOD;
 
        case1_1 *= (DP[y][0] + DP[y][1] + DP[y][1]) % MOD;
        case1_1 %= MOD;
 
        case1_0 *= (DP[y][0] + DP[y][1] + DP[y][1]) % MOD;
        case1_0 %= MOD;
    }
    case1_0 = (case1_0 - DP[x][0] + MOD) % MOD;
    DP[x][1] = (case1_0 + case1_1) % MOD;
}
 
int main(){
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }
 
    dfs(1);
    ll ans = (mpow(2, 2*n-1) + MOD - DP[1][1]) % MOD;
    printf("%lld", ans);
}

'대회 > Atcoder' 카테고리의 다른 글

ARC 121 후기 및 풀이  (0) 2021.05.29