IOI2016 Day 1 문제 및 해법
0. 문제 패키지 1. molecules $n$개의 자연수로 이루어진 집합 $S$가 있다. 한 집합 안에 같은 수가 여러 개 있을 수 있다. 이 때, 속한 원소의 합이 $l$이상 $u$이하가 되는 부분집합을 찾는 문제다. 이 문제에서 중요한 조건은 $u-l \geq \max(S) - \min(S)$이다. 부분집합의 크기 $k$를 정했을 때, 부분집합 원소 합의 최소값을 $s_k$, 부분집합 원소 합의 최대값을 $e_k$라고 하자. $[s_k, e_k]$와 $[l, u]$가 겹치는 것과 속한 원소의 합이 $l$이상 $u$이하가 되는 크기가 $k$인 부분집합이 존재하는 것은 필요충분조건이다. 왜냐하면 $u-l \geq \max(S) - \min(S)$이기 때문이다. 이에 대한 증명은 어렵지 않다. 위와 같은..
IOI/IOI2016
2016. 8. 15. 20:47
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Tree
- ioi
- HackerRank
- IOI2014
- moore
- Segment tree
- Knuth Optimization
- Dijkstra
- vote
- Algorithm
- IOI2011
- USACO
- BOI 2001
- BOI 2009
- Greedy Method
- dynamic programming
- Divide & Conquer
- Dynamic Pramming
- IOI2013
- idea
- Boyer
- majority
- BOI
- Splay Tree
- Boyer-Moore Majority Vote Algorithm
- IOI2012
- TRIE
- z-trening
- Parametric Search
- optimization
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
글 보관함