생각나는 대로 적는 PS팁

작성일 | In

업보를 청산하기 위해 만들었습니다.
어 이거 웰노운인데… / 이건 당연히 아는 거 아닌가? 라는 생각이 날 때마다 추가하겠습니다.

기본적인 연산

  • a < 0, M > 0일 때 a mod M = (a % M + M) % M
  • a > 0, b > 0일 때 a/b보다 작지 않은 최소 자연수: (a-1)/b+1 = (a+b-1)/b
  • 실수 오차 핸들링: 적당히 작은 상수(ex. 1e-7)에 대해, a == b 대신 abs(a-b) < eps로 비교

유명한 접근 방식

  • 가능한 최소/최대: 파라메트릭 서치
    • 분수를 최소/최대화: 파라메트릭 서치 (for(int i=0; i<ITER; i++) go();)
  • 기댓값을 최대화: DP 혹은 파라메트릭 서치 (ex. NYPC 2019 강화)
  • 격자에서 2~3방향으로 이동 + 사이클 없음: DP (3방향이면 DP 2개 관리해서 양쪽으로)
  • 격자에서 ???의 최대/최소 개수: 이분 매칭(최소 정점 덮개, 최대 독립 집합, 최소 경로 덮개, 최대 반사슬 등)
  • 간선을 끊는 쿼리: 순서 뒤집으면 간선을 연결하는 쿼리 = Union-Find
    • 구간 분할: 순서 뒤집으면 구간 병합 = Union-Find
  • 간선 정보가 바뀌는 쿼리: 쿼리를 sqrtN or sqrtQ개씩 나눠서 처리
  • xor 최대/최소: Trie
  • 괄호 문자열: Stack / DP / Tree(Forest)
    • 수직선 상에서 두 가지 종류의 사물을 매칭 (ex. KOI 2005 소방차)
  • 정적 트리: 트리 DP / Heavy Light Decomposition / Centroid Decomposition / 트리 압축 / 트리 이진 변환
  • 모든 구간에 대한 ???의 합/최소/최대/개수: 분할 정복
    • 트리의 모든 경로에 대한 ???의 합/최소/최대/개수: Centroid Decomposition
  • 구간을 뒤집는 연산: Splay Tree

유명한 문제 / 풀어보면 좋은 문제

  • KOI 2014 금광
  • APIO 2010 Commando
  • IOI 2014 Day2 Holiday
  • WF 2017 Money for Nothing
  • BalticOI 2009 Day1 Beetle (사수아탕)
  • KOI 2016 장애물 경기
  • KOI 2014 버스 노선
  • Good Bye, BOJ 2019 최단 경로와 쿼리
  • justiceHui/Unknown-to-Wellknown 참고

최적화 팁

  • 연속된 메모리에 동일한 연산을 적용하는 경우: SIMD
  • 캐시 히트(행렬 곱 for문 순서, Sparse Table 인덱스 순서 등)
  • Mo’s Algorithm with Hilbert Curve