5/23 PS일지

오늘은 팀연습을 했다. 

 

시간이 삭제된다.

 

앞의 5문제를 잡고 모두 해석하여 종이에 정리하여 두었다. 내가 잡은 5문제에서는 풀만한 것이 보이지 않았다...

팀원들은 모두 한 두문제씩 풀어서 괜히 뭐랄까 눈치가 보이고 그랬다..

 

뭐 대충 읽은 문제를 정리해두고, 팀원들이 해석해둔 문제 설명을 들었다. 그런데 팀원들이 풀고 있는 문제 말고는 딱히 풀이가 떠오르지 않았다.

 

그래서 다시 앞으로 돌아와서 문제들을 읽었다. E가 뭔가 할만해 보여서 이걸 잡았다.

 

 

boj.kr/25106 Fishing

인데, 처음엔 해석을 잘못해서 그물이 육지에 붙어있어야 한다는 것을 몰랐다. 그래서 좀 애를 먹고 있었는데, 샘터님과 예제를 보다가 뭔가 이상해서 자세히 읽어보니 육지에 붙어있어야 하더라.

그리고 특이한 점은, 쿼리에 이전 답들을 xor하여 계산해야 했다. 며칠 전에 수열과 쿼리 문제 보다가 알게된 사실인데, 이런 경우 쿼리를 온라인으로 강제하는 거라고 했다.

!

 

암튼 그렇다 치는데, N과 M이 너무 커서 2차원 배열은 만들 수 없었다. 

뭐 그리고 그물이 육지에 붙어있어야 해서 값들이 누적된다는 것을 생각했다.

그런데, 점의 개수는 N*M보다 훨 작다. 

이 정보들을 생각해봤을 때, 최근에 공부한 PST가 떠올랐다! boj.kr/11012 Egg문제처럼 구성하면 된다.

 

그런데 문제가 있었다. 각 행별로 PST를 구성한다고 해도, 그 세그트리에서 부분수열의합 중 최댓값을 찾는 법을 잘 모르겠었다.

 

여기서 샘터님께 SOS를 쳤다. 혹시 세그정보가 있을 때, 최대 부분수열의 합을 log정도 시간에 구할 수 있냐고 물어봤다. 그랬더니 있다고 하셨다. 근데, 샘터님은 푸시는 문제때문에 바빠서, 풀어주실 수 없었다. 그래서 개념만 알려주면 구현을 해보겠다고 했다. 그랬더니, 간단?하게 방법을 알려주셨다. 대충 분할정복느낌으로 구하면 되더라. 노드별로 왼쪽최댓값, 오른쪽 최댓값, 가운데 최댓값, 전체 합을 저장하고 이를 이용하여 구현해주면 된다고 설명해주셨다.

 

그래서 어차피 다른 문제 풀 것도 없고 해서 PST와 부분수열의 최댓값을 구하는 쿼리를 구현하기 시작했다. 한 30분정도 했고, 돌려봤는데 예제가 2개정도 나오고 끊겼다.

 

그 후, 팀원들과 틀린 부분을 열심히 고쳐서 30분정도를 더 썼더니 답이 옳게 나왔다.

제출했는데 바로 AC를 받았다!

너무 행복했다.

 

끝나고 solution을 보는데 내 풀이와 똑같았다.

그래서 너무 기뻤다. 이거 티어가 어느정도 되냐고 하니까 PST+금광이니까 다이아4정도 될 거라고 하셨다. 금광이라는 걸 이름만 알고 무엇인지 몰랐는데, 내가 구현한 게 금광세그(?)라고 하더라... 그래서 굉장히 행복했다. 

 

거의 혼자 힘으로 다이아를 풀어낸 것 같아서 너무 기뻤다!

#include <bits/stdc++.h>
#define endl '\n'
#define INF 9876543210
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct Node {
    Node* l, * r;
    ll L, R, M, A;
    Node() { l = r = NULL; L = 0; R = 0; M = 0; A = 0; }
};

struct lrma {
    ll l, r, m, a;
};

Node* root[300030];
vector<pll> adj[300030];
ll ans[3] = { 0,0,0 };
ll n, m, k, q, r, c, v, h, x, y;

void init(Node* node, ll s, ll e) {
    if (s == e) return;
    ll mid = (s + e) / 2;
    node->l = new Node();
    node->r = new Node();
    init(node->l, s, mid);
    init(node->r, mid + 1, e);
}

void update(Node* prv, Node* now, ll s, ll e, ll x, ll v) {
    if (s == e) {
        now->A = prv->A + v;
        now->L = max(now->A, 0LL);
        now->R = max(now->A, 0LL);
        now->M = max(now->A, 0LL);
        return;
    }
    ll mid = (s + e) / 2;
    if (x <= mid) {
        now->l = new Node();
        now->r = prv->r;
        update(prv->l, now->l, s, mid, x, v);
    }
    else {
        now->r = new Node(); 
        now->l = prv->l;
        update(prv->r, now->r, mid + 1, e, x, v);
    }
    now->A = now->l->A + now->r->A;
    now->L = max(now->l->L, now->l->A + now->r->L);
    now->R = max(now->r->R, now->r->A + now->l->R);
    now->M = max({ now->l->M,now->r->M,now->l->R + now->r->L });
}

lrma get(Node* node, ll s, ll e, ll l, ll r) {
    if (r < s || e < l) {
        lrma x;
        x.l = 0;
        x.r = 0;
        x.m = 0;
        x.a = 0;
        return x;
    }
    if (l <= s && e <= r) {
        lrma x;
        x.l = node->L;
        x.r = node->R;
        x.m = node->M;
        x.a = node->A;
        return x;
    }
    ll mid = (s + e) / 2;
    lrma left, right, ret;
    left = get(node->l, s, mid, l, r);
    right = get(node->r, mid + 1, e, l, r);
    ret.l = max(left.l, right.l + left.a);
    ret.r = max(left.r + right.a, right.r);
    ret.a = left.a + right.a;
    ret.m = max({ left.m, right.m,left.r + right.l });
    return ret;
}

void solve() {
    cin >> n >> m;
    cin >> k;
    for (ll i = 1; i <= k; i++) {
        cin >> r >> c >> v;
        adj[r].push_back({ c,v });
    }
    for (ll i = 0; i <= n; i++) root[i] = new Node();
    init(root[0], 1, m);
    vector<Node*> tmp;
    tmp.push_back(root[0]);
    for (ll i = 1; i <= n; i++) {
        if (adj[i].empty()) root[i] = root[i - 1];
        else {
            for (auto& [y,val] : adj[i]) {
                Node* now = new Node();
                update(tmp.back(), now, 1, m, y, val);
                tmp.push_back(now);
            }
            root[i] = tmp.back();
        }
    }
    cin >> q;

    lrma now;
    ll nowans;
    while (q--) {
        cin >> h >> x >> y;
        h ^= ans[0];
        x ^= ans[1];
        y ^= ans[2];
        now = get(root[h], 1, m, x, y);
        nowans = max({ now.l,now.r,now.a,now.m });
        cout << nowans << endl;
        for (ll i = 0; i < 2; i++) ans[i] = ans[i + 1];
        ans[2] = nowans;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

 

 

 

팀 연습이 끝나고 뼈해장국을 먹고 선배님들은 집에 가셨고 나는 다시 랩실로 왔다.

내가 금광세그라는 것을 구현해서 풀었다는 게 너무 신나서 오자마자 금광세그를 찾아서 한 문제 더 풀었다.

boj.kr/16993 연속합과 쿼리 금광 기본 문제인 것 같다. 연습셋때 짰던 코드를 참고하여 짰다. 

#include <bits/stdc++.h>
#define endl '\n'
#define INF 9876543210
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct Node {
    ll L, R, M, A;
};

ll n, m, i, j;
ll arr[100010];
Node tree[400040];

Node init(ll N, ll s, ll e) {
    Node ret;
    if (s == e) {
        ret.A = arr[s];
        ret.L = arr[s];
        ret.R = arr[s];
        ret.M = arr[s];
        return tree[N] = ret;
    }
    ll mid = (s + e) / 2;
    Node left = init(N * 2, s, mid);
    Node right = init(N * 2 + 1, mid + 1, e);
    ret.A = left.A + right.A;
    ret.L = max(left.L, left.A + right.L);
    ret.R = max(right.R, right.A + left.R);
    ret.M = max({ left.M,right.M,left.R + right.L });
    return tree[N] = ret;
}

Node update(ll N, ll s, ll e, ll idx, ll val) {
    Node ret;
    if (idx > e || idx < s) {
        ret.A = -INF;
        ret.L = -INF;
        ret.R = -INF;
        ret.M = -INF;
        return ret;
    }
    if (s == e) {
        ret.A += val;
        ret.L = arr[s];
        ret.R = arr[s];
        ret.M = arr[s];
        return tree[N] = ret;
    }
    ll mid = (s + e) / 2;
    Node left = update(N * 2, s, mid, idx, val);
    Node right = update(N * 2 + 1, mid + 1, e, idx, val);
    ret.A = left.A + right.A;
    ret.L = max(left.L, left.A + right.L);
    ret.R = max(right.R, right.A + left.R);
    ret.M = max({ left.M,right.M,left.R + right.L });
    return tree[N] = ret;
}

Node query(ll N, ll s, ll e, ll l, ll r) {
    Node ret;
    if (l > e || r < s) {
        ret.A = -INF;
        ret.L = -INF;
        ret.R = -INF;
        ret.M = -INF;
        return ret;
    }
    if (l <= s && e <= r) {
        return tree[N];
    }
    ll mid = (s + e) / 2;
    Node left = query(N * 2, s, mid, l, r);
    Node right = query(N * 2 + 1, mid + 1, e, l, r);
    ret.A = left.A + right.A;
    ret.L = max(left.L, left.A + right.L);
    ret.R = max(right.R, right.A + left.R);
    ret.M = max({ left.M,right.M,left.R + right.L });
    return ret;
}

void solve() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> arr[i];
    init(1, 1, n);
    cin >> m;
    while (m--) {
        cin >> i >> j;
        Node tmp = query(1, 1, n, i, j);
        cout << max({ tmp.L,tmp.R,tmp.A,tmp.M }) << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

 

 

그리곤 집에 와서 코포를 쳤다.

오늘 문제를 굉장히 잘 풀어서 기대를 많이했는데, 굉장히 못봤다...

 

요즘 코포 맨~~~~~~날 개못친다.

왜 갑자기 퍼포가 이렇게 낮게 나올까..

코포 문제를 푸는 시간을 조금 늘려야겠다.

 

블루에 가고 싶은데, 어림도 없는 것 같다. 아주 속이 상하는고만..

 

 

 

 

 

이번주는 샘선생님께서 컨벡스헐을 숙제로 내주셨다. 열심히 공부해보자.