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

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

IOI/IOI2015 (3)
IOI 2015 Day 2 문제 및 해법

0. 표지 1. horses 문제: 말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다. #include using namespace std; #define MAXN 500005 #define TS 1048576 #define pb push_back #define sz..

IOI/IOI2015 2015. 7. 30. 12:05
IOI 2015 Day 1 문제 및 해법

0. 표지 1. boxes 문제: 최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 좌표와 양수 좌표를 나누어 생각할 수 있다. 결국 선형인 경우에 대해 욕심쟁이 기법으로 답을 전부 구해놓은 뒤, 모든 지점에 대해 끊어 선형으로 바꾼 뒤 답을 계산하면 된다. 선형일 때 주의해야할 점은 K개의 지점에 선물을 나누어주고 다시 0번 지점으로 돌아가는 경로는 원형에서 이루어지는게 ..

IOI/IOI2015 2015. 7. 28. 12:23
IOI2015 개막 . 연습 세션 문제 설명

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다. 이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다. 출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다. 원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다. 관련 자료들은 여기에서 다운받을 수 있다. 1. search 문제: 정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다. #include "graderlib.h" int find(int sub, int N, int X) { int s = 0, e = N-1, t; whil..

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

티스토리툴바