티스토리 뷰
$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.
$N$개의 구간이 주어지고, 쿼리로 두 구간의 쌍이 주어진다. 두 구간이 겹칠 경우에 한 구간에서 다른 구간으로 이동할 수 있다. 입력으로 주어진 첫번째 구간에서, 최소한의 이동을 통해서 두번째 구간으로 이동해야 한다.
개인적으로 좋아하는 문제로, 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
- 770,796
- Today
- 430
- Yesterday
- 1,620