2023.11.11. PS log

김진수·2023년 11월 11일
Union Find그리디 알고리즘세그먼트 트리펜윅트리
0

PS

목록 보기
10/19
post-custom-banner

P4 13306 트리

1시간 55분 41초
모든 정점들이 연결되지 않은 상태에서 경로를 연결한다고 생각하면 풀린다.
query에서 부모노드와 분리하는 명령어는 query를 반대 순서로 보면 연결되어 있지 않은 트리에서 하나씩 부모노드와 연결하는 것과 같다.
연결되어 있지 않은 트리에서 시작하는 이유는 N-1개의 edge를 삭제하고 나면 결국 아무것도 연결되어 있지 않기 때문이다.
만약 전부 분리하지는 않고 일부만 분리했다면 일부만 분리된 트리상태에서 query를 반대로 보면서 연결하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

const int MXN = 2e5+1;
int N, Q;
int parent[MXN], origin[MXN];
vector<ti3> query;
vector<string> ans;

int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
void merge(int a, int b) {
    a = find(a); b = find(b);
    parent[b] = a;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for(int i=1; i<=MXN; i++) parent[i] = i;

    cin >> N >> Q;
    origin[1] = 1;
    for(int i=2; i<=N; i++) {
        cin >> origin[i];
    }
    Q += N-1;
    while(Q--) {
        int x, b, c; cin >> x;
        if(x==0) cin >> b, c = origin[b];
        else cin >> b >> c;
        query.emplace_back(x,b,c);
    }
    for(auto it = query.rbegin(); it != query.rend(); it++) {
        if(get<0>(*it) == 0) merge(get<1>(*it), get<2>(*it));
        else ans.emplace_back((find(get<1>(*it)) == find(get<2>(*it)) ? "YES\n" : "NO\n"));
    }
    for(auto it = ans.rbegin(); it != ans.rend(); it++)
        cout << *it;


    return 0;
}

후기

union-find를 생각했으나 문제 조건을 해결하라면 TLE가 나오고, LCA를 생각했으나 마찬가지로 연결이 끊어졌다는 것을 자식 노드들에게 기록하려면 TLE가 난다.
한참 고민했지만 결국 풀지 못 했고 구글링 후 답안지를 보고 나니 union-find를 역으로 생각할 수도 있다는 점을 배웠다.

P4 1280 나무 심기

59분 47초
treeitree_i를 XiX_i 위치에 심을 때
treeitree_i보다 왼쪽에 있는 treejtree_j에 대한 비용은 Xi−XjX_i - X_j 이다. 이를 모든 jj들에 대해서 더하면 Xi×Cnt(j∣Xj<Xi)−Sum(Xj∣Xj<Xi)X_i \times Cnt(j | X_j < X_i) - Sum(X_j | X_j<X_i)이 된다.
treeitree_i보다 오른쪽에 있는 treejtree_j에 대한 비용은 Xj−XiX_j - X_i이다. 이를 모든 jj들에 대해서 더하면 Sum(Xj∣Xj>Xi)−Xi×Cnt(j∣Xj>Xi)Sum(X_j | X_j > X_i) - X_i \times Cnt(j | X_j > X_i)이 된다.

Sum과 Cnt를 세그먼트 트리나 펜윅트리를 이용해서 풀면 O(NlogN)O(NlogN)에 풀 수 있게 된다.
여기서 주의할 점은 모듈러 연산을 할 때, 세그먼트 트리나 펜윅트리의 값을 다 구하기 전까지 하면 안 된다는 것이다. 그 이유는 뺄셈 때문이다.
예를 들어 X×Cnt−SumX \times Cnt - Sum을 하고 Mod=5Mod = 5이라 하자. Cnt=5Cnt = 5인데 modular 연산을 해서 0이 되었다고 하고 Sum=1Sum = 1이라고 하자. 그럼 값은 X×0−1=−1X \times 0 - 1 = -1이 된다. 즉, 음수가 나오게 된다.

여기서는 SumSum이나 CntCnt를 구할 때는 long long의 범위를 넘어가지 않으므로 굳이 modular 연산을 하지 않아도 괜찮다.
그렇다면 만약 modular 연산을 해야 한다면 어떻게 할까?? 뺄셈을 할 때마다 ModMod를 더 해주고 다시 ModMod로 나눠주면 된다.
예를 들어, (..)−Sum(..) - Sum을 하고 싶다면 ((..)−Sum+Mod)((..) - Sum + Mod) % ModMod를 해준다. 단, 여기서 Sum이 Mod보다 작아야 한다.
헷갈리지 않게 SumSum을 SumSum % ModMod로 표시하는 것도 좋다.

코드 (세그먼트 트리)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define val first
#define cnt second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1e9 + 7;

class segment {
public:
    vector<pll> tree; //tree[node] := a[start ~ end] 의 합

    segment() {}
    segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, pll(0,0));
    }
    ll sum(int node, int start, int end, int left, int right) {
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node].val;
        return (sum(node * 2, start, (start + end) / 2, left, right) +
                sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
    }
    ll count(int node, int start, int end, int left, int right) {
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node].cnt;
        return count(node * 2, start, (start + end) / 2, left, right) +
               count(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
    void update(int node, int start, int end, int index) {
        if(index < start || end < index) return;
        tree[node].val += index;
        tree[node].cnt++;
        if(start != end) {
            update(node * 2, start, (start + end) / 2, index);
            update(node * 2 + 1, (start + end) / 2 + 1, end, index);
        }
    }
};

const int MXN = 2e5;
int N;
ll ans = 1;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    segment root(MXN+1);

    cin >> N;
    for(int i=0; i<N; i++) {
        ll x; cin >> x;
        ll res = ( (x*root.count(1,0,MXN,0,x) - root.sum(1,0,MXN,0,x)) + (root.sum(1,0,MXN,x,MXN) - x*root.count(1,0,MXN,x,MXN)) ) % MOD;
        root.update(1,0,MXN,x);
        if(i != 0) ans = (ans * res) % MOD;
    }
    cout << ans << '\n';


    return 0;
}

코드 (펜윅트리)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
const int MXN = 2e5;
int N;
ll ans = 1;
ll fenwick[MXN+1];
ll cnt[MXN+1];

void update(int idx, int value) {
    while(idx <= MXN) {
        fenwick[idx] += value;
        cnt[idx]++;
        idx += (idx & -idx);
    }
}
// func = 0 -> sum, func = 1 -> cnt
ll sum(int idx) {
    ll ret = 0;
    while(idx) {
        ret += fenwick[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
ll count(int idx) {
    ll ret = 0;
    while(idx) {
        ret += cnt[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(fenwick, 0, sizeof fenwick);
    memset(cnt, 0, sizeof cnt);

    cin >> N;
    for(int i=0; i<N; i++) {
        ll x; cin >> x; x++;
        ll res = ( x*count(x) - sum(x) + sum(MXN) - sum(x) - x*(count(MXN) - count(x)) ) % MOD;
        if(i != 0) ans = (ans * res) % MOD;
        update(x,x);
    }
    cout << ans << '\n';


    return 0;
}

후기

모듈러 연산을 뺄셈할때는 주의해야 한다는 점을 배웠다. 이를 항상 0보다 크게 만들어야 한다는 점을 유의해야 한다.
해당 내용을 몰라서 애꿏은 오버로딩만 신경쓰느라 삽질을 많이 했다.

P4 1422 숫자의 신

58분 15초
K개의 수에서 복원추출하여 N개를 뽑는다. 이때 모두 한 번씩 써야 하므로 N개 중 K개는 숫자 하나씩을 뽑고 나머지 N-K개는 K개중 가장 큰 수로 고르는 것이 수를 가장 크게 만들 수 있다는 것은 쉽게 알 수 있다. (숫자가 길수록 좋고, 같은 길이라면 앞자리가 클 수록 좋으므로 결국 더 큰 수가 좋은 것이 된다.)
숫자 A와 B 중 어느 것이 더 먼저 오는 것이 좋을 지. 즉 우선순위가 누가 더 먼저일지를 확인하자.
A+B > B+A라면 A가 B보다 먼저 오는 것이 좋을 것이고, A+B < B+A라면 B가 A보다 먼저 오는 것이 좋을 것이다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

const int MXN = 1e9;
int N, K;
vector<ll> v;

bool cmp(ll a, ll b) {
    string strA = to_string(a), strB = to_string(b);
    strA += strB; strB += strA;
    return strA > strB;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> K >> N;
    for(int i=0; i<K; i++) {
        ll x; cin >> x;
        v.emplace_back(x);
    }
    sort(all(v));
    while(v.size() < N) v.emplace_back(v.back());
    sort(all(v), cmp);
    for(ll x : v) cout << x;

    return 0;
}

후기

P4 난이도라고 너무 어렵게 생각했다. greedy하게 생각했으면 쉽게 풀리는 문제다.

profile
김진수
https://jinsoolve.github.io으로 블로그 이전했습니다.
이전 포스트

2023.11.10. PS log

다음 포스트

2023.11.12. PS log

post-custom-banner

0개의 댓글