레프네 약방

레프네 약방

  • 분류 전체보기 (136)
    • 알고리즘 문풀 (59)
      • AtCoder 연습 (6)
      • BOJ 연습 (24)
      • Codeforces Problemset 연습 (4)
      • Others (25)
    • 수학 이론 (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 피드
로그인
로그아웃 글쓰기 관리

레프네 약방

컨텐츠 검색

태그

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

최근글

  • 제 3회 IDTCup 개최 후기
  • 2021 Jan-Feb Problem Solving
  • ACM-ICPC 2020 Seoul Regional 후⋯
  • Constructing Chain Cover of Fi⋯

댓글

  • 넵 Union by size/rank를 하지 않고 Path compres⋯
  • 3가지 풀이 정리해주신 글 잘 봤습니다! 감사합니다. 그런데 “부모 노드⋯
  • 안녕하세요 두 번째 관찰까진 이해했는데 그 이후는 아직 이해하기 어렵네요⋯
  • 갓

공지사항

아카이브

  • 2021/05
  • 2021/03
  • 2020/11
  • 2020/08

분류 전체보기(136)

  • 제 3회 IDTCup 개최 후기

    2021.05.10
  • 2021 Jan-Feb Problem Solving

    2021.03.04
  • ACM-ICPC 2020 Seoul Regional 후기

    2020.11.15
  • Constructing Chain Cover of Finite POSET

    2020.08.10
  • UCPC 2020 본선 후기

    2020.08.01
  • BOJ 10129 작은 새

    2020.02.10
제 3회 IDTCup 개최 후기

어제 끝난 제 3회 IDTCup의 후기이다. 무려 21명이 운영진이었고, 참가자는 20명에 불과한 대회였지만 그래도 준비 과정을 적어본다. 부족한 운영 능력에도 불구하고 열심히 검수/참가해주신 분들에게 감사를 표한다. Special thanks to jhhope1. 넋두리 대회에 대한 구상이 구체적으로 나온 건 12월 전후인 것 같다. 이때는 그래도 ICPC를 다시 나가고 싶다는 생각이 있었고. 올해 휴학을 할지 말지 정해진 부분이 없었기 때문에 PS에 대한 관심이 별로 식지 않았던 때였다. 그 사이에 이렇게 급격하게 PS에 무관심해질 줄은 몰랐다. 그래서인지 막판에는 즐겁다기보단 일로 느껴져서 부담되는 부분도 있었다. 출제자들 모두 PS에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내..

2021. 5. 10. 00:20
2021 Jan-Feb Problem Solving

글 쓰는 법을 까먹을 것 같으니, 몇 개 되지 않는 문제들을 줏어담아보자. BOJ 20556. 둥둥섬 다리 재정비하기 20556번: 둥둥섬 다리 재정비하기 첫 줄에 섬의 수 $N$과 쿼리의 수 $Q$가 주어진다. $(1 \leq N,Q \leq 300\,000)$ 이후 $N-1$개의 줄에 걸쳐 다리들이 연결하는 두 섬 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$ 이후 $Q$개의 줄 www.acmicpc.net 루트가 \(r\)로 고정되어 있다고 할 때, \(a\)개의 다리를 재정비해서 얻을 수 있는 최적의 결과는 가장 큰 \(a\)개 서브트리의 크기 합이라는 사실을 간단하게 알 수 있다. 따라서 "가장 큰 \(k\)개의 합"이 지원되는 자료구조에 서브트리들의 크기..

2021. 3. 4. 06:31
ACM-ICPC 2020 Seoul Regional 후기

ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다. 굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고... 대회 준비 팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, ..

2020. 11. 15. 00:36
Constructing Chain Cover of Finite POSET

최근 jo_on님을 통해 알게 된 내용을 정리해 보았다. Theorem (Dilworth). Finite POSET \(P\)에 대해, \(P\)의 minimum chain cover의 크기는 \(P\)의 maximum antichain의 크기와 같다. 이 글에서는 Dilworth's theorem의 constructive pf를 목표로 한다. POSET과 Mirsky's theorem에 대해서는 전에 대충 써놓은 글이 있다. 1. Non-constructive proof \(\newcommand{\abs}[1]{| #1 |}\)가장 잘 알려져 있는 증명법이기도 하다. Construction과는 그다지 관계가 없으니 관심없다면 스킵해도 될 듯. \(P\)의 크기에 대해 귀납법을 사용하자. \(P\)의 m..

2020. 8. 10. 22:58
UCPC 2020 본선 후기

고3 때를 포함해서 3번째 UCPC. ICPC멤버 그대로 (imeimi2000, jhhope1, TAMREF) 완전탐색 원툴 16등 도전합니다팀으로 참가했다. 최종 성적은 10 / 12 solve 5등으로, 역대 UCPC 중에서는 제일 좋은 성적이 나왔다. 팀연습이라고는 UCPC 예선밖에 없었는데 결과는 별로 나쁘지 않았다 ㅋㅋ 기억나는대로 타임라인을 재구성해본다. 약한 스포일러가 있으니 주의. 초반 (0~1시간) 내가 앞, 이멘이 중간, 즈홒이 뒤를 맡았다. A에 후원사 로고가 붙어있는 걸 발견했지만 뭔가 "제일 쉬운 문제"로 불릴 정도는 아닌 것 같아서 B랑 C를 보고 있었다. 한창 복잡한 지문을 읽고 있는데 스코어보드에 초록색 A들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 ..

2020. 8. 1. 20:25
BOJ 10129 작은 새

https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는 www.acmicpc.net 더보기 가장 먼저 드는 생각은 \(dp[i]\)를 "\(i\)번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식..

2020. 2. 10. 04:45
1 2 3 4 ··· 23
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.