레프네 약방

레프네 약방

  • 분류 전체보기 (148) N
    • 알고리즘 문풀 (62)
      • AtCoder 연습 (6)
      • BOJ 연습 (27)
      • Codeforces Problemset 연습 (4)
      • Others (25)
    • 수학 이론 (39)
      • 정수론 (10)
      • 미적분학 (3)
      • 추상대수학 (11)
      • 선형대수학 (2)
      • 이산수학 (10)
      • 경시 테크닉 (3)
    • 수학 문풀 (20)
      • 경시 (내 풀이) (5)
      • 경시 (남의 풀이) (2)
      • 대입 스타일 (4)
      • 기타 (9)
    • CS 이론 (15) N
      • 자료구조 (3)
      • 알고리즘 (12) N
    • 통계학 (1)
      • 2019-1 일반통계학 (1)
    • 물리학 이론 (3)
      • 전자기학 (1)
      • 양자역학 (2)
    • 화학 이론 (3)
      • 물리화학 (3)
      • 계산화학 (0)
    • Misc. (0)
      • Computational Number Theory (0)
  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록
RSS 피드
로그인
로그아웃 글쓰기 관리

레프네 약방

컨텐츠 검색

태그

조합론 ps-hell approximation 열역학 더블카운팅 computer_algebra 화학 그래프이론 함수방정식 Codeforces 수학문풀 물리 Russian Code Cup 물리화학 경시수학 computer-algebra 정수론 수학 AOPS approx

최근글

댓글

공지사항

아카이브

분류 전체보기(148)

  • LGV lemma [WIP]

    2025.02.04
  • BOJ 21268 Do Use FFT

    2025.01.31
  • Approximation of MAX CUT

    2025.01.28
  • Bostan-Mori, Tellegen's Principle, Power series composition

    2025.01.23
  • BOI 2016 Swap

    2025.01.22
  • 2-approximation of minimum knapsack problem

    2023.12.17
LGV lemma [WIP]

Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.$G = (V, E)$에서 $2n$개의 정점 $a_{1}, \cdots, a_{n}$, $b_{1}, \cdots, b_{n}$을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple $P = (P_{1}, \cdots, P_{n})$에 대해 $P_{i}$가 $a_{i}$를 $b_{\sigma(i)}$로 보내고, $\sigma$가 순열이면 이러한 $P$를 path system이라고 하자. $P$가 non-intersecting이면 non-intersecting path system이라고 부르고, ..

2025. 2. 4. 07:31
BOJ 21268 Do Use FFT

https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principle$E_{k} = \sum_{i = 1}^{n} C_{i} \prod_{j = 1}^{k} (A_{i} + B_{j})$를 답이라고 하자.$i$와 관련한 항들을 사부작거리다보면, $P_{j} = \sum_{i = 1}^{n} C_{i}A_{i}^{j}$를 미리 계산해두면 편할 것 같다.$\sum_{j} F_{k, j}x^{j} = (x+B_1)(x+B_2)\cdots (x+B_{k})$라고 두면, $E_{k} = \sum_{j} P..

2025. 1. 31. 00:24
Approximation of MAX CUT

오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph $G = (V, E, w)$에 대해서 $S \subseteq V$를 골라서 $vE(S, V - S)$의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 $S \subseteq V$에 대해 $E(S, V-S)$의 weight 합, 즉 $\sum_{e \in E(S, V-S)} w(e)$를 $w(\partial S)$라고 표기하자. $w(\partial S)$의 가능한 최댓값, 즉 MAX CUT을 $\mat..

2025. 1. 28. 22:48
Bostan-Mori, Tellegen's Principle, Power series composition

Bostan-Mori algorithm흔히 "선형 점화식의 $N$번째 항"을 구하는 알고리즘으로 알려진 방법이다. 사실은 보다 일반적으로, $P(x)/Q(x)$ 꼴의 rational power series의 $N$차항 계수를 구하는 데 사용할 수 있다.Theorem. $\deg P 어떤 다항식 / power-series의 $N$차항 계수를 $[x^N]f(x)$로 쓴다.$\mathcal{M}(d)$는 $\mathbb{F}[x]$의 두 $d$차 다항식을 곱하는 데 걸리는 시간이다. Computer algebra에서는 sublogarithmic factor를 따지지만, PS 범위에서는 $\mathcal{M}(d) = O(d\log d)$로 생각해도 무방하다.$\mathbb{F}$는 덧셈, 뺄셈, 곱셈, 나눗셈..

2025. 1. 23. 00:47
BOI 2016 Swap

BOI 2016 Swap순열 $x_1, \cdots, x_n$ 이 주어질 때, $i = 2, \cdots, n$ 에 대해 (순서대로) $x _ {[i/2]}$와 $x _ i$ 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.풀이$x_i$의 후보는 $x_i, x_{2i}, x_{2i+1}$ 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 $i$번 자리에 들어가는 것이 당연하다.(자명한 경우) $i$번 자리에 $x_i$ 또는 $x_{2i}$가 들어가는 경우, $(2i, 2i+1)$번 자리가 각각 $(x_{2i}, x_{2i+1}), (x_{i}, x_{2i+1})$로 강제된다.(비자명한 경우) 하지만 $x_{2i+1}$이 들어가는 경우..

2025. 1. 22. 08:55
2-approximation of minimum knapsack problem

블로그를 최근에 잘 하지 않았네요. 최근에 쓴 글 간단히 업로드합니다.

2023. 12. 17. 16:17
1 2 3 4 5 ··· 25
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.