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

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/2012 대전 (3)
F. Pandora

문제 설명은 매우 긴 반면에 문제는 매우 간단하게 풀 수 있다. 판도라(로봇)가 가리킬 수 있는 방향은 상,하,좌,우 뿐이다. 처음 시작 방향은 중요하지 않다. 문제 입력에서 R이 세 번 이상 반복하면, X,Y 축 모두에 대해 monotone하지 않게 된다.만약 R이 두 번 반복한 경우가 있다면, 판도라의 방향에 따라 X축이나 Y축 둘 중 하나가 monotone 하지 않게 된다. 이 두 조건을 알면 문제를 해결할 수 있다.한 가지 주의해야 할 점은 입력 Sequence가 R로 시작할 경우 Sequence 끝의 R과 연결이 될 수 있다는 점이다.

ICPC/2012 대전 2013. 10. 19. 01:36
L. Square Annulus

문제에 중요한 명제가 있다. 주어진 $N$개의 점들을 모두 덮는 최소 크기의 정사각형으로, $N$개의 점을 모두 덮을 수 있는 최소 두께의 정사각형 액자를 만들 수 있다.문제 설명에 따르면 위 명제는 이미 증명된 사실이며, 이 조건 없이 문제를 해결하기는 매우 힘들다. $w \leq w'$ 일 때, 두께 $w$가 모든 점을 덮으면 두께 $w'$도 모든 점을 덮을 수 있다. 따라서 답을 binary search로 구할 수 있다. 우선, 편의상 $max_x-min_x \leq max_y-min_y$ 라 하자.그러면 액자의 바깥 정사각형의 한 변 길이 $S = max_y-min_y$ 임과 동시에 액자 위의 y좌표와 아래의 y좌표가 결정된다. 이제 두께 $w$가 답이 될 수 있는지 확인해야한다.이 때, 여러가지..

ICPC/2012 대전 2013. 10. 19. 01:18
K. Sports Reporters

문제 설명에 의해 이벤트 $E_i$와 이벤트 $E_j$가 답이 요구하는 집합에 같이 있을 수 없는 조건은,$s_i + d_i + t_{i,j} \leq s_j$ 또는 $s_j + d_j + t_{j,i} \leq s_i$문제에 있는 조건 $t_{i,j} \leq t_{i,k} + t_{k,j}$ 에 의해서, 다음과 같은 정리가 성립한다.$E_i$와 $E_j$가 같은 집합 안에 있을 수 없고, $E_j$와 $E_k$가 같은 집합 안에 있을 수 없으면, 항상 $E_i$와 $E_k$도 같은 집합 안에 있을 수 없다.위 정리가 성립하므로, 이 문제를 이분 그래프의 Minimum Cut으로 해결할 수 있다. 우선, 이분 그래프의 왼쪽과 오른쪽에 각각 $n$개의 $E_i (1 \leq i \leq n)$ 들을 배치..

ICPC/2012 대전 2013. 10. 19. 00:30
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • shortcut 만점 코드의 반례가 존재하는 것 같습니⋯
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
Total
257,047
Today
0
Yesterday
50
링크
TAG
  • Tree
  • vote
  • Knuth Optimization
  • z-trening
  • Algorithm
  • Splay Tree
  • BOI 2009
  • BOI 2001
  • BOI
  • IOI2011
  • Dijkstra
  • majority
  • moore
  • TRIE
  • optimization
  • HackerRank
  • IOI2013
  • Boyer-Moore Majority Vote Algorithm
  • Greedy Method
  • Segment tree
  • Divide & Conquer
  • USACO
  • IOI2012
  • Dynamic Pramming
  • IOI2014
  • Boyer
  • Parametric Search
  • ioi
  • idea
  • dynamic programming
more
«   2023/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/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바