구사과

조만간 2020.05.11(?) problem solving이 올라옵니다. 그 글의 일부였는데, 좀 길어서 분리했습니다. https://www.acmicpc.net/problem/17405 Step 1 $gcd(F_i, F_j)$ 자체가 너무 커서 주어진 식 그대로는 다항 시간에도 계산을 할 수 없습니다. 하지만, $gcd(F_i, F_j) = F_{gcd(i, j)}$ 임이 잘 알려져 있기 때문에, 이 식을 쓰면 문제는 $\sum_{i = 1}^{n} \sum_{j=1}^{n} gcd(i, j)^k F_{gcd(i, j)}$ 가 됩니다. 항의 계산 결과가 gcd에만 의존함에 주목하십시오. $f(k) = 1 \le i, j \le N, gcd(i, j) = k$ 인 $i, j$ 의 수라고 하면, 위 식은..

http://www.hani.co.kr/arti/opinion/column/935716.html [세상읽기] 죽은 스탈린, 살아있는 진영론 / 조형근 사망 4개월 전인 1952년 당 대회에서의 스탈린. 이렇게 미화되지 않은 사진들은 공개되지 않았다. 러시아 국립사회정치사문서보관소. 삼인 제공 www.hani.co.kr 스탈린은 진영 테제의 창시자였다. 세상은 공존할 수 없는 적대 진영으로 나뉘어 있으며, 정치는 진영 간의 전쟁이라고 믿었다. 이상을 떠벌리는 지식인 부류를 경멸했다. 역사에 만약은 없지만 그의 미친 듯한 중공업 육성이 없었다면 소련은 나치한테 패망했을 확률이 높다. 그렇게 소련은 기적처럼 살아남았다. 진영론을 폄하할 수 없는 까닭이다. 그렇게 기적이 된 소련은 사회주의도 민주주의도 아닌 괴..

9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자. Problem. 길이 $N$ 의 배열이 있을 때, 다음 두 연산을 쿼리당 $O(\log N)$에 계산하여라. 원소 갱신: $A[x] := v$ 최대 부분합 쿼리: 부분배열을 골라, 그 안의 원소 합을 최대화하여라. 즉, $Ma..