PS 일지 (4/7~4/19)

숫자 놀이 (BOJ 1187)

푼 날짜: 4/7

solved.ac 티어: D5

 

풀이:

N=2^k이기 때문에 간단한 아이디어로도 풀린다.

일단, N=2일 때는 기우성(홀짝성)이 같은 2개의 수를 고르면 된다.

N=2^k (k>=2)인 경우, 수 N-1개를 고른 후, N=2^(k-1)인 경우에서 그 집합에 대해 답을 구해놓는다. 이를 S_1이라 하자.

원래 수들의 집합에서 S_1을 빼고, 방금 했던 시행을 한다. 이 시행을 2번 더 해서 집합 S_2와 S_3를 얻을 수 있고, 이 세 개의 집합의 합들을 2^(k-1)으로 나눴을 때 기우성이 같은 두 집합의 합집합이 답이 된다.

구현은 분할정복처럼 하면 된다.

시간복잡도는 대충 O(3^k) 같은데 맞는지 잘 모르겠다. (얼마인지 알면 댓글로 알려주세요.)

 

참고로 임의의 N에 대해 이 문제의 답이 존재함이 증명되어있다. (EGZ Theorem)

 

코드:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<vector<int>, vector<int>> dnc(vector<int> &v, int n){
    if (n==2){
        ll s=0;
        for (int i=0;i<3;i++) s += v[i];
        for (int i=0;i<3;i++) if (!((s-v[i])&1)){
            vector<int> ret1, ret2;
            for (int j=0;j<3;j++){
                if (j==i) ret2.push_back(v[j]);
                else ret1.push_back(v[j]);
            }
            /*printf("\n");
            for (int x: ret1) printf("%d ", x);
            printf("\n");
            for (int x: ret2) printf("%d ", x);
            printf("\n\n");*/
            return make_pair(ret1, ret2);
        }
    }
    vector<int> cur, tmp[3], ret2;
    for (int i=0;i<n-1;i++) cur.push_back(v[i]);
    for (int z=0;z<3;z++){
        auto tmp2=dnc(cur, n/2);
        tmp[z]=tmp2.first;
        cur.clear();
        for (int i=0;i<n/2-1;i++) cur.push_back(tmp2.second[i]);
        for (int i=0;i<n/2;i++) cur.push_back(v[i+n-1+n*z/2]);
        if (z==2) ret2 = tmp2.second;
    }
    ll s[3]={0}, S=0;
    for (int i=0;i<3;i++){
        for (int j=0;j<n/2;j++) s[i] += tmp[i][j];
        S += s[i];
    }
    for (int i=0;i<3;i++) if (!((S-s[i])&(n/2))){
        vector<int> ret1(n), ret3(n-1), chk;
        for (int j=0;j<3;j++){
            if (j==i) merge(ret2.begin(), ret2.end(), tmp[j].begin(), tmp[j].end(), ret3.begin());
            else chk.push_back(j);
        }
        merge(tmp[chk[0]].begin(), tmp[chk[0]].end(), tmp[chk[1]].begin(), tmp[chk[1]].end(), ret1.begin());
        /*for (int x: ret1) printf("%d ", x);
        printf("\n");
        for (int x: ret3) printf("%d ", x);
        printf("\n");*/
        return make_pair(ret1, ret3);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    vector<int> v(n*2-1);
    for (int i=0;i<n*2-1;i++) scanf("%d", &v[i]);
    vector<int> ans = dnc(v, n).first;
    for (int x:ans) printf("%d ", x);
    return 0;
}

 

애완 트리 (BOJ 19547)

푼 날짜: 4/10

solved.ac 티어: D3

 

풀이:

트리 dp 문제다. 지름이 x 이하라는 조건만 있는 상태에서 풀면 충분하다.

dp[v][i]: 점 v가 루트인 서브트리에서 최대 깊이(v에서 u까지 경로의 가중치 합)가 i이하면서 지름이 x이하를 만족하는 경우의 수

로 놓고 점화식을 세우면 O(N^3)에 풀린다.

기본 아이디어는 이건데 점화식이 좀 복잡해서 dp배열을 2개 관리해서 풀었다.

자세하게 설명하려면 너무 길어지니까 생략. (사실 어떻게 풀었는지 잘 기억 안 남)

 

이 문제를 추천해준 지인들은 다 엄청 쉽게 풀었다는데 나는 처음에 l r 제한이 400인걸 못 보고 그다음엔 점화식이 복잡해서 머리가 터지고 O(N^4)을 O(N^3)으로 줄이느라 또 머리가 터지고 예외케이스랑 상수 때문에 계속 틀려서 푸는데 많이 힘들었다. ㅋㅋ;

 

코드:

(메모리 1기가에 시간 6초 걸리는 노답 구현이다...)

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

typedef long long ll;
using namespace std;
struct edge{
    int to, l, r;
    edge(){}
    edge(int _to, int _l, int _r): to(_to), l(_l), r(_r) {}
};
const int MOD = 1e9+7, MXL = 160160;
int dp1[404][160160], dp2[404][160160], Mp[404][160160], Ms[404][160160];
//unordered_map<int, int> INV;
vector<edge> adj[404];

int add(int x, int y){
    int ret = x+y;
    if (ret>=MOD) return ret-MOD;
    return ret;
}

int str(int x, int y){
    int ret = x-y;
    if (ret<0) return ret+MOD;
    return ret;
}

int mul(int x, int y){
    ll ret = ((ll)x*y)%MOD;
    return (int)ret;
}

int pw(int a, int e){
    if (!e) return 1;
    int ret = pw(a, e/2);
    ret = mul(ret, ret);
    if(e&1) ret = mul(ret, a);
    return ret;
}

/*int inv(int x){
    if (INV.find(x)!=INV.end()) return INV[x];
    if (INV.size()>1e6) INV.clear();
    INV[x] = pw(x, MOD-2);
    return INV[x];
}*/

void dfs(int s, int mx, int pa){
    int cur=1;
    dp1[s][0]=1;
    for (auto &v:adj[s]) if (v.to!=pa){
        dp1[s][0]=0;
        dfs(v.to, mx, s);
        for (int i=v.l;i<=min(mx, MXL-1);i++){
            int tmp = 0;
            if (i>=v.r+1) tmp = dp1[v.to][i-v.r-1];
            dp2[v.to][i] = add(dp2[v.to][i-1], str(dp1[v.to][i-v.l], tmp));
        }
    }
    unordered_map<int, int> idx, idx1;
    for (auto &v:adj[s]) if (v.to!=pa){
        idx[v.to] = cur++;
        idx1[cur-1] = v.to;
        for (int i=0;i<v.l;i++) Mp[cur-1][i]=0;
        for (int i=v.l;i<=min(mx, MXL-1);i++){
            Mp[cur-1][i] = mul(Mp[cur-2][i], dp2[v.to][i]);
        }
    }
    //fill(M, M+min(mx, MXL-1)+1, 1);
    //fill(C, C+min(mx, MXL-1)+1, 0);
    fill(Ms[cur], Ms[cur]+min(mx, MXL-1), 1);
    for (int p=cur-1;p>=0;p--){
        for (int j=0;j<=min(mx, MXL-1);j++) Ms[p][j] = mul(Ms[p+1][j], dp2[idx1[p]][j]);
    }
    for (int val=1;val<=min(mx, MXL-1);val++){
        if (val*2<=mx){
            dp1[s][val] = Mp[cur-1][val];
        }
        else{
            //int tmp = 0;
            dp1[s][val] = dp1[s][val-1];
            for (auto &v:adj[s]) if (v.to!=pa){
                int tmp1 = 0, tmp2 = 0;
                if (val>=v.l) tmp1 = dp1[v.to][val-v.l];
                if (val>=v.r+1) tmp2 = dp1[v.to][val-v.r-1];
                //if (s==1 && val==8) printf("%d %d %d\n", tmp1, tmp2, dp2[v.to][mx-val]);
                //if (s==8 && val==21) printf("%d %d %d %d %d %d\n", tmp1, tmp2, v.to, idx[v.to], Mp[idx[v.to]-1][mx-val], Ms[idx[v.to]+1][mx-val]);
                dp1[s][val] = add(dp1[s][val], mul(str(tmp1, tmp2), mul(Mp[idx[v.to]-1][mx-val], Ms[idx[v.to]+1][mx-val])));
            }
            //if (val==8 && s==1) printf("%d %d %d\n", mul(tmp, M[mx-val]), tmp, M[mx-val]);
            //dp1[s][val] = add(mul(tmp, M[mx-val]), dp1[s][val-1]);
        }
    }
}

int main(){
    int n, s, e;
    scanf("%d %d %d", &n, &s, &e);
    for (int i=1;i<=n-1;i++){
        int a, b, x, y;
        scanf("%d %d %d %d", &a, &b, &x, &y);
        adj[a].push_back(edge(b, x, y));
        adj[b].push_back(edge(a, x, y));
    }
    int ans1, ans2;
    fill(Mp[0], Mp[0]+MXL, 1);
    dfs(1, e, -1); ans1=dp1[1][min(e, MXL-1)];
    /*for (int i=1;i<=n;i++){
        for (int j=0;j<=min(e, MXL-1);j++) printf("%d %d: %d %d\n", i, j, dp1[i][j], dp2[i][j]);
    }*/
    dfs(1, s-1, -1); ans2=dp1[1][min(s-1, MXL-1)];
    if (s==1) ans2=0;
    //printf("%d %d\n", ans1, ans2);
    printf("%d\n", str(ans1, ans2));
    return 0;
}

 

BOJ 14589 (Line Friends (Large))

푼 날짜: 4/11

solved.ac 티어: P1

 

풀이:

문제를 딱 보면 세그먼트 트리 문제 느낌이 나는데 놀랍게도 세그 문제가 아니다.

i번째 선분에 대해 k번의 이동으로 갈 수 있는 x좌표의 최댓값을 알 수 있다면, 쿼리를 처리할 수 있다.

i번째 선분에 대해 1번의 이동으로 갈 수 있는 가장 오른쪽에 있는 선분을 j라고 하고, i에서 j로 간선을 연결한 그래프를 생각해보면, 임의의 정점은 out_degree가 1이하이므로 간선을 따라 k번 이동하는 경로는 유일해지고, 정점 i에서 간선을 따라 k번 이동하면 x좌표의 최댓값을 구할 수 있다.

이를 로그시간에 처리하기 위해 sparse table을 만들어주고, lca 구하듯이 쿼리를 처리하면 쿼리를 O(logN)에 처리할 수 있다.

시간복잡도는 O((N+Q)logN)이다.

 

코드:

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Line{
    int l, r, n;
    Line(){}
    Line(int _l, int _r, int _n): l(_l), r(_r), n(_n) {}
    bool operator < (const Line &L) const{
        return l<L.l;
    }
} l1[150150], l2[150150];
unordered_map<int, int> idx;
set<int> st;
vector<int> adj[150150];
int deg[150150], sparse[150150][20];

bool comp(Line &x, Line &y){
    return x.r<y.r;
}

bool compn(Line &x, Line &y){
    return x.n<y.n;
}

void dfs(int s, int pa = -1){
    if (pa!=-1) sparse[s][0]=pa;
    for (int i=1;i<20;i++) sparse[s][i] = sparse[sparse[s][i-1]][i-1];
    for (int v:adj[s]) if (v!=pa){
        dfs(v, s);
    }
}

void query(int x, int y){
    int ans = 0;
    if (l2[x].r>=l2[y].l){
        printf("1\n"); return;
    }
    for (int i=19;i>=0;i--){
        int tmp = sparse[x][i];
        if (!tmp || l2[tmp].r>=l2[y].l) continue;
        x = tmp; ans += (1<<i);
    }
    printf("%d\n", ans+2);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++){
        int a, b;
        scanf("%d %d", &a, &b);
        l1[i] = Line(a, b, i);
        l2[i] = Line(a, b, i);
        idx[b] = i;
    }
    sort(l1+1, l1+n+1); sort(l2+1, l2+n+1, comp);
    int pt1=1, cur = -1e9;
    for (int i=1;i<=n;i++){
        while(pt1<=n && l1[pt1].l<=l2[i].r) cur = max(cur, l1[pt1++].r);
        if (cur==l2[i].r){
            if (st.find(cur)==st.end()) st.insert(cur);
            continue;
        }
        adj[idx[cur]].push_back(l2[i].n);
        deg[l2[i].n]++;
    }
    for (int i=1;i<=n;i++) if (!deg[i]) dfs(i);
    sort(l2+1, l2+n+1, compn);
    int q;
    scanf("%d", &q);
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (st.lower_bound(l2[x].l)!=st.lower_bound(l2[y].l)){
            printf("-1\n"); continue;
        }
        if (l2[x].r>l2[y].r) swap(x, y);
        query(x, y);
    }
    return 0;
}

 

BOJ 11266/11400 (단절점/단절선)

푼 날짜: 4/12

solved.ac 티어: P5/P5

 

풀이/코드: 웰노운이니까 생략.

 

BOJ 10957 (Pipes)

푼 날짜: 4/12

solved.ac 티어: D5

 

풀이:

따로 문제를 깊게 고민해본적은 없는데 지인한테 풀이 스포 당해서 걍 구현해봤다.

선분을 전부 저장하는 것은 불가능하기 때문에 반드시 필요한 선분 몇 개만 저장할 것이다.

선분 {x, y}를 추가하는 상황을 생각해보자.

만약 x에서 y로 가는 2개의 독립된 경로가 존재한다면, {x, y}를 추가하지 않아도 임의의 선분에 대해 그 선분을 제거했을 때의 연결성의 변화는 달라지지 않는다. 즉, {x, y}를 추가하는 것이 무의미하다.

따라서, 다음과 같은 알고리즘을 구현하면 된다.

 

유니온 파인드 2개를 각각 S1, S2라고 하자.

1. x, y가 S1에서 연결되어 있지 않다면 S1에서 연결해주고 간선을 그래프에 추가한다.

2. x, y가 S1에서 연결되어 있는데 S2에서 연결되어 있지 않다면 S2에서 연결해주고 간선을 그래프에 추가한다.

3. 둘 다 연결된 상태라면 2개의 독립된 경로가 존재한다는 뜻이므로 무시한다.

 

그러면 그래프의 간선은 2N개이고, 여기서 단절선을 구해주면 메모리 초과가 발생하지 않는다.

시간복잡도는 O(NlogN)이다. (유파 구현을 바꾸면 로그를 애커만으로 줄일 수 있음)

 

코드:

참고로 scanf로 입력 받으면 높은 확률로 TLE가 난다. cin이나 fastio를 쓰자.

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> path1(100100), path2(100100), h1(100100), h2(100100), adj[100100];
int dfn[100100], low[100100], cur=1;
bool visited[100100];
vector<pair<int, int>> ans;

int dis_find(int s, vector<int> &path){
    if (s==path[s]) return s;
    return path[s] = dis_find(path[s], path);
}

void dis_merge(int u, int v, vector<int> &path, vector<int> &h){
    int x = dis_find(u, path), y = dis_find(v, path);
    if (h[x]>h[y]) swap(x, y);
    path[x] = y;
    if (h[x] == h[y]) h[y]++;
}

void dfs(int s, int pa = -1){
    visited[s] = 1;
    dfn[s] = cur++;
    low[s] = dfn[s];
    bool chk=0;
    for (int &v:adj[s]){
        if (v==pa){
            if (!chk) chk=1;
            else low[s] = min(low[s], dfn[pa]);
        }
        else if (!visited[v]){
            dfs(v, s);
            low[s] = min(low[s], low[v]);
            if (low[v]>dfn[s]) ans.push_back(make_pair(s, v));
        }
        else low[s] = min(low[s], dfn[v]);
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) path1[i] = i, path2[i] = i;
    for (int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        if (dis_find(a, path1)!=dis_find(b, path1)){
            dis_merge(a, b, path1, h1);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        else if (dis_find(a, path2)!=dis_find(b, path2)){
            dis_merge(a, b, path2, h2);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    for (int i=1;i<=n;i++) if (!visited[i]) dfs(i);
    for (auto &p:ans) cout << p.first << ' ' << p.second << '\n';
    return 0;
}

 

BOJ 15902 (Split and Merge)

푼 날짜: 4/13

solved.ac 티어: D5

 

풀이:

일단, 처음과 최종 상태에서 겹치는 경계선에 대해 그 경계선에 대해 합치는 시행을 하고 분리하는 시행을 하는 것은 최적이 아니다.

즉, 다음 시행의 가짓수만 미리 구해놓으면 답을 쉽게 알 수 있다. (시행 횟수는 i-1)

초기 상태: x | xx | xx | xx

최종 상태: xx | xx | xx | x

길이가 i일 때 가짓수를 dp[i]라고 놓고, 처음 자를 xx 조각을 골라주면 다음과 같은 점화식을 얻을 수 있다.

dp[n] = sum_{k=1}^{k=floor(n/2)} {dp[2k]*dp[n-2k]*binomial(n-2, 2k-1)}

시간복잡도는 O(N^2)이다.

 

코드:

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll MOD = 1000000007;
ll ncr[3030][3030], fac[3030], facinv[3030], dp[3030];
vector<int> a, b;

ll pw(ll a, ll e){
    if (!e) return 1;
    ll ret = pw(a, e/2);
    ret = (ret*ret)%MOD;
    if (e&1) return (ret*a)%MOD;
    return ret;
}

ll inv(ll x){
    return pw(x, MOD-2);
}

int main(){
    fac[0] = ncr[0][0] = facinv[0] = 1;
    for (int i=1;i<3030;i++){
        for (int j=0;j<=i;j++){
            if (!j || i==j) ncr[i][j] = 1;
            else ncr[i][j] = (ncr[i-1][j-1]+ncr[i-1][j])%MOD;
        }
        fac[i] = (fac[i-1]*i)%MOD;
        facinv[i] = inv(fac[i]);
    }
    dp[1] = dp[2] = 1;
    for (int i=3;i<3030;i++){
        for (int j=2;j<i;j += 2){
            dp[i] = (dp[i]+(dp[j]*dp[i-j])*ncr[i-2][j-1])%MOD;
        }
        //if (i<=12) printf("%lld\n", dp[i]);
    }
    int l, n, m;
    scanf("%d", &l);
    scanf("%d", &n);
    a.push_back(0); b.push_back(0);
    for (int i=0;i<n;i++){
        int x;
        scanf("%d", &x);
        a.push_back(a.back()+x);
    }
    scanf("%d", &m);
    for (int i=0;i<m;i++){
        int x;
        scanf("%d", &x);
        b.push_back(b.back()+x);
    }
    int pt1=0, pt2=0, s=0, ans=0;
    vector<int> calc;
    while(true){
        //printf("%d %d %d\n", pt1, pt2, ans);
        if (a[pt1]<=b[pt2]) pt1++;
        else pt2++;
        if (pt1>=(int)a.size() || pt2>=(int)b.size()) break;
        if (a[pt1]==b[pt2]){
            if (a[pt1]-s==1){
                s = a[pt1]; continue;
            }
            else if (a[pt1]-s==2){
                if ((a[pt1]-a[pt1-1]==2) && (b[pt2]-b[pt2-1]==2)){
                    s = a[pt1]; continue;
                }
                calc.push_back(2);
                ans += 1;
                s = a[pt1];
            }
            else{
                calc.push_back(a[pt1]-s);
                ans += (a[pt1]-s-1);
                s = a[pt1];
            }
        }
    }
    ll ans2=fac[ans];
    for (auto &x:calc){
        ans2 = (ans2*facinv[x-1])%MOD;
        ans2 = (ans2*dp[x])%MOD;
    }
    printf("%d %lld\n", ans, ans2);
    return 0;
}

 

BOJ 1396/8217/16977 (크루스칼의 공/유성/히스토그램에서 가장 큰 직사각형과 쿼리)

푼 날짜: 4/13, 4/14, 4/15

solved.ac 티어: P1, D4, D3

 

풀이:

PBS 공부하면서 풀어봤다. 크루스칼의 공과 유성은 PBS 예제 수준이여서 풀이는 생략한다. 히가큰직쿼는 PBS 돌릴 때 크루스칼의 공처럼 제일 높은 직사각형부터 추가해주면서 금광세그로 가능한지 판별해주면 된다.

 

유성은 아무 생각없이 레이지 세그 썼다가 TLE 떠서 바텀업 세그 박았다. (펜윅은 내가 쓸줄 모름)

long long 오버플로우 나는 문제니까 조심하자.

 

코드는 생략.

 

BOJ 12766 (지사 배정)

푼 날짜: 4/14

solved.ac 티어: D5

 

풀이:

문제 표현 때문에 오해할 수 있는데 문제에서 구하라고 하는 값은 각 그룹에 대해 같은 그룹인 임의의 두 지사 i, j에 대해 i->본부->j의 값을 모두 더한 것이다.

일단 다익스트라를 2번 돌려서 i->본부, 본부->i의 값들을 모든 i에 대해 구해놓고 저장한다.

그다음 dp[i][j]를 1~i까지 j개의 그룹으로 나눴을 때 답이라고 정의하면, dp[i][j] = min_{k<i} (dp[k][j-1] + c[k][i]) 꼴의 점화식이 나오는데 c[k][i]는 다익스트라 돌린 걸로 계산할 수 있고, 식 정리를 좀 해보면 c가 monge array라서 dnc opt를 쓸 수 있다.

 

시간복잡도는 O(N^2logN)이다.

 

구현을 했는데 TLE가 자꾸 나길래 한참을 고민하다가 icpc 공식 사이트에서 데이터를 다운받아서 TLE 나는 케이스를 찾아서 디버깅을 했다... (너무 추하지만 어쩔 수 없었다...)

TLE나는 케이스가 모두 0인 케이스 딱 1개였는데 직접 돌려보면 7초? 그쯤이라 애매하게 TLE가 나서 많이 빡쳤다. (시간제한은 5초)

dp[n-1][j]가 0이 되면 그 이후로는 답이 0이라 dp 값 계산을 중단하도록 조건을 추가해주니까 TLE가 나지 않았다.

AC 받고 다른 사람 코드 보면서 이유를 찾으려고 했지만 결국 왜 그 케이스만 그렇게 오래 걸리는건지 이유를 찾지 못했다...

 

코드:

참고로 문제 풀이에 있는 dp[i][j]에서 i랑 j 바뀐 상태임

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

typedef long long ll;
using namespace std;
struct Vertex{
    int e;
    ll w;
    Vertex(){}
    Vertex(int _e, ll _w): e(_e), w(_w) {}
    bool operator<(const Vertex &V) const{
        return w>V.w;
    }
};
vector<vector<Vertex>> adj(5050), adj2(5050);
ll a[5050], dp[5050][5050], sum[5050];
int n, b, S, r;
ll cnt=0;

void dijkstra(vector<vector<Vertex>> &Adj){
    vector<bool> visited(n+1, 0);
    vector<ll> dist(n+1, 1e18);
    priority_queue<Vertex> pq;
    pq.push(Vertex(b+1, 0));
    while(!pq.empty()){
        Vertex s = pq.top();
        pq.pop();
        if (visited[s.e] || dist[s.e]<s.w) continue;
        visited[s.e]=1;
        for (auto &v:Adj[s.e]) if (dist[v.e]>s.w+v.w && !visited[v.e]){
            pq.push(Vertex(v.e, s.w+v.w));
            dist[v.e] = s.w+v.w;
        }
    }
    for (int i=1;i<=b;i++) a[i] += dist[i];
}

ll calc(int i, int j){
    //if (i>=j) return 1e18;
    return (sum[j]-sum[i])*(j-i-1);
}

void dnc(int l, int r, int s, int e, int idx){
    if (l>r) return;
    //cnt += (min(e, ((l+r)>>1)-1)-s);
    int m = (l+r)>>1, opt = s;
    dp[m][idx] = dp[opt][idx-1]+calc(opt, m);
    for (int i=s+1;i<=min(e, m-1);i++){
        if (dp[i][idx-1]+calc(i, m)<dp[m][idx]){
            opt = i;
            dp[m][idx] = dp[opt][idx-1]+calc(opt, m);
        }
    }
    //if (dp[m][idx]>1e18) dp[m][idx] = 1e18;
    dnc(l, m-1, s, opt, idx);
    dnc(m+1, r, opt, e, idx);
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> b >> S >> r;
    for (int i=0;i<r;i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back(Vertex(b, w));
        adj2[b].push_back(Vertex(a, w));
    }
    //printf("YES\n");
    dijkstra(adj); dijkstra(adj2);
    //printf("YES2\n");
    //for (int i=1;i<=b;i++) printf("%lld ", a[i]);
    //printf("\n");
    sort(a+1, a+b+1);
    for (int i=1;i<=b;i++) sum[i] = sum[i-1] + a[i];
    for (int i=1;i<=b;i++) dp[i][1] = sum[i]*(i-1);
    for (int i=2;i<=S;i++){
        if (!dp[b][i-1]){
            cout << 0;
            return 0;
        }
        dnc(1, b, 1, b-1, i);
    }
    /*for (int j=1;j<=S;j++){
        for (int i=1;i<=b;i++) printf("%lld ", dp[i][j]);
        printf("\n");
    }*/
    ll ans = dp[b][S];
    //for (int i=1;i<=S;i++) ans = min(ans, dp[b][i]);
    //printf("%lld\n", cnt);
    cout << ans;
    return 0;
}

 

BOJ 19938 (Stations)

푼 날짜: 4/18

solved.ac 티어: D5

 

풀이:

이 일지에 적은 문제들 중 제일 재밌는 문제였다.

섭태 1, 2, 3, 4는 사실 무의미하고 걍 섭태 5를 풀면 된다.

x에서 y로 가야하는 쿼리가 들어왔을 때, y가 x의 서브트리에 속해있다면 x가 아래로 가야하고, 그렇지 않으면 x가 위로 가야한다는 관찰로 접근을 했다.

 

서브트리 판별을 위해, 처음에는 점들을 dfs ordering으로 번호를 붙여봤다.

x의 서브트리에 있는 점들의 번호는 모두 x 이상이지만, 이는 필요충분조건이 아니기 때문에 쿼리를 처리할 수 없다는 걸 알 수 있다.

반대로, 자신의 자식들을 모두 dfs 돈 후, 자기 자신의 번호를 붙이는 방식으로 번호를 붙이게 되면 x의 서브트리에 있는 점들의 번호는 모두 x 이하가 되지만 이것도 필요충분조건이 아니라 쿼리를 처리할 수 없다.

(점 x에 대해 첫 번째 방법으로 했을 때 번호를 i, 두 번째 방법으로 했을 때 번호를 j라고 한 다음 i*1000+j로 번호를 붙여주면 서브트리를 판별할 수 있게 된다. 물론 만점은 받지 못한다.)

 

여기서 한참을 고민하다가 갑자기 아이디어가 떠올라서 만점 풀이를 찾아냈다.

 

아이디어: 점 x에 대해, x의 깊이가 짝수라면 x에 번호를 붙이고 자식들을 탐색하고, 홀수라면 자식들을 모두 탐색한 후 x에 번호를 붙인다.

 

이렇게 하게 되면, 깊이가 짝수인 경우와 홀수인 경우로 나눠서 x의 서브트리에 속하는 점들의 번호의 범위와, x의 부모 모두 계산하는게 가능해진다. (이는 직접 해보길 바란다.)

 

label 함수의 시간복잡도는 O(N)이고, find_next_station의 시간복잡도는 이분탐색을 사용해서 O(log(d(v))이다. (d(v)는 점 v의 차수)

 

코드:

#include "stations.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[1010], ans;
bool visited[1010];
int cur=0;

void dfs(int s, int dep){
    if (!(dep&1)) ans[s] = cur++;
    visited[s] = 1;
    for (auto &v:adj[s]) if (!visited[v]){
        dfs(v, dep+1);
    }
    if (dep&1) ans[s] = cur++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i=0;i<n;i++){
        adj[i].clear(); visited[i] = 0;
    }
    ans.clear();
    ans.resize(n);
    cur = 0;
    for (int i=0;i<n-1;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0, 0);
    //for (int i=0;i<n;i++) printf("%d ", ans[i]);
    //printf("\n");
    return ans;
}

int find_next_station(int s, int t, vector<int> c) {
    int l, r;
    if (!s) l = 0, r = c.back();
    else if (c[0]<s){
        r = s;
        if ((int)c.size()<2) l = s;
        else l = c[1];
    }
    else{
        l = s;
        if ((int)c.size()<2) r = s;
        else r = c[c.size()-2];
    }
    if (l<=t && t<=r){
        if (c[0]<s){
            auto iter = upper_bound(c.begin(), c.end(), t);
            return *(--iter);
        }
        else{
            auto iter = lower_bound(c.begin(), c.end(), t);
            return *iter;
        }
    }
    else{
        if (c[0]<s) return c[0];
        else return c.back();
    }
}

 

BOJ 17678 (합병)

푼 날짜: 4/19

solved.ac 티어: D4

 

풀이:

풀이가 조금 복잡한 편이니 그림을 그리면서 이해하는 것을 추천합니다.

 

그래프를 루트가 1인 트리로 바꿔놓고 생각하자.

분열가능한 상태는 "어떤 점 v가 존재하여 v가 루트인 서브트리에 속한 모든 정점들에 대해 그 정점과 동일한 색의 정점이 모두 같은 서브트리에 속해 있는 것"과 동치이다.

이러한 정점 v를 모두 구해놓은 상태라고 하자. (이를 모아놓은 집합을 S라고 하자.)

이때, 다음 조건을 만족하는 정점을 "특별한 정점"이라고 하자.

조건: S의 원소이면서, 자신을 제외한 자신의 서브트리에 속한 어떤 정점도 S의 원소가 아니다.

 

lca가 1번 정점인 2개의 특별한 정점을 같은 주로 병합시키면, S에서 그 2개의 정점과 조상들은 모두 제거됨을 알 수 있다. 따라서, 최적의 전략은 lca의 깊이가 제일 낮은 2개의 특별한 정점을 병합시키는 것을 반복하는 것이고, 마지막에 1개만 남으면 1번 정점과 병합시키면 된다.

따라서, 특별한 정점의 개수를 x라고 할 때, floor((x+1)/2)가 최소 횟수가 된다.

 

여기서 예외 케이스가 1가지 있는데 만약 어떤 S의 원소 w가 존재하여, 1에서 S의 원소로 가는 경로 상에 항상 w가 존재한다면, 점 w는 특별한 정점 2개를 병합시키는 시행을 통해 S에서 제거될 수 없다. 그래서 따로 특별한 정점 1개를 1번정점과 병합시켜주는 시행을 해야 하고, 횟수 계산은 단순히 x에 1을 더하고 floor((x+1)/2)를 계산하는 것으로 처리할 수 있다.

 

이제, 집합 S의 원소를 구하는 방법을 생각해보자.

단순하게 색깔별로 정점이 몇 개 있는지를 관리하면서 dfs를 하면 O(NK)에 구할 수 있다.

시간복잡도를 줄이는 방법을 생각해보자.

i번 색인 정점 v_1, v_2, ..., v_j에 대해, 이들을 모두 서브트리에 포함하는 깊이가 최대인 점 y_i는 lca를 통해 O(jlogN)에 구할 수 있다.

모든 색에 대해 이를 구해놓고, dfs를 돌리자.

정점 v를 탐색할 때, v의 서브트리의 원소들 중 y_i인 정점들에 대해 i번 색의 개수를 모두 더한 것을 z[v]라고 하자. v가 S의 원소라면, z[v]는 v의 서브트리 크기와 동일하고, 그렇지 않다면 z[v]는 v의 서브트리 크기보다 작다는 것을 확인할 수 있다.

따라서, O(NlogN)에 S의 원소를 모두 구할 수 있다.

 

전체 시간복잡도는 O(NlogN)이다.

 

코드:

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[500500], joi[500500], v[500500];
int col[500500], cnt[500500], val=0, val2=0;
bool visited[500500], visited2[500500], chk[500500];
struct LCA{
    int spa[500500][21], dep[500500];
    void dfs(int s, int pa=0){
        spa[s][0]=pa;
        for (int i=1;i<21 && spa[s][i-1];i++) spa[s][i] = spa[spa[s][i-1]][i-1];
        dep[s] = dep[pa]+1;
        for (auto &v:adj[s]) if (v!=pa){
            dfs(v, s);
        }
    }
    int query(int v, int u){
        if (dep[v]>dep[u]) swap(v, u);
        for (int i=20;i>=0;i--) if (spa[u][i] && dep[spa[u][i]]>dep[v]) u = spa[u][i];
        if (dep[v]!=dep[u]) u = spa[u][0];
        if (v!=u){
            for (int i=20;i>=0;i--) if (spa[v][i] && spa[v][i]!=spa[u][i]) v = spa[v][i], u = spa[u][i];
            v = spa[v][0], u = spa[u][0];
        }
        return v;
    }
}lca;

pair<int, int> dfs1(int s){
    pair<int, int> ret;
    ret.second = 1;
    for (auto &x:v[s]){
        ret.first += cnt[x];
    }
    visited[s]=1;
    //printf("%d %d %d\n", s, ret.first, ret.second);
    //printf(" %d %d %d\n", col[s], lct[col[s]], cnt[s]);
    for (auto &v:adj[s]) if (!visited[v]){
        auto tmp = dfs1(v);
        ret.first += tmp.first;
        ret.second += tmp.second;
    }
    if (ret.first==ret.second) chk[s]=1;
    //printf("%d %d %d\n", s, ret.first, ret.second);
    return ret;
}

int dfs2(int s, bool test){
    int ret=0;
    if (chk[s]) ret++;
    if (chk[s] && s!=1 && !test) test=1, val2++;
    visited2[s] = 1;
    for (auto &v:adj[s]) if (!visited2[v]){
        ret += dfs2(v, test);
    }
    if (chk[s] && ret==1 && s!=1) val++;
    return ret;
}

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i=0;i<n-1;i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i=1;i<=n;i++){
        scanf("%d", col+i);
        cnt[col[i]]++;
        joi[col[i]].push_back(i);
    }
    lca.dfs(1);
    for (int i=1;i<=k;i++){
        int tmp;
        tmp = joi[i][0];
        if (cnt[i]==1){
            v[tmp].push_back(i); continue;
        }
        for (int j=1;j<cnt[i];j++){
            tmp = lca.query(tmp, joi[i][j]);
        }
        v[tmp].push_back(i);
    }
    dfs1(1);
    dfs2(1, 0);
    /*for (int i=1;i<=k;i++) printf("%d ", lct[i]);
    printf("\n");
    for (int i=1;i<=n;i++) printf("%d ", chk[i]);
    printf("\n");*/
    if (val2==1) val++;
    //printf("%d\n", val2);
    printf("%d\n", (val+1)/2);
    return 0;
}