dlwocks31의 PS일기장

같이 PS하는 친구들과 주마다 P5 - P1 난이도의 문제 각 하나씩 푸는 것을 목표로 재활훈련 중이다. P5 - 초고속철도 https://www.acmicpc.net/problem/2543 2543번: 초고속철도 첫째 줄에 문제의 조건을 만족하면서 처리장치를 부착할 수 있는 경우의 수를 출력한다. 만약 경우의 수가 20,070,713 이상일 때에는 20,070,713으로 나눈 나머지를 출력한다. 또한 계산 도중 오버플 www.acmicpc.net 문제: [l, r] 구간 N개가 주어지고, 이 중에서 subset을 고를 때, 겹치는 구간 pair라면 둘 중 하나는 subset에 포함해야 하는 제한이 있다. 가능한 모든 subset의 개수를 구하는 문제. 풀이: 더보기 이미 입력된 구간의 일부만 보고 답을..

https://www.acmicpc.net/problem/20967 20967번: Uddered but not Herd A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might be different www.acmicpc.net USACO 2021 January Contest > Gold 1번으로 출제된 문제이다. 풀이 제한을 자세히..

https://www.acmicpc.net/problem/20649 20649번: Stuck in a Rut The first line of input contains $N$. Each of the next $N$ lines describes the starting location of a cow, in terms of a character that is either N (for north-facing) or E (for east-facing) and two nonnegative integers $x$ and $y$ ($0\le x\le 10^9$, $0\le www.acmicpc.net 방향이 다른 모든 cow pair에 대해서, 다른 소의 간섭이 없을 때 두 개의 소가 충돌하는지, 충돌한다면 예상 충..

https://www.acmicpc.net/source/share/412dd80e9e794587a5a0f3b851164ff7 공유 소스 보기 www.acmicpc.net KMP로 모든 string마다 suffix와 prefix가 같은 suffix/prefix의 길이를 찾을 수 있다는 생각을 했는데, 답을 빠르게 찾는데는 큰 도움이 되지 않았다. 생각이 안나서 결국에 공식풀이를 봤는데, 매우 신기한 방법이 있었다. 이 문제에서 a가 b와 이어질려면 a가 b의 prefix이면서 suffix이여야 한다. 이 때 suffix 조건을 제거해보자. prefix만 본다면 이 문제는 trie로 어렵지 않게 풀 수 있다. 각 노드마다 (이 노드에서 끝나는 string이 있다면)이 노드의 string에서 끝나는 최적의 답..

https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순서대로 1, 2, ..., N의 번호를 갖는다. 매일 밤 별들은 1, 2, ..., N의 연속한 부분 구간 [L, R]에 떨어진다. [L, R]에 별이 떨어지면, 각 점에는 순서대로 1, 2, ..., R-L+1개의 별이 떨어진다. 다시 말해, L에는 1개, L+1에는 2개 www.acmicpc.net 문제를 간단하게 말하자면, 쿼리 1: [l, r] 구간의 원소에 각각 1, 2, .....