Problem Solving Diary #25

랜덤한 ICPC 문제 몇 개를 뽑아 풀어보았다.

BOJ 17551. Jumbled Journey

문제를 solvable하게 만들기 위해 이상한 제한들이 덕지덕지 붙었는데,

• $i$에서 $j$로 가는 비용 $c$인 간선이 있다면, 이 간선을 통하지 않는 모든 경로의 길이가 $c$보다 크다.
• 어떤 두 정점 $x$와 $y$를 연결하는 서로 다른 경로는 최대 $1000$개이다.

따라서, 일단 $O(1000n^2)$ 짜리 (여기에 아마 로그가 붙을 수도 있는) 풀이를 생각하는 것이 가장 합리적인 것으로 보인다.

일단 몇 가지 사실을 관찰하고 가면 편리하다.

• 입력에 주어지는 행렬을 $a_{ij}$라고 하자. 또한 $i$에서 $j$로 가는 간선이 있다면 $c_{ij}$를 그 비용으로, 아니라면 $c_{ij} = -1$이라고 정의하자.
• 이때 $c_{ij} \le a_{ij}$임이 자명하게 성립한다.

먼저 주어진 그래프가 DAG이므로 위상 정렬부터 하고 시작하자. 자명히 $O(n^2)$ 시간이 걸린다. 이제 편의상 $c_{ij} \neq -1$이면 $i < j$라고 생각하자. (즉, $i < j$ 방향으로 가는 간선밖에 없다)

 

일단 여기서 생각해볼 만한 것은 인접한 번호를 가진 두 정점 사이의 간선을 찾는 것이다. 만약 $c_{i, i+1}$이 $-1$이 아니라면, 이 두 간선 사이를 연결할 방법은 $i \rightarrow i+1$ 간선밖에 존재하지 않기 때문이다. 이런 간선이 존재하는 경우 그 비용을 쉽게 알 수 있게 되는 것이다.

 

$c_{i, i+1}$을 모두 알아냈다면 이제 무엇을 할 수 있을까? $c_{i, i+2}$를 알아내면 된다. 우리는 $c_{i, i+2} \neq -1$인 경우에 $i$에서 $i+2$로 가는 경로 (그 중 $i \rightarrow i+2$ 간선을 사용하지 않는 경로)들을 전부 알아낼 수 있다. 따라서 이러한 경로의 개수와 길이 총합을 안다면, $i \rightarrow i+2$ 간선의 가중치도 알아낼 수 있다. (만약 평균 조건이 이미 만족한다면, 이 간선이 존재하지 않는 것까지 알 수 있다.)

 

이제 풀이는 명확하다. $j - i$가 작은 순으로 모든 $c_{i, j}$를 찾아 줄 것이다. 다만 이걸 그냥 한다면 $O(n^2)$개의 간선에 대해 $1000$개의 경로를 DP로 처리해야 하므로 시간 복잡도 걱정이 조금 된다. (DP의 상태 수 bound 때문에 될 수도 있긴 한데 조금 불안하다.)

 

마음 편하게 처리하는 것은 $j-i$ 값이 증가할 때마다 $DP_{cnt}[x][y]$와 $DP_{sum}[x][y]$를 따로 계산하는 것이다. 이렇게 하면 한 번 계산하는 데 $O(n^3)$이 들기 때문에 이 DP 계산이 전체 $O(n^4)$에 된다는 것을 알 수 있다. 따라서 문제를 $O(n^4)$에 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[102][102];
int in[102];
int ord[102], oc;
ll ans[102][102];
ll DPcnt[102][102], DPsum[102][102];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%lld", &arr[i][j]);
            if(arr[i][j] > 0) in[j]++;
        }
    }

    queue<int> que;
    for(int i=1; i<=n; i++){
        if(!in[i]) que.push(i);
    }
    while(!que.empty()){
        int x = que.front(); que.pop();
        ord[++oc] = x;
        for(int y=1; y<=n; y++){
            if(arr[x][y] > 0){
                in[y]--;
                if(!in[y]) que.push(y);
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ans[i][j] = -1;
        }
    }

    for(int d=1; d<n; d++){
        memset(DPcnt, 0, sizeof(DPcnt));
        memset(DPsum, 0, sizeof(DPsum));
        for(int i=1; i<=n; i++) DPcnt[i][i] = 1;
        for(int s=1; s<=n; s++){
            for(int x=s; x<=n; x++){
                for(int y=x+1; y<=n; y++){
                    if(ans[ord[x]][ord[y]] == -1) continue;
                    DPcnt[s][y] += DPcnt[s][x];
                    DPsum[s][y] += DPsum[s][x] + ans[ord[x]][ord[y]] * DPcnt[s][x];
                }
            }
        }

        for(int i=1; i+d<=n; i++){
            int j = i+d;
            int x = ord[i], y = ord[j];
            if(arr[x][y] == -1) continue;
            ll a = DPcnt[i][j], b = DPsum[i][j];
            if(a && a * arr[x][y] == b) continue;
            ans[x][y] = (a+1) * arr[x][y] - b;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) printf("%lld ", ans[i][j]);
        puts("");
    }
}

BOJ 21148. TripTik

문제가 쉽지만, 굉장히 특이하고 재밌는 것 같다.

 

문제를 요약하면 다음과 같다.

• 수직선 상에 $N$개의 점이 있다. $i$번 점의 위치는 $x_i$이고 가중치는 $i$이다.
• 화면은 중앙이 $0$이고 좌우로 $1$씩 포함하는 구간 $[-1, 1]$으로 초기화되어 있다. 이때 화면을 통해 구간에 포함되어 있는 점들을 볼 수 있다. 화면에 점이 너무 많다면 가중치가 가장 큰 $k$개의 점만 볼 수 있다.
• 다음 연산이 가능할 떄, 모든 $i$에 대해 중앙이 $x_i$가 되고 $i$번 점을 볼 수 있도록 하는 연산 횟수의 최솟값을 구해 보자.
  • 화면의 중앙을 그대로 한 채, 좌우 길이를 2배 늘린다 / 줄인다.
  • 화면에서 볼 수 있는 점 중 하나를 골라, 해당 점을 중앙으로 옮긴다. (화면 길이는 유지된다.)

핵심 아이디어는 그다지 어렵지 않다. 의미가 있는 상태는 (중앙의 위치, 화면의 길이)로 정의된다. 가능한 중앙의 위치는 원점에 $N$개의 $x_i$를 포함한 $N+1$개뿐이다. 화면의 길이 또한 $x$ 범위가 $10^8$이므로 $\log 10^8$개 정도만 중요하다. 정확히는, $\frac{1}{2} = 0.5$에서부터 $2^{27}$까지 중요하므로 29가지가 중요하다. 따라서 전체 상태의 수가 $29N$ 정도이다. 사실 이 수가 300만이기 때문에 그다지 작은 수는 아니다.

 

이제 각 상태에 대해 어떤 점들을 볼 수 있는지를 빠르게 찾는다면, 나머지 부분은 BFS를 돌려 해결 가능하기 때문에 사실상 저 부분을 어떻게 하는지만 중요하다. 이걸 처리하는 수없이 많은 방법이 있는데, 내가 사용한 방법은 set을 돌리는 것이다. 좌우 간격 $2^d$를 고정하고 왼쪽에서부터 스위핑하며 적당한 시점에 셋에 넣고 빼고를 반복하면 된다. 시간 복잡도는 $O(N \log N)$인데 상수가 굉장히 크다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int where[100002];
pair<int, int> arr[100002];
vector<int> lst[100002][29]; /// -1 ~ 27
int dist[100002][29];
bool visited[100002][29];
int ans[100002];

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i].first);
//        arr[i].first = i * (rand() % 2 ? 1 : -1);
        arr[i].second = i;
        where[i] = arr[i].first;
    }
    sort(arr, arr+n+1);

    for(int d=0; d<29; d++){
        int len = (1<<d) / 2;
//        printf("d: %d\n", d);

        int l=0, r=0;
        set<int> st;
        for(int i=0; i<=n; i++){
            int L = arr[i].first - len;
            int R = arr[i].first + len;
            while(r<=n && arr[r].first <= R){
                st.insert(arr[r++].second);
            }
            while(l<=n && arr[l].first < L){
                st.erase(arr[l++].second);
            }
            auto it = st.rbegin();
            for(int t=0; t<k && it != st.rend(); t++){
                lst[arr[i].second][d].push_back(*it);
                it = next(it);
            }
        }
    }

    queue<pair<int, int> > que;
    que.push(make_pair(0, 1));
    visited[0][1] = true;
    for(int i=1; i<=n; i++) ans[i] = INT_MAX;

    while(!que.empty()){
        pair<int, int> tmp = que.front(); que.pop();
        int x = tmp.first, d = tmp.second;
//        printf("(%d, %d): %d\n", x, d, dist[x][d]);
        if(d && !visited[x][d-1]){
            visited[x][d-1] = 1;
            dist[x][d-1] = dist[x][d] + 1;
            que.push(make_pair(x, d-1));
        }
        if(d < 28 && !visited[x][d+1]){
            visited[x][d+1] = 1;
            dist[x][d+1] = dist[x][d] + 1;
            que.push(make_pair(x, d+1));
        }
        for(int c: lst[x][d]){
            if(!visited[c][d]){
                visited[c][d] = 1;
                dist[c][d] = dist[x][d] + 1;
                que.push(make_pair(c, d));
            }
        }
    }

    for(int i=0; i<=n; i++){
        for(int d=0; d<29; d++){
            if(!visited[i][d] || !count(lst[i][d].begin(), lst[i][d].end(), i)) continue;
            ans[i] = min(ans[i], dist[i][d]);
        }
    }

    for(int i=1; i<=n; i++) printf("%d\n", ans[i] == INT_MAX ? -1 : ans[i]);
}

BOJ 7427. Triathlon

각 섹션의 길이가 $1$, $x$, $y$라고 하자. 이때 어떤 쌍 $(a_i, b_i, c_i)$가 $(a_j, b_j, c_j)$를 이길 조건을 적어 보면 다음과 같다.

$$
\frac{1}{a_i} + \frac{x}{b_i}+\frac{y}{c_i} < \frac{1}{a_j}+\frac{x}{b_j}+\frac{y}{c_j} \
\Longleftrightarrow \left(\frac{1}{b_j}-\frac{1}{b_i} \right) x + \left(\frac{1}{c_j}-\frac{1}{c_i}\right)y+\left(\frac{1}{a_j}-\frac{1}{a_i}\right) >0
$$

위 조건을 만족하는 $(x, y)$를 좌표평면에 그리면 반평면이 되고, 따라서 이 문제는 반평면 교집합 문제로 환원할 수 있다. 반평면 교집합을 $O(n \log n)$ 또는 $O(n^2)$ 정도의 시간 복잡도에 풀 수 있기 때문에, 전체 문제를 $O(n^3)$ 이하에 해결할 수 있다.

 

조금 까다로운 점은 방정식의 계수가 유리수로 주어져 있다는 점이다. 따라서 실수 오차가 발생할 확률이 매우 크다.

 

반평면 교집합 코드는 이곳에서 가져왔다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
const long double eps = 1e-9, inf = 1e9;

// Basic point/vector struct.
struct Point {
    long double x, y;
    explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}

    // Addition, substraction, multiply by constant, dot product, cross product.

    friend Point operator + (const Point& p, const Point& q) {
        return Point(p.x + q.x, p.y + q.y);
    }

    friend Point operator - (const Point& p, const Point& q) {
        return Point(p.x - q.x, p.y - q.y);
    }

    friend Point operator * (const Point& p, const long double& k) {
        return Point(p.x * k, p.y * k);
    }

    friend long double dot(const Point& p, const Point& q) {
        return p.x * q.x + p.y * q.y;
    }

    friend long double cross(const Point& p, const Point& q) {
        return p.x * q.y - p.y * q.x;
    }
};

// Basic half-plane struct.
struct Halfplane {

    // 'p' is a passing point of the line and 'pq' is the direction vector of the line.
    Point p, pq;
    long double angle;

    Halfplane() {}
    Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
        angle = atan2l(pq.y, pq.x);
    }

    // Check if point 'r' is outside this half-plane.
    // Every half-plane allows the region to the LEFT of its line.
    bool out(const Point& r) {
        return cross(pq, r - p) < -eps;
    }

    // Comparator for sorting.
    bool operator < (const Halfplane& e) const {
        return angle < e.angle;
    }

    // Intersection point of the lines of two half-planes. It is assumed they're never parallel.
    friend Point inter(const Halfplane& s, const Halfplane& t) {
        long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
        return s.p + (s.pq * alpha);
    }
};

// Actual algorithm
vector<Point> hp_intersect(vector<Halfplane>& H) {

    Point box[4] = {  // Bounding box in CCW order
        Point(inf, inf),
        Point(-inf, inf),
        Point(-inf, -inf),
        Point(inf, -inf)
    };

    for(int i = 0; i<4; i++) { // Add bounding box half-planes.
        Halfplane aux(box[i], box[(i+1) % 4]);
        H.push_back(aux);
    }

    // Sort by angle and start algorithm
    sort(H.begin(), H.end());
    deque<Halfplane> dq;
    int len = 0;
    for(int i = 0; i < int(H.size()); i++) {

        // Remove from the back of the deque while last half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
            dq.pop_back();
            --len;
        }

        // Remove from the front of the deque while first half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
            dq.pop_front();
            --len;
        }

        // Special case check: Parallel half-planes
        if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
            // Opposite parallel half-planes that ended up checked against each other.
            if (dot(H[i].pq, dq[len-1].pq) < 0.0)
                return vector<Point>();

            // Same direction half-plane: keep only the leftmost half-plane.
            if (H[i].out(dq[len-1].p)) {
                dq.pop_back();
                --len;
            }
            else continue;
        }

        // Add new half-plane
        dq.push_back(H[i]);
        ++len;
    }

    // Final cleanup: Check half-planes at the front against the back and vice-versa
    while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
        dq.pop_back();
        --len;
    }

    while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
        dq.pop_front();
        --len;
    }

    // Report empty intersection if necessary
    if (len < 3) return vector<Point>();

    // Reconstruct the convex polygon from the remaining half-planes.
    vector<Point> ret(len);
    for(int i = 0; i+1 < len; i++) {
        ret[i] = inter(dq[i], dq[i+1]);
    }
    ret.back() = inter(dq[len-1], dq[0]);
    return ret;
}

int n;
long double A[102], B[102], C[102];

int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for(int t=1; t<=n; t++){
        vector<Halfplane> vec;
        vec.push_back(Halfplane(Point(0, 0), Point(1, 0)));
        vec.push_back(Halfplane(Point(0, 1), Point(0, 0)));

        bool good = 1;
        for(int i=1; i<=n; i++){
            if(i==t) continue;
            if(A[i]>=A[t]&&B[i]>=B[t]&&C[i]>=C[t]){
                good = 0;
                break;
            }
            if(A[i]<=A[t]&&B[i]<=B[t]&&C[i]<=C[t]) continue;

            Point P, Q;
            long double a = (1/B[i] - 1/B[t]), b = (1/C[i] - 1/C[t]), c = (1/A[i] - 1/A[t]);
            if(a==0 && b==0) {} /// 이런 경우는 없다.
            else if(b>0) P = Point(-1, -(-a+c)/b), Q = Point(1, -(a+c)/b);
            else if(b<0) P = Point(1, -(a+c)/b), Q = Point(-1, -(-a+c)/b);
            else if(a>0) P = Point(-c/a, 1), Q = Point(-c/a, -1);
            else         P = Point(-c/a, -1), Q = Point(-c/a, 1);
            vec.push_back(Halfplane(P, Q));
        }

        if(good && (int)hp_intersect(vec).size() >= 3){
            puts("Yes");
        }
        else puts("No");
    }
}

BOJ 15049. K-ésimo

$|A - \sqrt B| < 1$일 때 $A + \sqrt B$의 정수 부분을 $10000$으로 나눈 나머지를 알아낼 수 있으면 되는 문제이다.

 

$(A+\sqrt{B})^N + (A-\sqrt{B})^N$ 의 합을 이용해 보자. 이 합은 무조건 정수이고, 뒷부분은 절댓값이 $1$ 이하임이 보장된다. 따라서 이 합을 빠르게 구할 수 있다면 문제를 빠르게 해결할 수 있다. 저 두 합을 $x+y\sqrt{B}$꼴로 구하는 것은 분할정복을 이용한 거듭제곱으로 할 수 있다. 여기서 $\sqrt{B}$ 항이 붙은 부분은 합이 $0$이 되어 제거되고 정수 부분만 남으므로 이 합을 쉽게 구할 수 있다. 이제 $(A-\sqrt{B})^N$의 부호에 따라서 이 값에서 적당히 $0$ 또는 $1$을 빼 주면 답을 구할 수 있게 된다.

 

시간 복잡도는 $O(\log n)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 10000;

ll a, b, n, k;

struct dat{
    ll x, y; /// x + ysqrt(b)

    dat(){}
    dat(ll x, ll y): x(x), y(y){}

    dat operator*(const dat &r)const{
        return dat((x*r.x+y*r.y*b)%MOD, (x*r.y+y*r.x)%MOD);
    }
};

dat mpow(dat x, ll y){
    if(!y) return dat(1, 0);
    if(y&1) return mpow(x, y-1) * x;
    dat tmp = mpow(x, y/2);
    return tmp * tmp;
}

int main(){
    scanf("%lld %lld %lld %lld", &a, &b, &n, &k);
    dat A = mpow(dat(a%MOD, 1), n), B = mpow(dat(a%MOD, MOD-1), n);
    ll v = (A.x + B.x) % MOD;

    if(a*a != b && (a*a > b || n%2 == 0)) v = (v+MOD-1)%MOD;
    k--;
    while(k--) v/=10;
    printf("%lld", v%10);
}

BOJ 15063. Linearville

결국 문제가 되는 부분은 여러 번 지나야 하는 가로/세로 구간들이다. 만약 가로 인덱스 차이 $\Delta x$와 세로 인덱스 차이 $\Delta y$가 같다면 하나의 가로/세로 구간을 여러 번 지날 필요 없이 지그재그로 이동하면 된다. 그렇지 않다면, 일반성을 잃지 않고 $\Delta x < \Delta y$라고 가정하자.

 

이때 세로 구간은 한 번씩만 지나도 될 것이다. 문제는 가로 구간을 여러 번 중복해 지나야 하는 부분이 있을 수 있다는 것이다. 만약 해당 가로 구간 안에 길이 $1$짜리 가로 선분이 있다면 해당 선분을 무조건 여러 번 왔다갔다하는 게 이득이다. 그렇지 않다면, 구간에서 왼쪽/오른쪽으로 가장 가까운 길이 $1$의 선분을 보고, 만약 해당 선분이 충분히 가까이 있다면 이 선분을 이용하는 게 최적이다.

 

누적합과 이분탐색 등을 이용하여 문제를 쿼리당 $O(\log N)$에 해결할 수 있다. 다만 구현이 조금 있는 편이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e8;

int n, q;
int A[100002], B[100002];
vector<int> oneA, oneB;

int main(){
    scanf("%d", &n);
    for(int i=2; i<=n; i++){
        scanf("%d", &A[i]);
        if(A[i] == 1) oneA.push_back(i);
        A[i] += A[i-1];
    }
    for(int i=2; i<=n; i++){
        scanf("%d", &B[i]);
        if(B[i] == 1) oneB.push_back(i);
        B[i] += B[i-1];
    }

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        int xl, xr, yl, yr;
        scanf("%d %d %d %d", &xl, &yl, &xr, &yr);
        if(xl>xr) swap(xl, xr);
        if(yl>yr) swap(yl, yr);

        int xdiff = A[xr] - A[xl], ydiff = B[yr] - B[yl], ans = xdiff + ydiff;
        if(xr-xl <= yr-yl){
            int need = ((yr-yl)-(xr-xl))/2;
            auto it1 = upper_bound(oneA.begin(), oneA.end(), xl);
            auto it2 = upper_bound(oneA.begin(), oneA.end(), xr);
            if(it1 != it2) ans += need * 2;
            else{
                int d1 = (it1 == oneA.begin() ? INF : xl - *prev(it1));
                int d2 = (it2 == oneA.end() ? INF : *it2 - xr - 1);
                int dist = min({need, d1, d2});
                ans += (dist * 5 + (need - dist)) * 2;
            }
        }
        else{
            int need = ((xr-xl)-(yr-yl))/2;
            auto it1 = upper_bound(oneB.begin(), oneB.end(), yl);
            auto it2 = upper_bound(oneB.begin(), oneB.end(), yr);
            if(it1 != it2) ans += need * 2;
            else{
                int d1 = (it1 == oneB.begin() ? INF : yl - *prev(it1));
                int d2 = (it2 == oneB.end() ? INF : *it2 - yr - 1);
                int dist = min({need, d1, d2});
                ans += (dist * 5 + (need - dist)) * 2;
            }
        }

        printf("%d\n", ans);
    }
}