구사과

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..

Grand Prix of Gomel Ptz Winter 2020 Gennady Korotkevich Contest 5이다. kdh랑 같이 했다. 문제들이 너무 수학적 성향이 강해 내 취향은 아니었다. B: online FFT 테크닉으로 된다는데, 그 online FFT가 그냥 분할 정복 같아서 차라리 G 말고 이걸 할까 하는 후회가 있었다. 뭐 분할 정복을 시도 안 해 본 건 아니지만.. 300iq가 웃긴 풀이를 알려줬는데, $n + k$ 개의 결과를 $2n+k$ 개의 결과로 확장하는 방법이 있다. $2n+k$ 각각의 계수는 (self-convolution) + ($[x/2, x/2+k]$ 근처에서 튀어나온 계수 몇개 제거) 정도로 구할 수 있다. 우항은 $n+k$ 개의 결과가 있으면 $O(nk)$ 에 ..