레프네 약방

레프네 약방

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

레프네 약방

컨텐츠 검색

태그

대수학 조합론 Codeforces 그래프이론 함수방정식 화학 경시수학 현대대수학 IMO 수학 AOPS 물리화학 열역학 수학문풀 Russian Code Cup 물리 더블카운팅 ps-hell Problem Solving 정수론

최근글

  • 2021 Jan-Feb Problem Solving
  • ACM-ICPC 2020 Seoul Regiona⋯
  • Constructing Chain Cover of⋯
  • UCPC 2020 본선 후기

댓글

  • 안녕하세요 두 번째 관찰까진 이해했는⋯
  • 갓
  • 네~!
  • 깔끔한 풀이네요~

공지사항

아카이브

  • 2021/03
  • 2020/11
  • 2020/08
  • 2020/02

2018(54)

  • 선대 연습문제 (181212)

    2018.12.12
  • Apostol 해석적 정수론 CH3. 28~31

    2018.12.07
  • AOPS 직접 풀이 #003

    2018.12.07
  • Putnam 2017 풀이 - 풀리는 것만

    2018.11.30
  • 2018 대수경 2분야 5번 풀이

    2018.11.24
  • HilbertMO : alternative query sorting for Mo's algorithm

    2018.11.15
선대 연습문제 (181212)

문제.\(n\times n\) matrix \(A \ = \ (a_{ij})\)에 대해 \(s_{i} := \sum_{j=1}^{n} |a_{ij}|\)라 하자.\(A\)의 eigenvalue \(\lambda\)는 다음을 만족함을 보여라.$$ |\lambda| \le \max \left( s_{1}, s_{2}, \ldots s_{n} \right) $$ 화난다... Key observation. $$ \left\lVert v \right\rVert_{\infty} = \max \left( |v_{1}|, |v_{2}|, \ldots |v_{n}| \right) $$도 norm이다. \(\lambda\)는 eigenvalue니까, 대응되는 eigenvector를 \(v\)라고 하면\(\left\lVer..

2018. 12. 12. 14:50
Apostol 해석적 정수론 CH3. 28~31

이건 또 정수론 공부할 때 (2017.08.09) 열심히 쓰던 글이다. Inline math 가독성 극혐... 나중에 TeX으로 써서 따로 올려야겠다. 일단은 포스팅이 적혀 있는 것까지만. 추가 notation : $$ \gamma := \lim_{n \to \infty} \left( \sum_{k=1}^{n}\frac{1}{k} - \text{log} n \right) \text{ (Euler - Mascheroni const.) } $$ $$ \zeta(s) := \begin{cases} \sum_{k=1}^{\infty} \frac{1}{k^s} & {(s>1)} \\ \lim_{x \rightarrow \infty} {\left(\sum_{n \le x} \frac{1}{k^s} - \frac{x..

2018. 12. 7. 14:49
AOPS 직접 풀이 #003

문제 링크 원래 1년 전 (2017.12 초)에 정수론 들을 때쯤 푼 문제인데, 포스팅 도중 계산이 틀려서 보류되었다. 얼추 기워서 올리긴 하지만 여전히 틀린 부분이 있을 수 있다. \(3k+1\) 꼴의 소수 \(p\)에 대해서 함수 \(L(m)\)을 다음과 같이 정의한다:$$ L(m) \ = \ \sum_{x = 0}^{p-1} (\frac{x(x^3 + m)}{p}) $$ 다음의 문제에 답하여라. (a) \(\forall t (\neq 0), \ m , \ L(m) = L(mt^3)\)(b) \(\mathbb{Z}_{p}^{*}\)를 다음의 조건을 만족하는 크기가 \(\frac{p-1}{3}\)인 집합 \(A,B,C\)로 분할할 수 있다:$$L(m) = \begin{cases} a & (m \in A..

2018. 12. 7. 14:45
Putnam 2017 풀이 - 풀리는 것만

AoPS 링크 A1. 다음을 만족하는 최소의 집합 \(S\)에 속하지 않는 원소로는 어떤 것이 있겠는가?- \(2 \in S\).- \(n^2 \in S \implies n \in S\).- \(n \in S \implies (n+5)^2 \in S\). 답은 \(1, 5k\).나는 그냥 bound 줄여나가면서 풀었는데, 훨씬 깔끔한 풀이가 있어서 가져왔다. \(n \in S\)에 대해서 \(n + 5 \in S\)가 자명하다. 또 2가 원소면 49가 원소고, \(54^2 = 2916\)이 \(S\)의 원소다. 이는 \(5k+1\)꼴이고, 따라서 \(2916\) 이상의 \(5k+1\) 꼴은 모두 \(S\)에 포함된다.임의의 \(5 \not{|} x\)에 대해 \(x^{16} \equiv 1 \ (\mod..

2018. 11. 30. 10:12
2018 대수경 2분야 5번 풀이

문제. \(1 \cdots n\)의 순열 \(a_{1}, a_{2}, \ldots a_{n}\)과 \(b_{1}, b_{2}, \ldots b_{n}\)에 대해, 다음 행렬 \(A\)의 행렬식으로 가능한 값을 모두 구하여라. $$ A = (A_{ij}) = ((1+a_{i}b_{j})^{n-1}) $$ \(n = 2\)일 때는 행렬을 다음의 꼴로 나타낼 수 있다. $$ A = \begin{pmatrix} 1 & a_{1} \\ 1 & a_{2} \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ b_{1} & b_{2} \end{pmatrix} $$ 따라서 적당한 \(k \in \{0,1\}\)에 대해 $$ \det (A) = (-1)^{k} \det \left[ \begin..

2018. 11. 24. 01:26
HilbertMO : alternative query sorting for Mo's algorithm

원본 Codeforces 블로그 문제를 잘 푸는 사람일수록 알고리즘을 암기하기보단 끊임없이 고찰하고, 최적화하고, 예외를 효과적으로 비껴가는 방법을 연구하는 것 같다. 그런 의미에서 이 포스팅 작성자도 굉장히 존경스럽다. 세상은 넓고 갓갓은 많아..MO's algorithm 흔히 루트질로 불리는 MO's algorithm은 배열에 대한 구간 쿼리를 오프라인으로 처리하는 많은 문제를 아슬아슬한 복잡도로 해결할 수 있게 해주는 트릭이다. kesakiyo님의 친절한 introduction 끄흐수님의 깔끔한 introduction MO's algorithm으로 문제를 풀기 위해서는 다음이 성립해야 한다 : - 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s-1, e] 또는 [s, e+1]에 대한 ..

2018. 11. 15. 16:03
1 2 3 4 ··· 9
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.