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

PS 이야기

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

PS 이야기

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

IOI/IOI2011 (6)
[IOI2011 Day2] Parrots 문제 고찰 및 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/parrots.pdf서브태스크1 (17 점)배열에 저장되어 있는 변수가 0 또는 1이다. 따라서 값이 1인 것의 위치들을 넘겨주면 된다. 위치는 0부터 7 사이의 정수이므로 넘겨주는데 별다른 무리는 없다. 이 때 호출 회수는 최대 N이 된다.서브태스크2 (17 점)이제, 배열에 저장되어 있는 변수는 0 이상 255 이하이고, N은 16이하..

IOI/IOI2011 2013.07.24 02:54
[IOI2011 Day2] Elephants 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로..

IOI/IOI2011 2013.07.24 01:52
[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번 방으로..

IOI/IOI2011 2013.07.24 01:30
[IOI2011 Day1] Race 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/race.pdf이 문제는 분할정복기법(Divide & Conquer)로 풀 수 있다. 노드 v를 선택하고 v를 포함한 길이가 K인 경로 중 가장 짧은 경로를 찾는다. 그리고 노드 v를 제거한다. 남은 트리들에서 일련의 과정을 반복한다. 분할정복으로 풀기 위해서는 다음 두 사항을 해결해야된다.어떻게 노드 v를 포함한 가장 좋은 경로를 찾을 수 있는가?..

IOI/IOI2011 2013.07.23 05:33
[IOI2011 Day1] Garden 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf 대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다. 이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector..

IOI/IOI2011 2013.07.23 03:23
[IOI2011 Day1] Ricehub 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/ricehub.pdf이 문제를 풀기 위해서, 어떤 구간이 있을 때, 그 구간에 있는 논들의 쌀을 다 가져오기 위한 최소 비용을 계산할 수 있어야한다. 구간 (i,j)가 있다는 것은 구간에 속한 논이 X[i], X[i+1], ..., X[j]라는 것이다. 이 때, 쌀창고는 X[(i+j)/2]에 놓는 것이 비용을 최소화 할 수 있다. 따라서,..

IOI/IOI2011 2013.07.23 03:06
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • IOI 2018 Day 2 문제 및 해법
  • IOI 2018 Day 1 문제 및 해법
  • 2018년 아시아태평양 정보..
  • ACM ICPC World Finals 2018
최근에 달린 댓글
  • 명우님 잘 봤습니다. 그런데..
  • E번 풀이에서 왼쪽에 가장 작..
  • 초면에 죄송(?)합니다만, http..
  • 이거 혹시 본선 문제인가요?..
Total
123,707
Today
3
Yesterday
87
링크
TAG
  • Splay Tree
  • USACO
  • majority
  • ioi
  • BOI 2009
  • moore
  • z-trening
  • Greedy Method
  • Algorithm
  • Divide & Conquer
  • BOI 2001
  • IOI2011
  • optimization
  • Boyer
  • Dijkstra
  • Boyer-Moore Majority Vote Algorithm
  • idea
  • vote
  • IOI2014
  • TRIE
  • IOI2012
  • Parametric Search
  • IOI2013
  • HackerRank
  • BOI
  • Dynamic Pramming
  • Tree
  • Knuth Optimization
  • Segment tree
  • dynamic programming
more
«   2019/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    
글 보관함
  • 2018/09 (2)
  • 2018/05 (2)
  • 2017/11 (1)
  • 2017/08 (3)
  • 2017/07 (2)

Blog is powered by Tistory / Designed by Tistory
  • 페이스북 공유하기
  • 카카오톡 공유하기
  • 카카오스토리 공유하기
  • 트위터 공유하기