JOIOC 2018

https://contests.ioi-jp.org/open-2018/index.html

https://oj.uz/problems/source/351

역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.

4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.

Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다.

4. xylophone

순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번만의 쿼리로 순열을 복구해야 한다.

핵심 관찰은 다음과 같다. 만약 어떠한 세 수가 있고 (a, b, c) a~b, b~c, a~c 의 쿼리를 날렸다고 생각해 보자.

만약 a를 알고 있다면 두 가지 경우를 생각해 볼 수 있다. (a<b / a>b)

이를 통해 a-b, b-c 의 부호만 잘 알 수 있다면 a와의 차이를 통하여 a, b, c를 모두 구할 수 있다는 것을 알게 된다.

구체적으로 말하자면, a, a-b의 부호를 알고 있다고 가정하자. 일반성을 잃지 않고 위 그림과 같이 a<b라고 생각하면 a~c, b~c 의 쿼리값만 가지고 b-c의 부호를 판별할 수 있다.

만약 첫번째 그림과 같은 상황이면 a~c 의 값이 a~b + b~c 가 될 것이고, 두번째 상황이면 a~c의 값이 max(a~b, b~c) 값이 될 것이다.

결론적으로 a, a-b의 부호를 알고 있다면 b, c의 값을 모두 알수 있으며, 이를 아는 것은 b-c의 부호를 아는 것과 같기 때문에 이 과정을 쭉 반복해나갈 수 있다.

순열의 상대적 위치를 저장하기 위하여 A[0]=0 이라 생각하고, A[0]-A[1]이 양수, 음수의 두 경우로 나누어 2N개의 쿼리를 날린 후 계산하면 두 가지 경우의 순열을 복구해 낼 수 있다. 이 두 순열에 문제에서 주어진 조건인 최솟값의 위치 < 최댓값의 위치 를 적용하면 답이 하나로 확정된다.

시간 복잡도 : O(N)

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 5000;
 
int N, A[MAXN+10], Q1[MAXN+10], Q2[MAXN+10], D[MAXN+10], P1[MAXN+10], P2[MAXN+10];
 
void ans(int* P)
{
    int i, j;
    for(i=1; i<=N; i++)
    {
        answer(i, P[i]);
    }
}
 
void solve(int n)
{
    int i, j;
    N=n;
 
    for(i=1; i<N; i++) Q1[i]=query(i, i+1);
    for(i=1; i+1<N; i++) Q2[i]=query(i, i+2);
 
    D[1]=1;
    for(i=1; i+1<N; i++)
    {
        int a=Q1[i]+Q1[i+1];
        int b=max(Q1[i], Q1[i+1]);
 
        if(a==Q2[i]) D[i+1]=D[i];
        else D[i+1]=-D[i];
    }
 
    P1[1]=P2[1]=0;
    int min1=0, min2=0;
    for(i=2; i<=N; i++)
    {
        P1[i]=P1[i-1]+D[i-1]*Q1[i-1];
        P2[i]=P2[i-1]-D[i-1]*Q1[i-1];
        min1=min(min1, P1[i]);
        min2=min(min2, P2[i]);
    }
 
    for(i=1; i<=N; i++) P1[i]-=min1-1, P2[i]-=min2-1;
 
    int a, b;
    for(i=1; i<=N; i++)
    {
        if(P1[i]==1) a=i;
        if(P1[i]==N) b=i;
    }
    if(a<b) ans(P1);
    else ans(P2);
}

1. bubblesort 2

일단 문제를 단순화시켜서 바뀌는 쿼리가 없을 때, 즉 하나의 배열에 대하여 Pass 수를 어떻게 구할 수 있을까 생각해보자.

가장 먼저 같은 수들에 대한 처리를 어떻게 해야 할까? 만약 같은 수 5가 i, j에 있다면 i와 j가 뒤바뀌는 일은 절대 없을 것이다. 이를 생각해 보면 i번째 수는 5.000000001, j번째 수는 5.000000002와 같이 순서를 강제해 버려도 상관이 없다는 것을 알 수 있다. 이제 모든 수들이 다른 상황만 생각하자.

버블소트와 연관된 다양한 성질들이 있다. 보통은 "한번 PASS 를 진행할 때 아직 정렬되지 않은 값들 중 최댓값을 오른쪽으로 이동시킨다"는 것을 사용하는데, 이 문제에서는 거꾸로 PASS 의 수를 이용해야 하고, 오른쪽으로 한번 PASS 할 때 많이 움직인다는 것을 생각해 보면 별로 좋은 아이디어 같지 않다.

그래서 거꾸로 생각해 보자. 한번 PASS 진행할 때 많은 수들이 오른쪽으로 움직이지만, 분명히 왼쪽으로 움직이는 수들도 있다. 그런데 왼쪽으로 움직이는 횟수는 한 PASS 당 최대 한번이다. 이를 통해 왼쪽으로 움직여야 하는 횟수들 중 최댓값이 답이라는 것을 알 수 있다.

식을 정리하면 max(i-(A[i]보다 작은 수들의 갯수)) 가 PASS의 횟수이다. 쿼리가 없는 문제를 풀 때에는 A[i]보다 작은 수들의 개수만 구하면 되는데, 이는 BIT 를 이용하여 매우 쉽게 구할 수 있다.

이제 쿼리를 생각해보자. 어떠한 수가 다른 수들로 바뀌면 i-A[i]의 값들은 어떻게 변할까?

몇개의 i-(A[i]보다 작은 수들이 갯수)값들이 변하고, 이때 최댓값을 계산하는 문제이니, Maximum Segment Tree 를 사용하면 풀릴 것 같다.

세그먼트 트리를 어떻게 구성할지에 대해서는 2가지 생각을 해볼 수 있다.

1. i에 대한 segment tree

2. A[i]에 대한 segment tree

i에 대한 segment tree를 구성하면 i-(A[i]보다 작은 수들이 갯수) 중 i는 불변이지만, 업데이트 되었을 때 변하는 값들이 불연속적이라는 것으로 보아 풀기가 쉽지 않아 보인다. A[i]에 대한 segment tree 는 A[i]가 a에서 b로 변했을 때 min(a, b)+1 ~ max(a, b)-1 사이의 값들만 변한다. 이를 이용해 보자.

만약에 a<b 라면 min(a, b)+1 ~ max(a, b)-1 구간의 모든 값들에 대해 자기보다 작은 수가 하나 감소했으니 i-(A[i]보다 작은 수들이 갯수)는 1 증가한다. 반대의 상황은 똑같이 1 감소한다.

이를 통해 lazy propagation 적용된 maximum segment tree 를 사용하면 문제를 풀 수 있다는 것을 알게 되었다. 마지막 문제 하나가 min(a, b)+1 ~ max(a, b)-1 구간 사이의 모든 값들이 차있는 것이 아니라 나중에 들어올 값이여서 지금 비어 있는 칸이면 +1, -1 해도 될까? 이다. 조금만 생각해보면 이는 모든 칸들을 음수 무한대로 채워놓고 시작하면 최댓값인 답에는 영향을 미치지 않을 것이라는 것을 알 수 있다.

정리하자면 A[i]값이 a에서 b로 바뀌었을 때 min(a, b)+1 ~ max(a, b)-1값들에 +1, -1을 해주고, a의 칸에는 음수 무한대, b의 칸에는 새롭게 들어올 i-(A[i]보다 작은 수들의 갯수)를 계산해서 넣어준다. 계산하는 방법은 위 쿼리가 없는 문제를 풀 때 처럼 BIT 를 이용하여 계산해 주면 된다. 이때 A[i]의 값들은 같은 것에 대해서는 i에 대해서 점수를 부여하여 좌표압축한 후 모두 다른 수들로 만들어주고, 처음에는 음수 무한대로 segment tree 를 초기화한다.

여기서 매우 주의해야할 것이 있다. 위 방법을 토대로 생각하면 segment tree에는 lazy propagation 을 이용한 구간에 얼마 더하는 연산, 하나를 바꾸는 연산이 필요하다. 아무 생각없이 하나를 바꾸는 연산을 실행하면 이미 남아있던 lazy 값에 대한 처리를 못해 segment tree가 망가지게 된다. 이를 해결하기 위하여 하나를 바꾸는 연산도 더하는 연산으로 바꾸어 그 차이를 더해준다. 이 과정에서도 lazy값이 잘 적용되어 segment tree 의 형태를 유지하는지를 잘 확인해 주어야 한다.

시간 복잡도 : O((N+Q)lg(N+Q))

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 5e5;
const int MAXQ = 5e5;
const ll NEGINF = -1e17;
 
int N, Q, S;
vector<ll> A, X, V, comp;
vector<int> ans;
 
ll getcomp(ll x)
{
    return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}
 
struct SEG
{
    int N;
    vector<ll> tree, lazy;
    SEG(int N) : N(N), tree(4*N+10, NEGINF), lazy(4*N+10, 0ll) {}
 
    void busy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node]+=lazy[node];
        if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
        lazy[node]=0;
    }
 
    void update_range(int node, int tl, int tr, int l, int r, ll val)
    {
        busy(node, tl, tr);
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            tree[node]+=val;
            if(tl!=tr) lazy[node*2]+=val, lazy[node*2+1]+=val;
            return;
        }
        int mid=tl+tr>>1;
        update_range(node*2, tl, mid, l, r, val);
        update_range(node*2+1, mid+1, tr, l, r, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
        //printf("!!!!!%d %d %d %d %d %lld : %lld %lld\n", node, tl, tr, l, r, val, tree[node], lazy[node]);
    }
 
    void update_change(int node, int tl, int tr, int pos, ll val)
    {
        busy(node, tl, tr);
        if(tl==tr)
        {
            tree[node]+=val;
            return;
        }
        int mid=tl+tr>>1;
        if(pos<=mid) update_change(node*2, tl, mid, pos, val);
        else update_change(node*2+1, mid+1, tr, pos, val);
        tree[node]=max(tree[node*2]+lazy[node*2], tree[node*2+1]+lazy[node*2+1]);
    }
 
    ll read(int node, int tl, int tr, int pos)
    {
        busy(node, tl, tr);
        if(tl==tr) return tree[node];
        int mid=tl+tr>>1;
        if(pos<=mid) return read(node*2, tl, mid, pos);
        else return read(node*2+1, mid+1, tr, pos);
    }
 
    void update_change(int pos, ll val)
    {
        //printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!%lld\n", read(1, 1, N, pos));
        update_change(1, 1, N, pos, val-read(1, 1, N, pos));
    }
 
    void debug(int node, int tl, int tr)
    {
        busy(node, tl, tr);
        if(tl==tr)
        {
            //printf("(%d : %lld) ", tl, tree[node]);
            return;
        }
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }
 
    ll query()
    {
        busy(1, 1, N);
        return tree[1];
    }
};
 
struct BIT
{
    int N;
    vector<ll> tree;
    BIT(int N) : N(N), tree(N+10, 0ll) {}
    void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]+=val; }
    ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};
 
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    int i, j;
    N=a.size(); Q=x.size();
    for(i=0; i<a.size(); i++) A.push_back((ll)a[i]*N+i), comp.push_back((ll)a[i]*N+i);
    for(i=0; i<x.size(); i++) V.push_back((ll)v[i]*N+x[i]), comp.push_back((ll)v[i]*N+x[i]);
    for(i=0; i<v.size(); i++) X.push_back((ll)x[i]);
 
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    S=comp.size();
 
    for(i=0; i<N; i++) A[i]=getcomp(A[i]);
    for(i=0; i<Q; i++) V[i]=getcomp(V[i]);
 
    SEG seg(S);
    BIT bit(S);
 
    for(i=0; i<N; i++) bit.update(A[i], 1);
    for(i=0; i<N; i++) seg.update_change(A[i], i-bit.query(A[i]-1));
 
    //for(i=0; i<N; i++) printf("%lld ", A[i]); printf("\n");
    //seg.debug(1, 1, S); printf("\n");
 
    for(i=0; i<Q; i++)
    {
        ll pos=X[i], bef=A[pos], aft=V[i];
        bit.update(bef, -1);
        bit.update(aft, 1);
 
        if(bef<aft)
        {
            if(bef+1<=aft-1) seg.update_range(1, 1, S, bef+1, aft-1, 1);
            seg.update_change(bef, NEGINF);
            seg.update_change(aft, pos-bit.query(aft-1));
        }
        else
        {
            if(aft+1<=bef-1) seg.update_range(1, 1, S, aft+1, bef-1, -1);
            seg.update_change(bef, NEGINF);
            seg.update_change(aft, pos-bit.query(aft-1));
        }
 
        ans.push_back(seg.query());
 
        A[pos]=V[i];
 
        //printf("%lld %lld %lld\n", pos, bef, aft);
        //for(j=0; j<N; j++) printf("%lld ", A[j]); printf("\n");
        //seg.debug(1, 1, S); //printf("\n");
    }
    return ans;
}

2. catdog

Subtask 2

첫번째 관찰은 트리를 여러 부분집합으로 쪼갰을 때, 각 부분집합에는 A만 있거나, B만 있거나, 비어있을 수 있다. 이때 비어있는 집합은 다른 아무 집합에 합쳐주면 쪼개는 횟수가 줄어듬으로 존재할 수 없다. 즉 모든 부분집합은 A, B중 하나로 그 색이 정해진다. 이를 통해 다음과 같은 Tree DP를 생각해 볼 수 있다.

dp[v][col] : v번째 정점의 색이 col일 때 v를 루트로 하는 서브트리의 안전도

dp[v][A]=sum(min(dp[c][A], dp[c][B]+1))

dp[v][B]=sum(min(dp[c][B], dp[c][A]+1)) 의 점화식을 통하여 모든 dp값들을 계산할 수 있다.

각 쿼리가 들어온 후 dp배열을 계산해 주면 된다.

시간 복잡도 : O(NQ)

Subtask 3

정해의 시작은 HLD(Heavy Light Decomposition) 이다. 트리의 간선들을 무거운 간선과 가벼운 간선으로 구분하여, 여러 개의 체인으로 쪼갠다. 이때 루트에서 임의의 노드까지 가는데 체인을 바꾸는 횟수는 O(lgN) 임이 보장된다.

HLD 를 하는 이유는 일차원에서 문제를 푼 다음, 비슷한 방법으로 응용해서 트리에서 문제를 풀기 위함이다. 1차원 상에서 업데이트가 있는 위 문제를 어떻게 풀 수 있을까? 이와 비슷한 상황이 금광 세그 (maximum subarray segment tree) 가 있다. 이와 같이, DNC SEG 로 풀 수 있다. 각 노드가 양 끝이 AA, AB, BA, BB일 경우를 모두 나눠서, 노드를 합쳐 주며 세그먼트 트리를 관리하면 된다.

여기서 잘 지켜볼 것이, 노드 하나일 때는 어떻게 될까? 일단 AB, BA는 불가능하므로 무한대로 초기화한다. AA, BB는 가벼운 간선들로만 연결된 체인들에서 받아온 dp값을 이용해 갱신한다. 정확히 말하자면, 세그트리에서 이 노드의 의미는 이 노드를 A로 색칠하기 위한 비용, B로 색칠하기 위한 비용이니, Subtask 2에서의 dp처럼 받아오면 된다.

이제, 1차원 문제는 해결했으니, 트리에서를 해결해야 한다. 기본적인 아이디어는 HLD 의 무거운 간선은 DNC SEG 를 이용하여 처리하면 되고, 가벼운 간선은 Subtask 2와 같은 dp를 이용하여 해결해 준다.

위 그림과 같은 상황일 때 v에 대해서 a를 v의 체인 헤드, b를 a의 부모라 하자. 일단, b에서 a체인의 값을 제거해 준다. 다음, a체인에서 v값을 업데이트 해준다. 다음 다시 b에서 a체인의 갱신된 값으로 추가해 준다. 이와 같은 과정을 루트 체인까지 반복해주면 된다.

모든 업데이트를 끝냈으면, 답은 바로 루트 체인의 값을 의미한다.

시간 복잡도 : O(Qlg^2N)

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
const int INF = 1e6;
 
int N;
vector<int> adj[MAXN+10];
 
int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10];
int A[MAXN+10], C[MAXN+10], D[MAXN+10];
 
struct Node
{
    int AA, AB, BA, BB;
    Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {}
    Node() : AA(0), AB(0), BA(0), BB(0) {}
};
 
Node combine(Node lc, Node rc)
{
    Node ret;
    ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA});
    ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB});
    ret.BA=min({lc.BA+rc.AA, lc.BA+rc.BA+1, lc.BB+rc.AA+1, lc.BB+rc.BA});
    ret.BB=min({lc.BA+rc.AB, lc.BA+rc.BB+1, lc.BB+rc.AB+1, lc.BB+rc.BB});
    return ret;
}
 
struct SEG
{
    Node tree[MAXN*4+10];
 
    void init(int node, int tl, int tr)
    {
        if(tl==tr) { tree[node]=Node(0, INF, INF, 0); return; }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
        tree[node]=combine(tree[node*2], tree[node*2+1]);
    }
 
    void update(int node, int tl, int tr, int pos, Node val)
    {
        if(tr<pos || pos<tl) return;
        if(tl==tr)
        {
            tree[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, pos, val);
        update(node*2+1, mid+1, tr, pos, val);
        tree[node]=combine(tree[node*2], tree[node*2+1]);
    }
 
    void query(int node, int tl, int tr, int l, int r, vector<Node> &ret)
    {
        if(l<=tl && tr<=r) { ret.push_back(tree[node]); return; }
        if(r<tl || tr<l) return;
        int mid=tl+tr>>1;
        query(node*2, tl, mid, l, r, ret);
        query(node*2+1, mid+1, tr, l, r, ret);
    }
 
    Node query(int l, int r)
    {
        int i, j;
        vector<Node> V;
        query(1, 1, N, l, r, V);
        Node ret=V[0];
        for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
        return ret;
    }
 
    void debug(int node, int tl, int tr)
    {
        printf("%d %d %d : %d %d %d %d\n", node, tl, tr, tree[node].AA, tree[node].AB, tree[node].BA, tree[node].BB);
        if(tl==tr) return;
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }
}seg;
 
void dfs(int now, int bef, int depth)
{
    sz[now]=1;
    par[now]=bef;
    dep[now]=depth;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, depth+1);
        sz[now]+=sz[nxt];
    }
}
 
void hld(int now, int bef)
{
    idx[now]=cnt++;
 
    int heavy=0;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(sz[heavy]<sz[nxt]) heavy=nxt;
    }
 
    if(heavy==0)
    {
        tail[now]=now;
        return;
    }
 
    head[heavy]=head[now];
    hld(heavy, now);
 
    for(int nxt : adj[now])
    {
        if(nxt==bef || nxt==heavy) continue;
        head[nxt]=nxt;
        hld(nxt, now);
    }
 
    tail[now]=tail[heavy];
}
 
void initialize(int _N, vector<int> A, vector<int> B)
{
    int i, j;
    N=_N;
 
    for(i=0; i<N-1; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
 
    dfs(1, 0, 1);
    head[1]=1;
    hld(1, 0);
    seg.init(1, 1, N);
}
 
int query(int u, int val)
{
    Node chg;
    if(val==0) chg=Node(C[u], INF, INF, D[u]);
    if(val==1)
    {
        Node t=seg.query(idx[u], idx[u]);
        D[u]=t.BB;
        chg=Node(C[u], INF, INF, INF);
    }
    if(val==2)
    {
        Node t=seg.query(idx[u], idx[u]);
        C[u]=t.AA;
        chg=Node(INF, INF, INF, D[u]);
    }
    A[u]=val;
 
    while(head[u]!=1)
    {
        int a=par[head[u]], b=head[u];
        Node qa=seg.query(idx[a], idx[a]), qb=seg.query(idx[head[b]], idx[tail[b]]);
        if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
        seg.update(1, 1, N, idx[u], chg);
        qb=seg.query(idx[head[b]], idx[tail[b]]);
        if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
 
        chg=qa;
        u=par[head[u]];
    }
 
    seg.update(1, 1, N, idx[u], chg);
    Node ans=seg.query(idx[head[1]], idx[tail[1]]);
 
    //seg.debug(1, 1, N); printf("===========================\n");
    return min({ans.AA, ans.AB, ans.BA, ans.BB});
}
 
int cat(int u)
{
    return query(u, 1);
}
 
int dog(int u)
{
    return query(u, 2);
}
 
int neighbor(int u)
{
    return query(u, 0);
}

3. collapse

아직 해결하지 못하였다.