본문 바로가기

UCPC3

[백준 28399] 황혼 (UCPC 2023 본선; Platinum IV) 원본 그래프 G의 복사본을 만들어 각각 G1, G2라고 이름붙여줄 수 있다. 만약 주어진 사람이 단순 경로를 처음부터 따라 이동하는 중이라면 그 사람을 G2 위로 보내고, 아니라면 G1 위로 보내자. 그러면 이것은 그냥 그래프이므로, 다익스트라를 돌리면 한 점 위에서 나머지 2n개의 정점으로 향하는 최단 경로의 길이를 구할 수 있다. 다 구한 다음에는 그래프를 다시 하나로 합쳐 주고, 정점에 부여된 가중치는 두 정점의 최솟값으로 잡으면 된다. 이 문제는 체감상 다익스트라를 돌리는 과정보다 구현이 더 까다로웠다. 예를 들면, 내가 지금 주어진 단순 경로 위에 있는지, 있다면 주어진 단순 경로의 다음 정점은 몇 번인지를 어떻게 O(1)에 구하는가? 이 문제를 해결하기 위해 vector를 2개 만든다. 첫 번.. 2023. 8. 11.
[백준 22357] 경품 추첨 (UCPC 2021 예선) (Platinum IV) https://www.acmicpc.net/problem/22357 22357번: 경품 추첨 UCPC가 작년에 이어 올해도 온라인으로 열리는 것이 아쉬웠던 청한이는 평행우주를 뒤져서 평소처럼 모두가 한 곳에 모여 대회를 치르는 세계를 찾아냈다. 청한이는 이 세계의 시상식에서 성대 www.acmicpc.net 출력할 수 있는 수의 제한이 500만 이하로 매우 작다는 것에 주목, 번호들을 최대한 구겨넣어서 생성하는 방법을 생각해 보자. 예컨대 K = 2, N = 5라면 다음과 같이 2~26까지의 수를 모두 생성하는 것이 가능하다. 1 6 11 16 21 1 2 7 12 17 22 2 3 8 13 18 23 3 4 9 14 19 24 4 5 10 15 20 25 5 6 11 16 21 26 따라서 등차수열을 .. 2022. 9. 5.
[백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V) https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다. 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다. 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다) -> 수열이 몇 .. 2022. 8. 20.

티스토리툴바