2022.05.07 PS 일지 ★

오늘 기분이 좀 안 좋았었는데 문제가 잘 풀려서 싹 나았다.

+) 32일 스트릭 뱃지 달성

+) 세그트리 태그 티어 플래5 달성

냅색문제

문제 링크

기억에, 옛날에 못 풀고 끙끙댔던 것 같은데

오늘 풀어보니까 풀이가 바로 떠올랐고, 구현도 쉬웠다.

풀이

$N\le 30$이니까 meet in the middle을 써야 한다는 것이 보일 수 밖에 없다.

$\lfloor N/2\rfloor$랑 $N-\lfloor N/2\rfloor$개로 각각 나눠서 모든 경우를 나열한 뒤에

이진 탐색으로 하나씩 확인해주면 된다. 구현도 간단해서 코드는 생략한다.

데이터 만들기 1

문제 링크

APIO 2013 기출이다. 최단경로를 입문하는 사람한테 반례에 대한 사고력을 높여줄 만한 문제들인 것 같다.

풀이.

간단히 $V\ge 1000$인 상황을 만들어주면 터진다.

데이터 만들기 5

문제 링크

APIO 2013 기출이다. 벨만-포드의 작동 원리를 잘 이해했다면 풀 수 있는 문제다.

풀이..

$Q=10$으로 맞추자.

$V$는 뭐 다르게 잡아도 될텐데 깔끔하게 $300$으로 잡아도 된다.

직선형 그래프를 구성한다.

단, 벨만-포드에서 변화가 없는 경우 미리 탈출하는 것을 방지하기 위해 적당히 역순으로 구성해준다.

대충 이런 모양이다

그러면 계산량이 $Q\times (V-1)\times (V-1)=10\times 299\times 299=894\,010$으로, 약간 모자라다.

이때 사용한 정수의 개수가 $1+898+1+20$인데(그냥 해보면 그렇게 될 것이다), 좀 남으니까 0에다가 루프로 때려 넣으면 계산량이 $1\,000\,000$를 넘길 것으로 기대할 수 있다.

요렇게

실제로, $Q\times (V-1)\times E=10\times 299\times (299+40)=1\,013\,610$이 된다. 이렇게 플3을 날먹..!!

삼색 그래프

문제 링크

마음에 드는 문제다.

풀이...

기존 다익스트라 알고리즘이 풀 수 있는 문제에 빨간색 값과 파란색 값이라는 2가지 요소가 포함된 것이다.

그리고 각 경로에 포함된 빨간색 간선과 파란색 간선의 개수 각각이 가중된다.

참고로, 당연히 $X$는 남김없이 사용해야 한다.

따라서 각 경로의 길이는 $($경로 위 빨간색 간선 수$)\times k+($경로 위 파란색 간선 수$)\times (X-k)+($기존 간선 가중치들의 합$)$으로 표현될 것이다.

이는 직선형 함수로서, 각 경로 $i$에 대해 경로의 길이를 $f_i(k)$라 하면, $\displaystyle \min_i f_i(k)$는 볼록함수가 된다.

따라서 삼진 탐색 또는 증가 여부에 따른 이진 탐색이 가능해진다.

그렇게 플4도 날먹..!!

코드

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 2e5+3;
int n, m;
ll ts;
vector<tuple<int,ll,int>> adj[N];

ll dist[N];
ll f(ll R) {
    ll B = ts-R;
    fill(dist,dist+N,1e18);
    priority_queue<pair<ll,int>> pq;
    pq.push({0,1}), dist[1] = 0;
    while (not empty(pq)) {
        auto [d,a] = pq.top(); pq.pop(); d=-d;
        if (d > dist[a]) continue;
        for (auto [b,w,p] : adj[a]) {
            if (p == 1) w += R;
            if (p == 2) w += B;
            if (dist[b] > dist[a]+w) {
                dist[b] = dist[a]+w;
                pq.push({-dist[b],b});
            }
        }
    }
    return dist[n];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> ts;
    REP(i,1,m) {
        int u, v, w, p;
        cin >> u >> v >> w >> p;
        adj[u].push_back({v,w,p});
        adj[v].push_back({u,w,p});
    }
    ll a = 0, b = ts-1;
    while (a <= b) {
        ll m = (a+b)/2;
        if (f(m) < f(m+1)) a = m+1;
        else b = m-1;
    }
    cout << f(a);
}

북서풍

문제 링크
디코 서버에서 스위핑 다들 하길래 나도 풀어봤다.

풀이....

그냥 개기초 스위핑

y좌표가 작은것들이 아니라 큰것들의 합을 구한다는거 주의하면 된다.

간단하게 펜윅트리로 구현하면 된다.

 

* std::find는 선형시간이더라..ㅋㅋ