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

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)
  • 방명록

Dijkstra (2)
[HackerRank w7] Savita And Friends

문제: HackerRank or hongjun7's blog 이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다. 우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다. 답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다. 답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다. 문제..

해법 2014. 7. 21. 21:32
[IOI2011 Day2] Crocodile 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. $$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로 이동하는 시간)이 2번째로 작은 값을 취해야한다. 이를 해결하기 위해서는 $O(N^2)$ 방법과 $O(N lg N)$ 방법이 존재한다.$O(N lg N)$ 방법은 힙(heap)을 이용해 다잌스트라(Dijkstra's Algorithm)를 돌리듯이 하면 된다.코드: http:/..

IOI/IOI2011 2013. 7. 24. 01:30
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Google Code Jam 2022 Rou⋯
  • Hu-Tucker Algorithm
  • Skew Heap
  • Nexon Youth Programming⋯
최근에 달린 댓글
  • gumgood 님이랑 ㅇㅇ 님이 말⋯
  • 왜 4N개가 되는지 잘 모르겠⋯
  • 그 부분은 서브태스크2에 대⋯
  • 지금 적혀있는 것이 맞습니다.
Total
227,239
Today
100
Yesterday
92
링크
TAG
  • TRIE
  • Knuth Optimization
  • Segment tree
  • Algorithm
  • IOI2012
  • BOI 2009
  • USACO
  • Divide & Conquer
  • moore
  • IOI2013
  • z-trening
  • vote
  • BOI 2001
  • Splay Tree
  • idea
  • IOI2011
  • Greedy Method
  • BOI
  • HackerRank
  • Dynamic Pramming
  • majority
  • Boyer
  • Parametric Search
  • Dijkstra
  • IOI2014
  • optimization
  • ioi
  • Boyer-Moore Majority Vote Algorithm
  • Tree
  • dynamic programming
more
«   2022/05   »
일 월 화 수 목 금 토
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