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

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

IOI 2017 Day 2 문제 및 해법

문제: 공식 홈페이지채점: Yandex 1. prize 1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다. 우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰 수는 등장 빈도가 과반이다. 가장 큰 수가 아닌 수의 최대 갯수는 조건에 따라 472개(1개, 4개, 21개, 446개, ...)다. 첫 번째로 가장 큰 수의 개수를 구하기 위해 최대 473번의 질문을 하여, 가장 큰 수의 위치 중 하나를 찾을 수 있다. ..

IOI/IOI2017 2017. 8. 11. 14:53
IOI 2017 Day 1 문제 및 해법

문제: 공식 홈페이지 채점: Yandex 1. nowruz 이 문제는 빈 칸과 장애물로 이루어진 직사각형 모양의 격자칸에서 빈 칸에 새로운 장애물을 적절히 넣어, 격자판의 빈 칸들을 트리 모양으로 만든다. 이 때, 만들어지는 트리에 포함된 리프 정점 수를 최대화하는 문제다. IOI 2010 Maze 문제와 비슷한 감이 있는 문제다. 문제 세팅 자체도 2차원 격자판이라는 것도 비슷하지만, 최적해가 아니라 최적근접해를 구하는 output only 문제라는 사실이 비슷하다. 이런 류의 문제는 TopCoder Marathon Match 줄여서 MM에 주로 나오는 것으로 알고 있다. 예전에 maze 문제를 해결할 때, 공부에 도움이 됐던 일루님의 글을 소개하고, 이 문제에 맞는 자세한 풀이는 추후 시간이 나면 추..

IOI/IOI2017 2017. 8. 11. 14:43
제34회 한국정보올림피아드 (KOI 2017) 중등부 풀이

1. 방 배정하기 (room) 수용인원이 A, B, C인 세 종류의 방이 있다. 이 방들을 적절히 예약하여 정확히 N명의 사람이 묵을 수 있도록 하는 문제다. N이 최대 300으로 굉장히 작기 때문에 아래 DP 배열을 정의하고 값을 채우면 된다. D[i] = 정확히 i명의 사람이 묵을 수 있도록 예약할 수 있는가 (있으면 true, 없으면 false) 점화식은 다음과 같다: D[i] = D[i-A] OR D[i-B] OR D[i-C] #include using namespace std; int A, B, C, N; bool D[350]; int main() { cin >> A >> B >> C >> N; D[0] = 1; for (int i=0;i

해법 2017. 7. 27. 23:38
이전 1 ··· 5 6 7 8 9 10 11 ··· 45 다음
이전 다음
공지사항
최근에 올라온 글
  • Google Code Jam 2022 Rou⋯
  • Hu-Tucker Algorithm
  • Skew Heap
  • Nexon Youth Programming⋯
최근에 달린 댓글
  • gumgood 님이랑 ㅇㅇ 님이 말⋯
  • 왜 4N개가 되는지 잘 모르겠⋯
  • 그 부분은 서브태스크2에 대⋯
  • 지금 적혀있는 것이 맞습니다.
Total
229,480
Today
38
Yesterday
54
링크
TAG
  • ioi
  • Divide & Conquer
  • Boyer-Moore Majority Vote Algorithm
  • TRIE
  • Knuth Optimization
  • Dijkstra
  • optimization
  • Dynamic Pramming
  • BOI
  • IOI2014
  • USACO
  • Algorithm
  • IOI2013
  • BOI 2001
  • Greedy Method
  • moore
  • Boyer
  • z-trening
  • Tree
  • HackerRank
  • IOI2011
  • Parametric Search
  • Splay Tree
  • idea
  • majority
  • BOI 2009
  • Segment tree
  • IOI2012
  • dynamic programming
  • vote
more
«   2022/06   »
일 월 화 수 목 금 토
      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    
글 보관함
  • 2022/05 (3)
  • 2021/08 (1)
  • 2021/03 (2)
  • 2020/09 (7)
  • 2019/05 (2)

Blog is powered by Tistory / Designed by Tistory