11812 K진 트리

우선 두 노드 사이의 거리를 구하기 위해서는 LCA를 구해야 하는데, 다른 문제와 달리 Segment Tree나 다른 기법을 사용하지 않고도 K진 트리의 기본 속성을 이용해 LCA를 구할 수 있다. 공식은 다음과 같다.

2월 4일에 solved.ac 문제별 경험치와 티어 구간이 많이 바뀌었습니다. 바꾼 이후로 solved.ac 티어 v. 코드포스 레이팅 계산을 다시 해 봤습니다.

티어와 레이팅의 상관관계 R² = 0.62였습니다.

• 운영진: leejseo, ryute, jhnah917, Lawali, ahgus89, ckw1140, cheetose, ho94949, rdd6584, gs11008, junseo, wookje, junie
• 모든 출제자 및 검수자, 대회 플랫폼을 지원해주신 스타트링크, 그리고 대회에 참가하고 지금 에디토리얼을 읽고 있는 당신께 감사의 말씀을 전합니다.

solved.ac 티어 v. 코드포스 레이팅에 대한 통계를 작성해봤습니다. 표본 n = 624이고, R² = 0.60으로 유의미한 상관관계가 발견되었습니다.

레이팅 최대치로 계산했을 때에는 레이팅 1500 이하 분들의 데이터에서 왜곡이 심하게 일어나, 현재 레이팅으로 계산했습니다.

이 글에서는 정수 $N$의 소인수분해를 결정적으로 (deterministic) $O(N^{1/3})$ 시간만에 할 수 있는 리먼 소인수분해 (Lehman Factorization) 기법을 소개하고, 유도합니다. 교과서에 소개된 구현은 다음과 같습니다.

// 가장 작은 소인수를 return
int lehmanFactorization(int n)
{
    // n > 21이어야 함
    if (n <= 21) return trialDivision(n);
    // n^(1/3)까지의 수로 나눔
    // cbrt는 세제곱근을 구하는 함수
    for (int i = 2; i < ceil(cbrt(n)); i++)
    {
        if (n % i == 0) return i;
    }
    // 이 글에서 주로 설명할 부분
    for (int k = 1; k <= ceil(cbrt(n)); k++)
    {
        double fourKN = 2 * sqrt(k * n)
        for (int a = ceil(fourKN); a <= floor(fourKN + cbrt(sqrt(n)) / 4 / sqrt(k)); a++)
        {
            if (isSquare(a * a - 4 * k * n)) return gcd(a + sqrt(b), n);
        }
    }
    // 이제 n은 소수
    return n;
}

$\sqrt N$보다 작거나 같은 숫자로 정수 $N$을 나누면 $O(\sqrt N)$ 시간만에 소인수분해 할 수 있는 것은 잘 알려져 있습니다. 이 방법을 trial division이라고 부릅니다.

int trialDivision(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) return i;
    }
    return n;
}

또한, $9991$과 같은 숫자는 $9991=100^2-3^2=(100-3)\times(100+3)=97\times103$인 것을 관찰하여 쉽게 소인수분해 할 수 있습니다. 이 방법을 페르마의 소인수분해 방법이라고 부릅니다.

페르마의 소인수분해 방법으로 $N=pq$ 및 $p\ge q$를 만족하는 두 수 $p$, $q$를 찾으면, $N=\left(\frac{p+q}2\right)^2-\left(\frac{p-q}2\right)^2$가 됩니다. $\frac{p+q}2$가 정수인 것이 편리하기 때문에, $p$와 $q$의 홀짝이 같으면 좋습니다. 이것은 $N$을 $2$로 나눠지지 않을 때까지 나눠서 쉽게 달성할 수 있습니다. 그리고, 이제 $p$와 $q$가 홀수이므로 $\frac{p+q}2$가 최대이려면 $q=3$, $p=N/3$이어야 하며, 이 때 $\frac{p+q}2=\frac{N+9}6$입니다.

int fermatFactorization(int n)
{
    if (n % 2 == 0) return 2;
    for (int i = sqrt(n); i <= (N + 9) / 6; i++)
    {
        if (isSquare(i * i - N)) return gcd(i + sqrt(i * i - N), N);
    }
    return n;
}

이 방법은 최악의 경우 $N/6$회 정도의 loop를 돌 수 있기 때문에, 일반적인 수의 소인수분해 방법으로는 적절하지 않습니다.

Trial division은 작은 인수를 가진 숫자를 빠르게 소인수분해 할 수 있지만, 두 인수가 서로 비슷한 숫자의 소인수분해는 느립니다. 반대로, 페르마의 소인수분해 방법은 인수가 서로 비슷한 숫자의 소인수분해가 빠르고, 작은 인수를 가진 숫자에 대해 가장 느립니다. (for 문의 순회 방향을 바꿔도 이 사실이 변하지 않습니다. 이 사실의 증명은 연습문제로 남깁니다.)

따라서, 작은 인수에 대해 나눠본 뒤 페르마의 소인수분해 방법을 적용하는 것을 생각할 수 있습니다.

int trialFermat(int n)
{
    // M은 N에 따라 바뀔 수 있는 수. 아래에 설명합니다.
    for (int i = 2; i <= M; i++)
    {
        if (n % i == 0) return i;
    }
    for (int i = sqrt(n); i <= f(M); i++)
    {
        if (isSquare(i * i - N)) return gcd(i + sqrt(i * i - N), N);
    }
    return n;
}

여기서, $f(M)$은 $N=pq$를 만족하는 $p$와 $q$에 대해 $\frac{p+q}2$의 최대값이며, $p=M$, $q=N / M$일 때를 생각하면 $f(M)=\frac{N+M^2}{2M}$입니다.

흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다.

다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다.

1. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다.
2. $A_k$를 출력한다.

$B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리는 이렇게 변합니다.

1. $B_L$에 x를 더하고, R이 마지막 인덱스가 아니면 $B_{R+1}$에서 x를 뺀다.
2. $B_1 + \cdots + B_k$를 출력한다.

안녕하세요 jaehoo1입니다.

저는 BOJ에서 문제를 풀 때, 로컬(Visual Studio 2010)로 코딩을 한 다음에, 코드를 복사해 붙여넣어 푸는데요, 틀리면 가끔 실행환경 차이를 고려하지 않고 로컬에 맞춰 코딩을 해서 틀릴때가 있습니다. 그럴 때 예전에는 ideone.com이라는 온라인 컴파일러를 사용해 차이를 알아보거나 했었습니다. 근데 ideone은 컴파일을 할 때, 입력파일을 같이 컴파일 한다는 점이 있는데, 이 입력파일의 크기가 64KB로 제한이 되어있습니다. 입력 데이터 제한이 작은 문제들은 웬만한 TC들을 만들어서 넣어볼 수 있지만, 제한이 조금만 커지면 입력데이터가 64KB를 초과하는 문제들이 간혹 있습니다(사실 자주 보입니다). 이런 문제들의 경우, ideone에서 돌려볼 수 없단 점이 많이 아쉬웠습니다. 또, 제가 붙여넣은/작성한 코드들이 저장되지도 않고, 나갔다 들어오면 다시 초기화 됩니다(물론, 링크를 저장하는 방식으로 코드를 저장할 순 있습니다). 마지막으로, 실행이 즉각적이지 않고, 메모리를 좀 쓴다는 점이 있습니다.

1000번 문제를 풀 때 사용하는 코드를 기준으로 보자면,

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d %d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}

ideone 기준으로는 0s 4452KB, BOJ 기준으로는 0ms 1116KB 가 듭니다.

안녕하세요, Ba*rkingDog입니다. 삼성 소프트웨어 멤버십 기술 블로그에 Persistent Segment Tree 튜토리얼을 올렸는데 공유를 하면 좋을 것 같아 동일한 내용을 BOJ 게시판에도 올립니다. 제 글 이외에도 도움이 될만한 글들이 많습니다. 기술 블로그를 확인해보세요.

Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. Segment Tree를 모른다면 Persistent Segment Tree를 이해할 수 없으니 여기까지 읽으신 독자 분이면 Segment Tree를 아마 알고 계실테지만 그래도 다시 한 번 짚고 넘어가겠습니다.

예전부터 주변에서 코포 레이팅이 xx면 롤에서 어느정도 되는지, 혹은 반대로 롤 xx면 코포에서 어느정도 되는지 물어보는 사람이 꽤 있었습니다.
이 글에서는 op.gg에 있는 롤 티어 통계와 여기있는 코드포스 레이팅 통계를 이용해 어떤 티어가 어떤 색깔에 대응되는지 소개합니다.

여기에서 데이터를 수집했습니다.

이 글은 우분투 환경에서 서브라임텍스트를 사용하는 방법에 관한 글입니다.
이 글은 다음 동영상을 참고하여 쓰였습니다.


윈도우 환경에서 Sublime Text를 사용하는 방법은 아래 링크에 있습니다.
https://www.acmicpc.net/blog/view/24
이 글에서는 위의 방법을 모두 안다고 가정하겠습니다.

g++ 과 서브라임이 모두 깔려있는 Ubuntu에서 빌드 설정을 다음처럼 주면 input.txt를 입력으로 받으면서 배시창으로 실행됩니다.

{
    "cmd": ["g++", "$file", "-o", "${file_path}/${file_base_name}"],
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "working_dir": "${file_path}",
    "selector": "source.c, source.c++, source.cxx, source.cpp",
    "variants": 
    [ 
        { 
            "name": "Run", 
            "shell": true,
            "cmd": ["g++ -O2 -std=c++11 \"${file}\" -o \"${file_path}/${file_base_name}.out\" && gnome-terminal -e 'bash -c \"${file_path}/${file_base_name}.out < input.txt;echo;echo; echo Press ENTER to continue; read line;exit; exec bash\"'"]
        } 
    ] 
}

p.s. 알아두면 유용한 팁
숨겨놓은 메뉴를 보려면 팔레트 ( Ctrl + Shift + P ) 에서 "vmen" ( 자동으로 "View: Toggle Menu"를 검색해줍니다. )을 치고 엔터를 누르면 됩니다. ( 윈도우즈에서는 Alt키만 누르면 됩니다. )
사이드바를 토글( 있으면 없게 없으면 있게 )하려면 Ctrl 을 누른 상태에서 K, B 를 순서대로 눌러주면 됩니다.