0. 문제 패키지 1. paint 길이가 $n$인 문자열이 있고 각 문자는 'X'혹은 '_'이다. 연속한 'X'끼리 묶어 블록이라 부르고, 총 $k$개의 블록이 있다. 문자열의 전체가 주어지지 않고 일부만 주어진다. 그리고 블록의 개수 $k$와 왼쪽부터 순서대로 블록들의 크기가 길이 $k$인 정수배열로 주어진다. 이 때 가능한 문자열이 여러 개가 있을 수 있는데, 가능한 모든 문자열에 대해서 항상 'X'가 놓이는 위치, 그리고 항상 '_'가 놓이는 위치를 구하는 문제다. 모든 위치에 대해서 '_'를 놓을 수 있는지, 'X'를 놓을 수 있는지를 나눠서 계산하면 된다. 아래와 같은 세 개의 DP 배열을 계산해놓으면 편하다.D[i][j] = 1번 블록부터 i번 블록을 1번째 문자부터 j번째 문자까지의 부분 문..
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)$이기 때문이다. 이에 대한 증명은 어렵지 않다. 위와 같은..
- Total
- Today
- Yesterday
- Boyer
- IOI2011
- BOI
- optimization
- Boyer-Moore Majority Vote Algorithm
- dynamic programming
- z-trening
- HackerRank
- Splay Tree
- Dijkstra
- IOI2013
- TRIE
- IOI2012
- Divide & Conquer
- idea
- Greedy Method
- BOI 2001
- Algorithm
- BOI 2009
- majority
- Knuth Optimization
- Dynamic Pramming
- moore
- USACO
- IOI2014
- vote
- Parametric Search
- Segment tree
- ioi
- Tree
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |