한글 문제 부터 순서대로 훑어서 가장 먼저 풀게된 문제다. 처음에 수식으로 문제를 풀려하다가 시간이 오래걸릴 것 같아, $O(N)$에 풀게되었다. 생각은 해보지 않았지만, 분명 더 빠른 방법들도 존재할 것이다. 우선 문제에서 $$ 가 주어진다.이 때 가능한 연도는 $year = k \times N + y \space (0 \le k < M)$ 이다.따라서 k를 0 부터 M-1 까지 돌려보고 $year$ 를 구한 뒤 $x \equiv year (\bmod M)$인 경우가 있으면 그 $year$를 출력하면 되고, 아니면 -1을 출력하면 된다. 자세히 적진 않았지만 modulo 연산을 통해 0이 나오면 M으로 바꿔주는 과정이 필요하다.
입력으로 주어지는 두 점 $(x1,y1)$ $(x2,y2)$를 잇는 선분이 있다.(WLOG 편의상 $x1 \le x2 , y1 \le y2$) 입력으로 주어지는 직선은 수직선이나 수평선이다.따라서 $x = a$ 꼴의 수직선이 이 선분과 교차하기 위해서는 $x1 \le a \le x2$ 이여야 한다.$y = b$ 꼴의 수평선이 이 선분과 교차하기 위해서는 $y1 \le b \le y2$ 이여야 한다. 이 관찰을 통해, 이 문제를 indexed tree로 $O(N \lg N)$ 만에 해결할 수 있다.x좌표의 트리, y좌표의 트리 두 개를 만들어야 하는데, 두 과정이 똑같으므로 x좌표의 트리에 대해서만 설명하겠다. 우선 indexed tree의 각 노드를 stack으로 잡는다.모든 선분에 대해, 선분이 차지하..
- Total
- Today
- Yesterday
- Boyer-Moore Majority Vote Algorithm
- moore
- majority
- Knuth Optimization
- idea
- ioi
- Dynamic Pramming
- IOI2011
- Boyer
- USACO
- Dijkstra
- TRIE
- BOI 2001
- IOI2013
- BOI
- Greedy Method
- dynamic programming
- Divide & Conquer
- IOI2012
- Segment tree
- Algorithm
- IOI2014
- vote
- Tree
- HackerRank
- BOI 2009
- optimization
- Splay Tree
- Parametric Search
- z-trening
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |