KimHwon

• 정당성
  • 세그 : 교환법칙 성립
  • 펜윅 : 교환법칙 성립, 역연산 존재 (ex. +와 -, xor과 xor)
  • 레이지 : 교환법칙 성립, 구간 update할 값을 O(1)에 계산 가능 (ex. +v : +(r-l+1)*v )
  • 스파스 : 교환법칙 성립, 겹쳐도 괜찮음 ( f(a,b,c) == f(f(a,b), f(b,c)) )

struct SegTree {
    ll seg[MAX*4];
    ll (*func)(ll a, ll b), fail;
    ll init(vector<ll> &a, int no, int nl, int nr) {
        if(nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = func(init(a,no*2,nl,mid), init(a,no*2+1,mid+1,nr));
    }
    ll query(int l, int r, int no, int nl, int nr){
        if(r < nl || nr < l) return fail;
        if(l <= nl && nr <=r) return seg[no];
        int mid = (nl + nr)/2;
        return func(query(l, r, no*2, nl, mid), query(l, r, no*2+1, mid+1, nr));
    }
    ll update(int i, ll v, int no, int nl, int nr) {
        if(i<nl || nr<i) return seg[no];
        if(nl == nr) return seg[no] = v; // += v;
        int mid = (nl + nr)/2;
        return seg[no] = func(update(i,v,no*2,nl,mid), update(i,v,no*2+1,mid+1,nr));
    }
} SEG;


// = main ========================

	SEG.func = [](ll a, ll b) {
		return (ll)(a + b);
	};
    SEG.fail = 0;

struct LazySeg {
	ll seg[MAX*4], lazy[MAX*4];
	void prop(int no, int nl, int nr) {
		if (lazy[no] != 0){
			seg[no] += (nr - nl +1)*lazy[no];	// FIX: [l,r] range apply
			if (nl != nr) {
				lazy[no*2] += lazy[no];
				lazy[no*2+1] += lazy[no];
			}
			lazy[no] = 0;
		}
	}
    ll init(vector<ll> &a, int no, int nl, int nr) {
        if (nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = init(a,no*2,nl,mid) + init(a,no*2+1,mid+1,nr);	// FIX: func
    }
	ll update(int l, int r, ll v, int no, int nl, int nr) {
		prop(no, nl, nr);
		if (r<nl || nr<l) return seg[no];
		if (l <= nl && nr <= r) {
			lazy[no] = v;	// FIX: lazy apply 
			prop(no, nl, nr);
			return seg[no];
		}
		int mid = (nl+nr)/2;
		return seg[no] = update(l,r,v,no*2,nl,mid) + update(l,r,v,no*2+1,mid+1,nr);	// FIX: func
	}
	ll query (int l, int r, int no, int nl, int nr) {
		prop(no, nl, nr);
		if (r<nl || nr<l) return 0;
		if (l <= nl && nr <= r) return seg[no];
		int mid = (nl + nr)/2;
		return query(l,r,no*2,nl,mid) + query(l,r,no*2+1,mid+1,nr);	// FIX: func
	}
} LS;

struct GoldSeg {
    static ll safe_add (const ll& a, const ll& b) {
        if (a > -LINF && b > -LINF) return a+b;
        if (a > -LINF) return a;
        if (b > -LINF) return b;
        return -LINF;
    }
    struct Node {
        ll lval = -LINF, rval = -LINF, val = -LINF, all = 0;
        Node operator+ (const Node& n) const { return {safe_add(lval,n.lval), safe_add(rval,n.rval), safe_add(val,n.val), safe_add(all,n.all)}; }
    } seg[MAX*4];
    Node func(Node a, Node b) {
        return {
                max({a.lval, safe_add(a.all,b.lval)}),
                max({safe_add(a.rval,b.all), b.rval}),
                max({a.val, b.val, safe_add(a.rval,b.lval)}),
                max({safe_add(a.all,b.all)})
        };
    }
    Node init(vector<Node> &a, int no, int nl, int nr) {
        if(nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = func(init(a,no*2,nl,mid), init(a,no*2+1,mid+1,nr));
    }
    Node query(int l, int r, int no, int nl, int nr){
        if(r < nl || nr < l) return Node();
        if(l <= nl && nr <= r) return seg[no];
        int mid = (nl + nr)/2;
        return func(query(l, r, no*2, nl, mid), query(l, r, no*2+1, mid+1, nr));
    }
    Node update(int i, Node v, int no, int nl, int nr) {
        if (i < nl || nr < i) return seg[no];
        if (nl == nr) return seg[no] = seg[no]+v; // = v
        int mid = (nl + nr) / 2;
        return seg[no] = func(update(i, v, no * 2, nl, mid), update(i, v, no * 2 + 1, mid + 1, nr));
    }
} GSEG;

vector<GoldSeg::Node> nodes;

struct RectSeg {	// 직사각형들의 넓이를 관리하는 웰논 세그 (boj.kr/3392)
    ll cnt[MAX * 4], rng[MAX * 4], diff[MAX * 4];
    ll init(vector<ll> &zip, int no, int nl, int nr) {    // 압축한 좌표를 토대로, 노드 사이 실제 차이를 계산
        if (nl == nr) return diff[no] = zip[nl] - zip[nl-1];    // 0~1 --> 1
        int mid = (nl + nr)/2;
        return diff[no] = init(zip,no*2,nl,mid) + init(zip,no*2+1,mid+1,nr);
    }
    void prop(int no, int nl, int nr) {
        if (cnt[no] > 0) rng[no] = diff[no]; // colored: return self's width
        else {  // uncolored: just merge childs
            if (nl != nr) rng[no] = rng[no*2] + rng[no*2+1];
            else rng[no] = 0;
        }
    }
    ll query(int l, int r, int no, int nl, int nr) {
        if (r < nl || nr < l) return 0ll;
        if (l <= nl && nr <= r) return rng[no];
        int mid = (nl+nr)/2;
        return query(l, r, no*2, nl, mid) + query(l, r, no*2+1, mid+1, nr);
    }
    void update(int l, int r, int v, int no, int nl, int nr) {
        if (r < nl || nr < l) return;
        if (l <= nl && nr <= r) {
            cnt[no] += v;
            prop(no, nl, nr); return;
        }
        int mid = (nl+nr)/2;
        update(l, r, v, no*2, nl, mid); update(l, r, v, no*2+1, mid+1, nr);
        prop(no, nl, nr);
    }
} RS;

// ========================
RS.init(yzip, 1, 1, N-1);
RS.query(1, N-1, 1, 1, N-1);
RS.update(r.xx+1, r.yy, (r.flag?-1:+1), 1, 1, N-1);

struct SparseTable {
    ll arr[MAX][30], lg2[MAX];  // 30=lg2(1e9), 20=lg2(1e6)
    ll (*func)(ll a, ll b);     // f(a,b,c) == f(f(a,b), f(b,c))

    void init(int n) {
        for (int j = 1; (1ull << j) < n; ++j) {
            lg2[(1ull << j)] = j;
            for (int i = 0; i + (1ull << (j-1)) < n; ++i) {
                arr[i][j] = func(arr[i][j-1], arr[i + (1ull << (j-1))][j-1]);
            }
        }
        for (int i = 0; i <= n; ++i) {
            if (!lg2[i]) lg2[i] = lg2[i-1];
        }
    }
    ll query(int l, int r) {
        ll lefts = r - (1ull << lg2[r - l + 1]) + 1;
        return func(arr[l][lg2[r - l + 1]], arr[lefts][lg2[r - l + 1]]);
    }
};

A. Strange Partition

수열과 정수 x가 주어진다. 수열의 원소들을 적절히 서로 합쳐서, 각 원소를 x로 나누고 올림한 값들의 총합이 최소가 되거나 최대가 되게 해야하는 문제.

어떤 수를 x로 나누고 올림했을 때 값이 바뀌려면 x로 나눈 나머지가 있어야 한다. 잘 생각해 보면 두 원소가 따로 있을 때는 x의 배수가 아니다가 합치면 x의 배수가 되어버릴 수 있다. 그러면 합치기 전에는 각각 올림해서 값이 증가할 텐데, 합친 뒤에는 나머지가 없기에 올림을 해도 값이 증가하지 않는다. 따라서 모든 원소를 다 합쳐버린 상태가 최소가 되는 상태이고, 전혀 합치지 않은 상태가 최대가 되는 상태이다.

B. Strange List

수열과 정수 x가 주어진다. 수열을 하나씩 순회하면서 지금 보는 원소가 x로 나누어지면, 그 몫을 x개 만큼 수열 맨 뒤에 추가한다. 만약 x로 나누어지지 않으면 끝낸다. 끝난 시점에서 수열의 총 합이 얼마인지 알아내는 문제.

일단 원소를 나눈 몫을 x개 추가하므로, 새로 추가되는 수들의 합은 원래 원소의 값과 같다. 즉, a_i/x를 x개 추가하므로 a_i/x * x = a_i 인 것이다. 새로 수열에 추가되는 연산이 최대 몇 번 있는지 생각해보면, 어떤 원소가 같은 수로 계속 나누어 떨어져야 한다. 입력되는 범위(<=10^9) 내에서 이런 경우는 2^29을 2로 나누는 경우일 것이다. 최대 29번 나누어지므로 각 원소당 29번 이내에 반복이 끝난다는 것을 알 수 있다. 따라서 그냥 주어진 수열에 끝나는 조건이 나올 때까지 x로 나눠나가다 보면 된다.

C. Strange Birthday Party

수열 k와 정렬된 수열 c가 주어진다. k의 모든 원소에 대하여 1. j<=k_i 를 만족하는 c_j 를 더하거나 2. c_{k_i}를 더할 수 있다. 단, 1번 방법에서는 c의 원소를 한 번씩만 사용할 수 있다. 합을 최소화하는 문제.

c가 정렬되어 있으므로 k_i가 클 수록 2번 방법을 선택했을 때의 페널티가 커진다. 따라서 k_i가 클 수록 가능한 1번 방법을 선택하는 것이 최적이라고 생각해 볼 수 있다. k를 내림차순으로 정렬하고, c_{k_i}의 합을 관리한다. 가장 큰 k_i부터 1번 방법으로 가장 작은 c_j를 선택해나가 보자. 적절히 합을 관리한다면 모든 경우를 확인할 수 있다.

D. Strange Definition (업솔빙)

두 수 x와 y에 대하여 lcm(x,y) / gcd(x,y) 가 완전제곱수면 '인접'했다고 정의해보자. 수열이 하나 주어지고 1초가 지날 때마다 서로 '인접'한 원소들이 서로 곱해진다. 쿼리로 시간이 주어졌을 때 각 쿼리에서 '인접'한 원소가 가장 많은 수를 알아내는 문제.

서로 '인접'한 원소들을 관리해주는 것이 키포인트이다. 어떤 원소를 소인수분해하면 a^3 * b^4 * c^5 이런 식으로 나올텐데 홀수 차수인 값만 남기고 무시해도 된다. 즉, a * c 이렇게 두 인자만 남게 된다. 왜냐하면 제곱수는 lcm(x,y) / gcd(x,y)한 후에 남아있어도 인접한 것은 자명하기 때문이다. 0초에서 1초로 넘어갈 때는 서로 곱해질 텐데, 이 경우도 마찬가지로 짝수차수가 만들어지면 무시하고 홀수 차수인 값만 남길 수 있다. 이렇게 되면 이전 상태에서 그대로 있거나 1로 바뀌게 된다. 1초에서 2초로 넘어갈 때는 이미 1초로 넘어올 때 정리가 되었기 때문에 '인접'한 관계가 변하지 않는다. 즉, 0초일 때 한번, 1초일 때 한번만 '인접'한 원소들의 수를 세어주면 된다.

딥3라 그런지 E도 꽤 풀렸는데 E번을 못 푼게 좀 아쉬웠다. 다행이 레이팅은 안떨어짐

A. Cards for Friends

w*h 크기의 카드를 n개 조각으로 자를 수 있는지 확인하는 문제. 자를 조건은 자르려는 변이 짝수여야 한다.

가능한 최대로 자르고 그 조각의 수를 n과 비교하면 된다. 최대한 자른 횟수는 변이 나누어 떨어지는 가장 큰 2^k이다. (절반씩 자르므로)

별거 아닌데 구현이 말려서 늦었다.

B. Fair Division

1g짜리 사탕과 2g짜리 사탕이 주어질 때 두 종류의 사탕을 같은 무게로 분할 할 수 있는지 알아내는 문제.

2g짜리를 먼저 최대한 공평하게 나누고, 남은 차이를 1g짜리로 채울 수 있는지 확인하면 된다.

C. Long Jumps

수열이 주어지고 임의의 위치에서 시작한다. 현재 원소의 값만큼 점수를 더하고 원소의 값 만큼 오른쪽으로 이동한다. 수열 바깥으로 나갈 때까지 반복할 때, 최대 점수를 찾는 문제.

임의의 위치 i에 대하여, 이전에 어떤 방법으로든 i에 도달할 수 있었다면 그 점수에 이어서 누적하는 것이 최적이다. 반대로 이전에 어떤 방법으로든 i에 도달 할 수 없었다면 i가 시작점이 되어야 한다. a_1부터 반복문을 돌면서 위 논리를 적용하면서 점수의 최대값을 관리해주면 된다.

D. Even-Odd Game

수열이 주어지고 두 사람이 번갈아 가며 원소를 선택하고 없앤다. 한 사람은 짝수를 선택하면 그 원소만큼 점수를 누적하고, 다른 사람은 홀수를 선택하면 그 원소만큼 점수를 누적한다. 점수를 못 받더라도 원소를 선택하고 없앨 수도 있다.

확신이 없어서 E번 보다가 그냥 냈더니 맞았다. 게임 쪽은 많이 부족한 것 같다.

직관적으로 가장 큰 원소를 고르는 것이 최적임은 당연하다. 한 사람이 할 수 있는 행동은 1. 자기가 점수를 얻도록 선택하거나 2. 상대방이 점수를 못 얻도록 선택하는 두 가지가 있다. 내가 1번 선택을 아무리 잘 했더라도 상대가 큰 점수를 얻어버리면 지게 된다. 따라서 (내가 얻는 이득)과 (상대가 얻을 이득)을 비교해서 더 큰 쪽을 선택하거나 방해하면 된다.

E. Correct Placement (업솔빙)

pair들이 주어지고, 한 pair 앞에 다른 pair가 존재할 수 있는지 확인하는 문제다. (x_i, y_i)와 (x_j, y_j)에 대하여 x_i < x_j && y_i < y_j 이거나 x_i < y_j && y_i < x_j 를 만족하면 (x_i, y_i)가 (x_j, y_j)의 앞에 존재할 수 있다. 

모든 pair들을 x좌표로 정렬을 한 뒤, 순회하면서 각 x좌표에 대한 y좌표의 prefix min 값을 구한다. 예를 들어 (1,5) (1,8) (2,3) (2,7) (4,6) 이 있다면 pmin[1]=5, pmin[2]=3, pmin[4]=3 이런 식으로 x좌표 값을 알 때 가능한 가장 작은 y값을 저장하고, 그 위치도 관리한다. x값과 y값을 바꿀 수 있으므로 (x_i, y_i)에 대하여 벡터에 (x_i, y_i)와 (y_i, x_i)를 모두 벡터에 집어 넣고 순회하면서, 이전에 정렬한 pair들에서 이분 탐색으로 x좌표에 대한 조건이 맞는 지점을 찾는다. 그리고 prefix min 값을 보고 해당 x좌표값에서 y좌표에 대한 조건도 만족이 되는지 확인을 해주면 된다.

인버스 모듈러

$ A^{-1} \equiv A^{M-2} \pmod{M} $

A^{M-2} 는 분할정복으로 nlogn 으로 구현 가능 (pow는 오버플로 주의)

이렇게 하면 이항계수도 해결 가능

$ _{n}\mathrm{C}_{r} \bmod M = \frac{ n! }{ (n-r)! \, r! } \bmod M = ( n! \bmod M ) ( (n-r)! \, r! )^{-1} \bmod M = ( n! \bmod M ) ( (n-r)! \, r! )^{M-2} \bmod M $

이항계수 코드

struct Combination {
    ll fact[MAX];
    ll safe_mul(ll a, ll b) { return ((a%MOD) * (b%MOD)) % MOD; }
    void init(int n=MAX) {
        fact[0] = 1;
        for (int i = 1; i < n; ++i) fact[i] = safe_mul(fact[i-1], i);
    }
    ll fast_pow(ll n, ll e) {
        ll ret = 1;
        while (e > 0) {
            if (e % 2) ret = safe_mul(n, ret);
            e /= 2;
            n = safe_mul(n, n);
        }
        return ret;
    }
    ll comb(ll n, ll k) {
        return safe_mul(
                fact[n],
                fast_pow(safe_mul(fact[n-k], fact[k]), MOD-2)
                );
    }
} CM;

소수 개수

1e5 이하 : 9 592

1e7 이하 : 664 579

1e9 이하 : 50 847 534

약수

개수 : O( N^{1/3} )

총합 : O( N loglog N )

O(sqN) 안에 나이브하게 구할 수 있다.

소인수분해

kimhwon.tistory.com/9

1e7 이하 소인수 갯수는 7개  (1e8 이상부터는 체 돌리는데도 3초 넘김)

struct Sieve {
    int isPrime[MAX+2];	// 소수거나 0, 1이면 -1,  합성수면 가장 작은 소인수
    void find_prime(){
        memset(isPrime, -1, sizeof(isPrime));
        int sqMAX = sqrt(MAX)+1;
        for(long long i=2; i<=sqMAX; ++i)
            if(isPrime[i] == -1)
                for(long long j=i*i; j<=MAX; j+=i)
                    if(isPrime[j] == -1)
                        isPrime[j] = i;
    }
    void print_factor(int n, vector<pii>& elem){	// 소인수 {e, k}
        elem.emplace_back(0, 0);
        while(isPrime[n] != -1){
            if (elem.back().xx == isPrime[n]) {
                ++elem.back().yy;
            } else {
                elem.emplace_back(isPrime[n], 1);
            }
            //cout << isPrime[n] << ' ';
            n /= isPrime[n];
        }
        //cout << n;
        if (elem.back().xx == n) {
            ++elem.back().yy;
        } else {
            elem.emplace_back(n, 1);
        }
        elem.erase(elem.begin());
    }
} SV;