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

PS 이야기

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

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2016 (2)
      • IOI2015 (3)
      • 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)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

ICPC/World Finals (4)
ACM ICPC World Finals 2018

문제 링크 B. Comma Sprinkler 길이가 최대 1,000,000인 문장들이 주어진다. 어떤 단어 앞에 콤마(,)가 오면 같은 단어 앞에 모두 콤마가 오도록 바꾸며, 어떤 단어 뒤에 콤마가 올 경우 같은 단어 뒤에 모두 콤마가 오도록 바꿔야한다. 단, 단어의 끝과 시작에서 부자연스럽게 콤마를 추가하진 않는다. 이 때, 최종 문장을 구하는 문제다. 같은 단어들을 묶어 정점으로 만든다. 그리고 정점을 단어 앞에 콤마가 오는 경우, 단어 뒤에 콤마가 오는 경우를 나타내는 두 정점으로 이원화한다. 단어 앞에 콤마가 오거나, 단어 뒤에 콤마가 오는 경우 해당하는 정점에 색칠은 한 뒤, 원래 문장에서 인접한 두 단어의 정점에는 방향성 간선을 만들어주어 Flood-Fill 한다. 그러면 시간복잡도 $O(V+..

ICPC/World Finals 2018. 5. 8. 18:07
ACM ICPC World Finals 2016

문제 링크 C. Ceiling Function $K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다. 구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다. #include using namespace std; int N, M; int A[21]; struct NODE { NODE(int val=0): val(val) { left = right = 0; } int val; NODE *left, *right; } *root[51]; bool identical(NODE *a, NODE *b) { if ((bool)a->left != (b..

ICPC/World Finals 2016. 6. 18. 00:31
ACM ICPC World Finals 2015

문제 링크 A. Amalgamated Artichokes 1부터 N까지 정수 k가 있을 때, price(k) 에 대해 최대 감소폭을 구하는 문제다. 이전까지 나온 최대 값을 저장해두고 현재 값이 최대값 보다 같거나 작다면 최대 감소폭에 차이를 갱신해주고, 현재 값이 최대값 보다 크다면 최대값을 갱신해주면 된다. 시간복잡도는 $O(N)$이다. #include using namespace std; int P, A, B, C, D, N; int main() { double mx = -2e9, ans = 0; scanf("%d%d%d%d%d%d", &P, &A, &B, &C, &D, &N); for (int i=1;i v) ans = max(ans , mx - v); else mx = v; } printf("%..

ICPC/World Finals 2015. 5. 22. 08:28
ACM ICPC World Finals 2011

문제 링크 K. Trash Removal 다각형이 주어질 때, 다각형이 쓰레기 장으로 들어가기 위한 통로의 최소 너비를 구하는 문제다. 임의의 두 점을 잡아 직선을 그렸을 때, 그 직선이 수직하게 들어간다고 가정하고 너비를 계산한다. 계산된 너비 중 최소 너비가 답이 된다. 이와 같은 알고리즘이 가능한 이유는 다각형을 덮는 볼록 껍데기를 생각했을 때 너비가 최소가 되는 경우는 볼록 껍데기의 변들 중 한 변이 통로의 변과 평행하기 때문이다. #include #include #include using namespace std; int N; int X[101], Y[101]; double w[101][101]; double dist(int a, int b, int c) { double area2 = X[a]*..

ICPC/World Finals 2015. 5. 18. 20:51
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
  • 감사합니다~
Total
253,749
Today
16
Yesterday
73
링크
TAG
  • BOI 2001
  • Knuth Optimization
  • optimization
  • Dynamic Pramming
  • BOI 2009
  • Boyer
  • Dijkstra
  • BOI
  • idea
  • Algorithm
  • Tree
  • ioi
  • Splay Tree
  • Segment tree
  • Parametric Search
  • USACO
  • IOI2014
  • HackerRank
  • dynamic programming
  • moore
  • Divide & Conquer
  • z-trening
  • IOI2011
  • vote
  • Greedy Method
  • Boyer-Moore Majority Vote Algorithm
  • TRIE
  • IOI2013
  • IOI2012
  • majority
more
«   2023/02   »
일 월 화 수 목 금 토
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
글 보관함
  • 2022/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바