본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (134)
    • 문제 (1)
    • 해법 (15)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2015 (3)
      • IOI2016 (2)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (21)
    • 잡담 (1)
  • 방명록

2021/03 (2)
Z-function

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 common prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z$ 배열을 문자열 $s$의 Z-function이라고 부른다. 예를 들어, 문자열 "aaaaa"의 경우, $z = [0, 4, 3, 2, 1]$이 되며, 문자열 "aaabaab"의 경우, $z = [0, 2, 1, 0, 2, 1, 0]$이 되고, 문자열 "abacaba"의 경우, $z = [0, 0, 1, 0, 3, 0, 1]$이 된다. Z-function을 $O(n^2)$ 시간복잡도로 naive 하게 구하면 아래와 같이 코딩할 수 있다. vector z_functio..

공부 2021. 3. 8. 18:32
Li Chao Tree (Dynamic Convex Hull Optimization)

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다. 실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다. 직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다. 더보기 #include using namespace std; #define MAXN 100005 typedef __int64_t lld; typedef __int128_t lll; i..

공부 2021. 3. 8. 10:53
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Google Code Jam 2022 Rou⋯
  • Hu-Tucker Algorithm
  • Skew Heap
  • Nexon Youth Programming⋯
최근에 달린 댓글
  • gumgood 님이랑 ㅇㅇ 님이 말⋯
  • 왜 4N개가 되는지 잘 모르겠⋯
  • 그 부분은 서브태스크2에 대⋯
  • 지금 적혀있는 것이 맞습니다.
Total
227,245
Today
106
Yesterday
92
링크
TAG
  • USACO
  • Parametric Search
  • BOI
  • moore
  • BOI 2009
  • Dynamic Pramming
  • Divide & Conquer
  • idea
  • Dijkstra
  • TRIE
  • Tree
  • Splay Tree
  • IOI2012
  • Algorithm
  • Boyer
  • BOI 2001
  • IOI2011
  • dynamic programming
  • IOI2014
  • IOI2013
  • Knuth Optimization
  • ioi
  • vote
  • z-trening
  • Boyer-Moore Majority Vote Algorithm
  • Greedy Method
  • Segment tree
  • HackerRank
  • majority
  • optimization
more
«   2021/03   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함
  • 2022/05 (3)
  • 2021/08 (1)
  • 2021/03 (2)
  • 2020/09 (7)
  • 2019/05 (2)

Blog is powered by Tistory / Designed by Tistory