티스토리 뷰

공부

2018.01.23 problem solving

구사과 2018. 1. 23. 04:06

POI 2009/2010. Pilots

$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.


고려대학교 2017 경시대회. Line Friends

$N$개의 구간이 주어지고, 쿼리로 두 구간의 쌍이 주어진다. 두 구간이 겹칠 경우에 한 구간에서 다른 구간으로 이동할 수 있다. 입력으로 주어진 첫번째 구간에서, 최소한의 이동을 통해서 두번째 구간으로 이동해야 한다.


POI 2005/2006. Ploughing

개인적으로 좋아하는 문제로, 2017년 6월 국가대표 멘토 교육때 김동현 대표에게도 준 적이 있다. 다만 최근에 매우 중요한 대회에 그대로 출제되었다고 들어서 몹시 당황스럽다.

문제 내용은 간단하다. $N * M$ 직사각형 모양의 주어지고, 각 격자에 양의 정수들이 쓰여 있다. 격자의 1번째 / M번째 세로줄, 혹은 1번째 / N번째 가로줄에 적힌 수들의 합이 $k$ 이하라면, 이 가로줄 / 세로줄을 제거할 수 있다. 최소 횟수로 가로 / 세로줄을 제거하여서 격자를 없애 버리는 것이 목적이다.



'공부' 카테고리의 다른 글

RUN@KAIST 2018 겨울 3주차 연습 문제  (5) 2018.02.02
BOJ 내가 만든 문제집  (6) 2018.01.27
2018.01.23 problem solving  (4) 2018.01.23
RUN@KAIST 2018 겨울 2주차 연습 문제  (1) 2018.01.22
2018.01.20 problem solving  (0) 2018.01.20
Atcoder Regular Contest 035-057  (0) 2018.01.17
댓글
  • 프로필사진 사과팬 문제 세트가 정말 좋아요! 어떻게 이 세 문제를 모은건가요? O.O 2018.01.23 11:41
  • 프로필사진 mystika 사랑해요 쿠사가! 와와! 2018.03.22 23:23
  • 프로필사진 plast 2번째 문제에서 질문드립니다!
    마지막 스프레이즈 테이블 전단계까지는 도달을 했었는데, 아무래도 시간 안에 안풀릴것 같아서 풀이를 보려 왔는데요
    설명하는 부분에서
    'DP[i−1][∗] 를 알면 DP[i][∗]를 알 수 있다' << 이말이 DP[i][∗] = DP[i-1][DP[i-1][∗]] 이 식으로 풀어내라는게 맞는건가요?
    2018.10.13 16:11
  • 프로필사진 구사과 네. 2018.10.15 03:12 신고
댓글쓰기 폼
공지사항
Total
638,014
Today
106
Yesterday
451