과거 청산 챌린지 #3

이제 D4가 너무 적게 (3문제, 문제 오류 제외하면 2문제) 남은 관계로 D3도 scope에 포함시키기로 했다. 현재 D4+D3은 18문제가 남아 있다.

 

 

기술적인 문제로 인해 한 문제 (9467)는 캡처에서는 빠져 있다.

 

새로 추가된 다이아 3 문제에 대한 인상은 다음과 같다. 제목과 기억에만 의존한 내용이다.

• 누가 봐도 Matkor 컵인 문제가 하나 보인다. 얘는 좀 미뤄두는 게 정신건강에 좋을 것 같다.
• 구데기컵 문제도 하나 보이는데, 얘도 미뤄두는 게 정신건강에 좋을 것 같다.
• 마지막 문제인 레이저는 매우 최근 대회에서 시간이 부족해 디버깅을 하지 못한 문제이다. 풀이를 알기 때문에 크게 어렵지 않게 풀 수 있을 거라고 기대한다.
• 수쿼 문제 비슷한 게 보이는데, 얘도 수쿼과라면 빠르게 풀 수 있을 거라고 기대한다.

남은 문제: 65 → 60문제

BOJ 9467. 문자열 경로

문제를 봤는데 그렇게 어려워 보이지 않아서 생각해 봤고 실제로도 그리 어렵지 않았다. 두부 모판 자르기라는 문제와 별 차이 없이 풀면 된다. 원래 D3이었는데 P2를 줘서 D5로 떨어졌다.

#include <iostream>

using namespace std;

typedef long long ll;
const ll MOD = 1'000'000'009;

int n, m;
char s[20], t[20];

ll DP[100][1<<16];

inline void update(int r, int c, int mask, ll val){
    DP[r*m + c][mask] = (DP[r*m + c][mask] + val) % MOD;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> s >> t;
    if(s[0] != t[0]){
        cout << 0;
        return 0;
    }
    DP[0][3] = 1;

    int MX = (1<<(m*2)) - 1;
    for(int cell=1; cell<n*m; cell++){
        int r = cell / m, c = cell % m, d = r+c; // cell1 -> cell 전이
        for(int mask=0; mask<=MX; mask++){
            int up = (mask >> (m*2-2)) & 3, left = mask & 3;
            if(r == 0) up = 0;
            if(c == 0) left = 0;
            int us = (up >> 1) & 1, ut = up & 1;
            int ls = (left >> 1) & 1, lt = left & 1;
            ll val = DP[cell-1][mask];
            if(s[d] != t[d]){ // 하나만 가능
                if(us || ls) update(r, c, ((mask<<2) & MX) | 2, val);
                if(ut || lt) update(r, c, ((mask<<2) & MX) | 1, val);
                update(r, c, ((mask<<2) & MX), val * (26 - int(us || ls) - int(ut || lt)) % MOD);
            }
            else{ // 둘 다 가능
                if(us || ls || ut || lt){
                    update(r, c, ((mask<<2) & MX) | (us || ls ? 2 : 0) | (ut || lt ? 1 : 0), val);
                }
                update(r, c, ((mask<<2) & MX), val * (26 - int(us||ls||ut||lt)) % MOD);
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<=MX; i++) if((i & 3) == 3) ans = (ans + DP[n*m-1][i]) % MOD;
    cout << ans;
}

 

BOJ 35035. 레이저

대회 때 풀이는 찾았는데 시간이 없어서 디버깅을 못 한 문제다. 중요한 관찰은 문제의 상황을 세그먼트 트리로 관리할 수 있다는 것이다. 특정 $x$ 구간을 통과한 후 초기 $y$값 -> 나중 $y$값과 이동 거리는 slope trick 비슷한 식으로 생겼는데, 이 형태가 둘 중 하나라서 세그먼트 트리로 합쳐줄 수 있다. 이렇게 하고 나면 구현 실수 없이 각 케이스를 처리하는 문제가 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    struct Node{
        bool mode; // 0: [l, r] / 1: l
        ll l, r, p, v;
        Node(){}
        Node(bool mode, ll l, ll r): mode(mode), l(l), r(r), p(0), v(0){}
        Node(bool mode, ll l, ll p, ll v): mode(mode), l(l), r(0), p(p), v(v){}

        void print(int i=-1){
            if(i>-1) cout << "[Node " << i << "] ";
            if(!mode) cout << "[T0] l: " << l << ", r: " << r << "\n";
            else cout << "[T1] l: " << l << ", p: " << p << ", v: " << v << "\n";
        }

        inline ll pos(ll x){
            if(!mode) return max(l, min(r, x));
            else return l;
        }

        inline ll dist(ll x){
            if(!mode) return (x < l ? l-x : x > r ? x-r : 0);
            else return abs(x-p) + v;
        }

        friend Node operator+(const Node a, const Node b){
            if(a.mode == 0 && b.mode == 0){
                if(a.r <= b.l) return Node(1, b.l, a.r, b.l - a.r);
                else if(b.r <= a.l) return Node(1, b.r, a.l, a.l - b.r);
                else return Node(0, max(a.l, b.l), min(a.r, b.r));
            }
            else if(a.mode == 0 && b.mode == 1){
                if(a.l <= b.p && b.p <= a.r) return Node(1, b.l, b.p, b.v);
                else if(b.p < a.l) return Node(1, b.l, a.l, a.l-b.p + b.v);
                else return Node(1, b.l, a.r, b.p-a.r + b.v);
            }
            else if(a.mode == 1 && b.mode == 0){
                if(b.l <= a.l && a.l <= b.r) return a;
                else if(a.l < b.l) return Node(1, b.l, a.p, b.l - a.l + a.v);
                else return Node(1, b.r, a.p, a.l - b.r + a.v);
            }
            else if(a.mode == 1 && b.mode == 1){
                return Node(1, b.l, a.p, abs(a.l - b.p) + a.v + b.v);
            }
            else exit(1);
        }
    } tree[1<<20];

    void init(int i, int l, int r, ll *A, ll *B){
        if(l==r){
            tree[i] = Node(0, A[l], B[l]);
            // tree[i].print(i);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A, B);
        init(i*2+1, m+1, r, A, B);
        tree[i] = tree[i*2] + tree[i*2+1];
        // tree[i].print(i);
    }

    void update(int i, int l, int r, int x, ll a, ll b){
        if(l==r){
            tree[i] = Node(0, a, b);
            // tree[i].print(i);
            return;
        }
        int m = (l+r)>>1;
        if(x <= m) update(i*2, l, m, x, a, b);
        else update(i*2+1, m+1, r, x, a, b);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Node query(int i, int l, int r, int s, int e){
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        if(e<=m) return query(i*2, l, m, s, e);
        else if(m<s) return query(i*2+1, m+1, r, s, e);
        else return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} tree;

int n, q; ll L;
ll A[300002], B[300002];

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> L >> q;
    for(int i=1; i<=n; i++) cin >> A[i];
    for(int i=1; i<=n; i++){
        cin >> B[i];
        B[i] = L - B[i];
    }

    tree.init(1, 1, n, A, B);

    while(q--){
        int qt;
        cin >> qt;
        if(qt==1){
            ll xs, ys, xt, yt;
            cin >> xs >> ys >> xt >> yt;
            if(xs == xt) cout << abs(ys - yt) << '\n';
            else{
                if(xs > xt) swap(xs, xt), swap(ys, yt);
                xs++;
                segTree::Node p = tree.query(1, 1, n, xs, xt);
                cout << p.dist(ys) + abs(p.pos(ys) - yt) + (xt - xs + 1) << '\n';
            }
        }
        else{
            int x; ll a, b;
            cin >> x >> a >> b;
            b = L-b;
            tree.update(1, 1, n, x, a, b);
        }
    }
}

BOJ 17191. Valleys

대략적인 풀이 방식은 다음과 같다. 어떤 격자칸 집합이 non-holey region일 조건은,

• 해당 격자칸 집합이 edge-connected이고,
• 해당 격자칸 집합을 그래프로 만들었을 때, 즉 각 격자칸을 점으로, edge-인접한 격자칸들을 간선으로 이은 그래프를 생각했을 때, 모든 면은 $2 \times 2$ 격자칸에서 만들어진 사각형이어야 한다.

여기까지 생각하고 난다면 특정한 방향으로 진행하며 V와 E의 크기를 union find를 통해 관리하고, 남은 F가 예상치와 맞는지 비교하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, y, v;
    dat(){}
    dat(int x, int y, int v): x(x), y(y), v(v){}

    bool operator<(const dat r)const{
        return v<r.v;
    }
};

int n;
int A[752][752];
int B[752][752];

struct UnionFind{
    int par[600002];
    ll V[600002], E[600002], F[600002];

    void init(int n){
        for(int i=0; i<=600'000; i++) par[i] = i, V[i] = E[i] = F[i] = 0;
    }

    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x==y) return;
        par[y] = x;
        V[x] += V[y], E[x] += E[y], F[x] += F[y];
    }
} dsu;

inline int get(int x, int y){
    return (x-1)*n+(y-1);
}

const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
void addPoint(int x, int y){
    int id = get(x, y);

    // uf에 반영
    B[x][y] = 1;
    for(int d=0; d<4; d++){
        int nx = x+xx[d], ny = y+yy[d];
        if(nx<1||nx>n||ny<1||ny>n) continue;
        if(B[nx][ny]) dsu.merge(id, get(nx, ny));
    }

    // v, e, f 업데이트
    int where = dsu.find(id);
    dsu.V[where]++;

    for(int d=0; d<4; d++){
        int nx = x+xx[d], ny = y+yy[d];
        if(nx<1||nx>n||ny<1||ny>n) continue;
        if(B[nx][ny]) dsu.E[where]++;
    }

    for(int a=0; a<2; a++) for(int b=0; b<2; b++){
        int xl = x+a-1, xr = x+a;
        int yl = y+b-1, yr = y+b;
        if(xl<1||xr>n||yl<1||yr>n) continue;
        if(B[xl][yl] && B[xl][yr] && B[xr][yl] && B[xr][yr]) dsu.F[where]++;
    }
}

ll ans;

void check(int x, int y, int id){
    int idx = get(x, y);
    idx = dsu.find(idx);

    int V = dsu.V[idx], E = dsu.E[idx], F = dsu.F[idx];
    if(V - E + F == 1) ans += V;
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n;

    vector<dat> vec;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        cin >> A[i][j];
        vec.push_back({i, j, A[i][j]});
    }
    sort(vec.begin(), vec.end());

    dsu.init(n*n);
    for(int l=0; l<(int)vec.size(); l++){
        addPoint(vec[l].x, vec[l].y);
        check(vec[l].x, vec[l].y, vec[l].v);
    }

    cout << ans;
}

BOJ 8128. Subway

뭔가 그리디하게 하면 되겠다는 느낌은 있었는데 ML이 128MB라 조금 걱정이었다. 처음에 생각했던 풀이는 가장 작은 가지부터 쳐내면서 $2k$개의 리프 노드만 남기는 것이었는데, 시간 복잡도 자체는 $O(n \log n)$ 같아 보였지만 $n$도 크고 ML도 작아서 이게 될지 확신이 없었다. 그러다가 온라인에 풀이 검색을 해 보았고 풀이가 트리의 지름을 사용한 다른 방향이라는 걸 알게 되었다.

 

그래도 궁금하니 기존에 생각했던 풀이가 작동하는지 짜 보기로 했다. 구현을 생각하던 중 결국 내 그리디 알고리즘을 사용하면 트리의 지름이 남을 수밖에 없다는 사실을 깨달았다. 그렇다면 트리의 지름 하나를 아무렇게나 잡아 살려 두는 것으로 고정하고, 나머지 가지들 중에서 그리디하게 긴 쪽으로 뽑아 주는 식으로 하면 구현이 편해진다는 것을 알게 되었다.

 

이렇게 생각하니 구현이 크게 어렵지 않았다. $O(n \log n)$에 풀 수 있다. 로그 factor는 마지막 정렬 한 번에서만 사용된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
vector<int> edge[1000002];
int dist[1000002];
bool onPath[1000002];

void dfs(int x, int p=-1){
    for(int y: edge[x]){
        if(y==p) continue;
        dist[y] = dist[x] + 1;
        dfs(y, x);
    }
}

bool findPath(int x, int p, int target, vector<int> &path){
    if(x==target){
        path.push_back(x);
        return true;
    }
    path.push_back(x);
    for(int y: edge[x]){
        if(y==p) continue;
        if(findPath(y, x, target, path)) return true;
    }
    path.pop_back();
    return false;
}

vector<int> branch;

int dfs2(int x, int p=-1){
    vector<int> childs;
    for(int y: edge[x]){
        if(y==p || onPath[y]) continue;
        childs.push_back(dfs2(y, x) + 1);
    }
    if(childs.empty()) return 0;

    auto it = max_element(childs.begin(), childs.end());
    int idx = it - childs.begin();
    swap(childs[idx], childs[childs.size()-1]);
    int tmp = childs.back(); childs.pop_back();
    for(int v: childs) branch.push_back(v);
    return tmp;
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> k;
    k = min(2*k, n);
    if(!k){
        cout << 0;
        return 0;
    }

    for(int i=1; i<n; i++){
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    int leafCnt = 0;
    for(int i=1; i<=n; i++) {
        if(edge[i].size() == 1) leafCnt++;
    }

    if(leafCnt <= k){
        cout << n;
        return 0;
    }

    int remove = leafCnt - k;

    // 지름 뽑기
    dfs(1);
    int d1 = max_element(dist+1, dist+n+1) - dist;
    fill(dist+1, dist+n+1, 0);
    dfs(d1);
    int d2 = max_element(dist+1, dist+n+1) - dist;

    vector<int> path;
    findPath(d1, -1, d2, path);

    int L = (int)path.size() - 1;
    for(int x: path) onPath[x] = true;

    for(int x: path){
        int tmp = dfs2(x);
        if(tmp) branch.push_back(tmp);
    }
    sort(branch.rbegin(), branch.rend());

    int ans = n;
    while(remove--){
        ans -= branch.back();
        branch.pop_back();
    }
    cout << ans;
}

BOJ 4223. Mummy Madness

일단 parametric search를 쓰자. 시간 $s$ 동안 주인공이 살아남을 수 있는지 본다. 주인공을 중심으로 한 $(2s+1) \times (2s+1)$ 영역이 주인공이 시간 동안 도달할 수 있는 영역이다. 비슷한 방식으로 각 미라가 시간 동안 도달할 수 있는 영역도 정의된다. 이제 시간 $s$ 동안 미라들이 접근 가능한 영역이 시간 $s$ 동안 주인공이 접근 가능한 영역을 전부 덮는지를 보면 된다. 모두 덮는다면 미라들이 항상 잡을 수 있고, 모두 덮지 못한다면 주인공이 도피 가능한 루트가 항상 존재한다.

 

여기까지 왔다면 저걸 짜면 테스트 케이스당 $O(n \log n \log X)$에 문제를 해결할 수 있다. 다만 여기서 끝내면 조금 찜찜하니 증명을 시도해보기로 했다.

 

보여야 할 조건은 (직사각형이 완전히 덮인다) -> (잡을 수 있다), (직사각형이 완전히 덮이지 않는다) -> (잡을 수 없다)이다. 후자가 조금 더 쉽다. 시간 $t$에도 직사각형이 완전히 덮이지 않으면, 귀납적으로 시간 $t-1$에도 잡히지 않는 칸이 있어야 함을 알 수 있다. 이런 식으로 $t=0$까지 진행하면 어떤 루트로 도망갈 수 있는지 알 수 있다.

 

(직사각형이 완전히 덮인다) -> (잡을 수 있다)는 이런 식으로 보일 수 있다. 시간 $t$에 직사각형이 완전히 덮인다고 하자. 주인공의 최종 위치 $(x, y)$를 덮는 어떤 미라 $p$를 생각하자. 이때 미라 $p$가 시간 $t$ 후 무조건 $(x, y)$에 도착한다는 것을 보이면 된다. 핵심은 주인공이 갈 수 있는 칸의 집합이 점점 줄어든다는 것과, 미라가 $(x, y)$에 시간 $t$ 이내에 갈 수 있다는 성질이 보존된다는 것이다. 조금 생각해 본다면 주인공이 시간 $t$에 $(x, y)$에 도달했다면, 어떤 방법으로든 미라가 주인공을 향해 다가갈 때 미라가 시간 $t$에 도착할 수 있는 영역에서 $(x, y)$가 빠질 수 없다는 것을 알 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(int tc);

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    for(int tc=1; ; tc++){
        solve(tc);
    }
}

int n;
ll X[100002], Y[100002];
ll xl[100002], xr[100002], yl[100002], yr[100002];

struct segTree{
    int minV[1<<20], minC[1<<20];
    int lazy[1<<20];

    void init(int i, int l, int r){
        minV[i] = 0, minC[i] = r-l+1;
        lazy[i] = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        minV[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void merge(int i){
        minV[i] = min(minV[i*2], minV[i*2+1]);
        minC[i] = (minV[i] == minV[i*2] ? minC[i*2] : 0) + (minV[i] == minV[i*2+1] ? minC[i*2+1] : 0);
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    pair<ll, ll> query(int i, int l, int r){
        propagate(i, l, r);
        return make_pair(minV[i], minC[i]);
    }
} tree;

struct Query{
    ll y;
    int xl, xr, v;
    Query(){}
    Query(ll y, int xl, int xr, int v): y(y), xl(xl), xr(xr), v(v) {}

    bool operator<(const Query &r) const{
        return y < r.y;
    }
};

bool able(ll D){
    for(int i=1; i<=n; i++){
        if(abs(X[i]) > 2*D || abs(Y[i]) > 2*D) continue;
        xl[i] = X[i] - D, xr[i] = X[i] + D;
        yl[i] = Y[i] - D, yr[i] = Y[i] + D;
        xl[i] = max(-D, min(D, xl[i])), xr[i] = max(-D, min(D, xr[i]));
        yl[i] = max(-D, min(D, yl[i])), yr[i] = max(-D, min(D, yr[i]));
    }

    vector<ll> vx = {-D, D};
    for(int i=1; i<=n; i++){
        if(abs(X[i]) > 2*D || abs(Y[i]) > 2*D) continue;
        vx.push_back(xl[i]), vx.push_back(xr[i]);

        if(xl[i] > -D) vx.push_back(xl[i]-1);
        if(xr[i] < D) vx.push_back(xr[i]+1);
    }
    sort(vx.begin(), vx.end()); vx.erase(unique(vx.begin(), vx.end()), vx.end());

    for(int i=1; i<=n; i++){
        if(abs(X[i]) > 2*D || abs(Y[i]) > 2*D) continue;
        xl[i] = lower_bound(vx.begin(), vx.end(), xl[i]) - vx.begin() + 1;
        xr[i] = lower_bound(vx.begin(), vx.end(), xr[i]) - vx.begin() + 1;
    }

    vector<Query> vec;
    for(int i=1; i<=n; i++){
        if(abs(X[i]) > 2*D || abs(Y[i]) > 2*D) continue;
        vec.push_back(Query(yl[i], xl[i], xr[i], 1));
        vec.push_back(Query(yr[i]+1, xl[i], xr[i], -1));
    }
    sort(vec.begin(), vec.end());

    if(vec.empty()) return true;

    int k = (int)vx.size();
    assert(k <= 500'000);
    ll prvy = -D;
    tree.init(1, 1, k);
    for(Query &p: vec){
        if(prvy != p.y){
            pair<ll, ll> tmp = tree.query(1, 1, k);
            if(tmp.first == 0) return true;
            prvy = p.y;
        }
        tree.update(1, 1, k, p.xl, p.xr, p.v);
    }
    if(prvy <= D) return true;
    return false;
}

void solve(int tc){
    cin >> n;
    if(n == -1) exit(0);

    for(int i=1; i<=n; i++) cin >> X[i] >> Y[i];

    ll MIN = 0, MAX = 3e6, ANS = 0;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        if(able(MID)){
            ANS = MID;
            MIN = MID + 1;
        }
        else{
            MAX = MID - 1;
        }
    }

    cout << "Case " << tc << ": ";
    if(ANS >= 3e6) cout << "never\n";
    else cout << (ANS+1) << "\n";
}