-
Problem Solving (08.17~08.21)BOJ 2020. 8. 22. 01:03
https://www.acmicpc.net/problem/13138
13138번: Fairies' Sorcery
첫 번째 줄에는 요정의 수 N과 요정이 마법을 쓰는 횟수 M이 주어진다. (2 ≤ N, M ≤ 100,000) 두 번째 줄부터 M-1개의 줄에는 요정들의 마법이 주어진다. '2 P Q'는 P번 요정과 Q번 요정이 마법을 동시에
www.acmicpc.net
두 명의 요정이 마법을 사용하는 것은 상수시간에 처리가 가능하지만, 한명의 요정이 마법을 쓰는 것은 처리가 까다롭다. 파훼법은, 0번 요정을 임의로 추가하여 현재 있는 요정들을 0번을 기준으로 오른쪽으로 읽어온다고 가정하면 한명의 요정이 마법을 쓰는 것은 그 요정과 0번 요정의 위치를 swap하는 연산이 된다는 것이다. 이 순간에 마법을 써서 최종 배열을 만들수 있다는 것은, 마지막부터 현재까지 최종 배열에 역연산을 적용한 배열과, 현재 배열에 두개의 원소가 swap된 뒤 cylcic shift한 배열이 일치한다는 것과 동치다. 이는 각 수별로 위치의 차이를 저장하고, 그들의 최빈값과 같은 값을 관리하는 것으로 판별할 수 있다. N이 작을 때의 코너케이스를 조심하자.
https://www.acmicpc.net/problem/18605
18605번: Coins
There are n groups of coins, and the i-th group contains two coins valued as ai and bi. Now you want to pick exactly k coins out of them. However, there is a restriction: you can not pick the second coin (the one valued as bi) in the i-th group without pic
www.acmicpc.net
Need Upsolving
https://www.acmicpc.net/problem/19559
19559번: Graph
The first line contains two integers N (1 ≤ N ≤ 100 000) and M (0 ≤ M ≤ 200 000): the number of nodes and the number of edges, respectively. The nodes are numbered by consecutive integers: 1, 2, . . . , N. The next M lines describe the edges. Each
www.acmicpc.net
임의의 Spanning tree를 기준으로 값을 ax+b와 같은 꼴로 저장한 뒤 남은 간선들의 정보를 활용하여 값을 확정지으면 된다. 확정되지 않았을 시 -a/b들의 중앙값을 x로 하면 문제의 조건을 만족한다.
https://www.acmicpc.net/problem/18916
18916번: Joining Points
Print one integer: the number of suitable drawings modulo $998\,244\,353$.
www.acmicpc.net
임의의 간선을 하나 확정 지으면 선형 문제로 바뀐다. 이 점을 감안하여 DP를 해주면 됨.
https://www.acmicpc.net/problem/15742
15742번: Slingshot
Here, the first pile of manure needs to move from position 1 to position 12. Without using an slingshot, this would take 11 units of time. However, using the first slingshot, it takes 1 unit of time to move to position 0 (the slingshot source), 1 unit of t
www.acmicpc.net
Slingshot(s->e, 비용 t)을 정확히 하나 쓴다고 가정하면, a에서 b로 가는 거리는 D=abs(a-s)+abs(e-b)+t이다. a와 s, e와 b사이의 대소관계에 따라 식이 4개로 쪼개지는데, 각각의 케이스에 대해 (s, e)와 (a, b)를 plotting한 뒤 RMQ를 들고 스위핑해주면 된다.
https://www.acmicpc.net/problem/15743
15743번: New Barns
The first line contains the integer $Q$. Each of the next $Q$ lines contains a query. Each query is of the form "B p" or "Q k", respectively telling you to build a barn and connect it with barn $p$, or give the farthest distance, as defined, from barn $k$.
www.acmicpc.net
다양한 풀이가 존재하는걸로 알고 있다. 정해는 O(QlgQ)인듯 하지만 O(Q√QlgQ)로 AC를 받았다. 트리 상에 있는 임의의 점에서 가장 먼 위치에 있는 점은 트리 지름의 양 끝이다. (증명은 https://lunarhy.tistory.com/7에 간단히 적어놓았다.) 점이 추가됨에 따라 지름을 유동적으로 관리하면 풀리지만, 그러지 말고 쿼리를 루트개의 버킷으로 나누자. 버킷이 끝날때마다 dfs를 통해 트리의 지름을 확정적으로 갱신해주고, 버킷 내에서는 전 단계에서 구한 지름과, 현재 버킷상에서 추가된 정점들 사이의 거리를 모두 고려해주면 된다.
https://www.acmicpc.net/problem/15745
15745번: Snow Boots
It's winter on the farm, and that means snow! There are $N$ tiles on the path from the farmhouse to the barn, conveniently numbered $1 \dots N$, and tile $i$ is covered in $f_i$ feet of snow. In his farmhouse cellar, Farmer John has $B$ pairs of boots, num
www.acmicpc.net
정렬하고 금광세그 or 유파
https://www.acmicpc.net/problem/10596
10596번: Improvements
Son Halo owns n spaceships numbered from 1 to \(n\) and a space station. They are initially placed on one line with the space station so the spaceship \(i\) is positioned \(x_i\) meters from the station and all ships are on the same side from the station (
www.acmicpc.net
최적해에서 움직이지 않는 점들의 번호에는 단조성이 있음을 알 수 있다. -> LIS
https://www.acmicpc.net/problem/16662
16662번: Cactus Search
First, the testing system writes a line with two integers n and m (1 ≤ n ≤ 500; 0 ≤ m ≤ 500). Here n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are represented by a set of edge-distinct paths, wher
www.acmicpc.net
트리에서는 Centroid를 잡고 풀 수 있음이 알려져있지만 선인장에서는?
놀랍게도 선인장에도 (Centroid은 아니지만) 비슷한 역할을 하는 점이 존재한다. 구체적으로는, 답이 될수 있는 정점들로부터의 최단거리의 합이 최소가 되는 정점을 계속 물어보면 후보 집합의 크기가 절반 이상씩 줄어든다고 한다.
https://www.acmicpc.net/problem/9582
9582번: Dictionary
On the first line output the number of vertices in the tree m. The following m lines shall contain descriptions of tree vertices, one description per line. Vertices are indexed from 1 to n in the order of their corresponding description lines. If the corre
www.acmicpc.net
그래프 모델링을 적절히 한 뒤, Directed MST를 구해야 한다. 공부중...
https://www.acmicpc.net/problem/11591
11591번: VUDU
Young Mirko has been buying voodoo dolls lately. Considering that he is very interested in the cheapest purchase possible, he has been tracking the prices of voodoo dolls each day. His price list consists of doll prices in the last N days, where doll price
www.acmicpc.net
구간 (l, r]의 평균이 k 이상이라는 것은, sum[r]-k*r≥sum[l]-k*l이라는 것과 동치다. 인버젼 구하듯이 스위핑하면 된다.
https://www.acmicpc.net/problem/9520
9520번: NP-hard
문제 TSP는 매우 유명한 문제이다. 이 문제는 NP-hard 문제이기 때문에 효율적인 해법이 존재하지 않는다. 이번에는 약간 변형된 TSP 문제를 풀어보자. TSP문제는 도시 N개를 모두 한 번씩 방문하는 ��
www.acmicpc.net
답의 형태를 관찰해보면, 단조감소하다가 1을 찍고 단조증가하는 형태임을 확인할 수 있다. 반대로 1부터 양쪽으로 i를 붙여나간다고 생각하고 DP를 해주면 된다.
'BOJ' 카테고리의 다른 글
BOJ 18803 방역 (0) 2020.07.14 BOJ 17439 꽃집 (0) 2020.04.09