BOJ 31234 - 대역폭 관리

재미있는 문제여서 가져와봤습니다.

경인지역 대학연합 SHAKE 2023 문제인데, 이 대회를 칠 당시에는 hld를 안배웠어서 접근을 못했었던 문제였습니다.

그래도 나름 선방하기는 했었던 아레나였는데, 아마 이 문제를 시간내에 풀었더라면 퍼포 SSS를 띄웠을 것 같아요

한계 대역폭을 어떻게 처리하느냐가 핵심 아이디어인데, 구간 최댓값을 관리하는 lazy segment tree을 작성하고, 초기에 한계 대역폭 값을 음수로 걸어주면 문제를 해결할 수 있습니다.

지문에서 들어오는 쿼리로

대역폭 증가 업데이트 쿼리를 처리하고 난 뒤에, 최댓값 쿼리를 날려봅니다.

최댓값 쿼리가 0을 초과하면 원래 걸어두었던 한계 대역폭을 초과한 대역폭이 지나가고 있는 것이기 때문에 break 후 결과를 출력해주면 됩니다.

트리에서 구간쿼리를 처리하기 때문에, heavy-light decomposition을 활용해서 트리를 쪼개서 관리해주면 문제를 해결할 수 있다.

태그 목록이 살벌한 문제.

개인적으로 lazy segment tree에서 구간 최댓값을 관리해본적이 없는 것 같은데, 이번 기회에 새로 시도해볼 수 있었어서 기억에 남는 문제입니다.

void prop(int s, int e, int node){
    seg[node] += lazy[node];

    if(s != e){
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
    }
    lazy[node] = 0;
    return;
}

propagate 시키는 함수인데, 구간에 덧셈을 해주면 최댓값도 덩달아 더 커지니까 부분합 세그에서의 (e-s+1) 없이 바로 lazy[node] 를 더해주면 됩니다.

void seg_update(int l, int r, ll K, int s=1, int e=M, int node=1){
    if(lazy[node]) prop(s,e,node);
    if(r<s || e<l) return;
    if(l<=s && e<=r){
        lazy[node] = K;
        prop(s,e,node);
        return;
    }

    int mid = (s+e)/2;
    seg_update(l,r,K,s,mid,node*2);
    seg_update(l,r,K,mid+1,e,node*2+1);
    seg[node] = max(seg[node*2], seg[node*2+1]);
    return;
}

ll seg_query(int l, int r, int s=1, int e=M, int node=1){
    if(lazy[node]) prop(s,e,node);
    if(r<s || e<l) return MIN;
    if(l<=s && e<=r) return seg[node];

    int mid = (s+e)/2;
    return max(seg_query(l,r,s,mid,node*2), seg_query(l,r,mid+1,e,node*2+1));
}

세그는 propagate 시키는 부분이 포함된 것을 제외하면 일반적인 최댓값 세그트리와 동일합니다.

void hld(int now = 1){
    siz[now] = 1;
    for(int &nxt : g[now]){
        if(siz[nxt]) continue;

        dep[nxt] = dep[now] + 1;
        par[nxt] = now;

        hld(nxt);

        siz[now] += siz[nxt];
        if(siz[nxt] > siz[g[now][0]]) swap(nxt, g[now][0]);
    }
}

int idx = 0;
void ett(int now = 1){
    st[now] = ++idx;
    for(int nxt : g[now]){
        if(st[nxt]) continue;

        if(nxt == g[now][0]) chain[nxt] = chain[now];
        else chain[nxt] = nxt;
        ett(nxt);
    }
    ed[now] = idx;
}

오일러 투어 테크닉을 활용해서 트리를 구간 형태로 변화시키고, hld를 통해서 해당 구간들을 분할시킵니다.

ll hld_query(int s, int e){
    ll ret = MIN;
    while(chain[s] != chain[e]){
        if(dep[chain[s]] > dep[chain[e]]) swap(s,e);

        ret = max(ret, seg_query(st[chain[e]], st[e]));
        e = par[chain[e]];
    }

    if(st[s] > st[e]) swap(s,e);
    ret = max(ret, seg_query(st[s], st[e]));
    return ret;
}

void hld_update(int s, int e, ll K){
    while(chain[s] != chain[e]){
        if(dep[chain[s]] > dep[chain[e]]) swap(s,e);

        seg_update(st[chain[e]], st[e], K);
        e = par[chain[e]];
    }

    if(st[s] > st[e]) swap(s,e);
    seg_update(st[s], st[e], K);
}

hld_query 함수나 seg_query 에서 임의의 작은 숫자를 사용해야 함에 유의합니다. 저는 -2147483647을 사용했습니다.

    for(int i=1; i<=N; i++){
        cin >> a;
        seg_update(st[i],st[i],-a);
    }

초기에 대역폭 한계를 설정해 주는 부분입니다. -a 만큼을 update해주면 됩니다.

첨언

hld를 풀면서 boj 17429 국제 메시 기구 등의 문제를 쭉쭉 풀고, 오늘 solved.ac 기준 Diamond V를 달성했습니다.

개강 이전에 다이아V를 달성하는것을 목표로 삼았었는데, 대학입시나 대학교에서의 활동 등으로 치여사느라 기회가 없었다만 이번 방학을 통해 찍어둘 수 있었어서 다행이라는 생각이 듭니다.

티어를 더 이상 올리는 것보다는 제가 취약한 부분에 대한 보강이나 codeforces 쪽을 조금 더 집중하게 되지 않을까 싶습니다.

Read more

죽음의 수용소에서 - 빅터 프랭클

죽음의 수용소에서 - 빅터 프랭클

최근 밀리의서재 구독을 신청하며 책을 본격적으로 읽기 시작했다. 스타트를 끊었던 책인 빅터 프랭클의 <죽음의 수용소에서>를 읽으며 느꼈던 점들을 정리해 보고자 한다. 저자 저자 빅터 프랭클은 오스트리아 빈 출신의 신경정신과 교수이다. 1944년 아우슈비츠로 끌려가 여동생을 제외한 가족 모두를 잃었으며, 포로 수용소에서의 경험을 기반으로 심리치료 기법 <로고테라피>

By 박성훈

JENKINS_HOME is almost full 해결 - VM 용량확장

동아리 활동 관련해서 CI/CD를 구축할 일이 생겨서 간만에 젠킨스에 접속해 보았는데, 디렉토리 공간이 부족하다는 경고가 떠서 이를 해결해보도록 하겠다. 각 프로젝트의 오래된 로그를 제거 빌드할때마다 로그라던지를 기록하는데, 로그를 삭제하지 않기 때문에 가만히 내버려두고 있으면 파일이 점점 쌓인다. Pipeline > 구성 > 오래된 빌드 삭제 를 통해서 먼저 사용하지 않는

By 박성훈

wg-easy 구축을 통한 vpn 사용

저는 지금 서울에서 기숙사 생활을 하고 있는데, 기숙사 생활 와중에도 본가에서 열심히 작동중인 서버에 접근하기 위해서는 필연적으로 vpn을 사용해야 했습니다. pptp 등의 일반적인 VPN 프로토콜과 비교했을때 wireguard는 속도나 안전성 면에서 장점을 보이기 때문에, 개인서버를 구축하시는 분들이 많이들 선택하고는 하시는데 wireguard는 터미널 기반의 vpn 프로그램이라 클라이언트 기기들을 추가하기가 조금 귀찮다는 단점이

By 박성훈

tachiyomi 뷰어의 대안, mihon

카카오 엔터테인먼트의 요청 이후, tachiyomi 앱의 코어 개발자들이 지원 중단을 선언하였습니다. 지원 중단 및 프로그램 삭제에 따라 다음 문제들이 발생하게 되었는데, * tachiyomi의 레포 삭제 * tachiyomi의 다운로드 불가 * tachiyomi 내부 확장 프로그램 설치 불가 * 확장 프로그램 저장소의 삭제, tachiyomiSY 등의 호환 앱에서도 확장 설치 불가 그 중에서 확장 프로그램 저장소의 삭제가

By 박성훈