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://codeforces.com/contest/1198/standings/participant/26799422#p26799422 A - array의 distinct value한테만 비트를 배정해야 한다는 걸 못봐서 한번, 바이너리서치하는 배열을 정렬 안해서(..) 한번 틀리고 그걸 발견 못해서 B 풀고 와서 좀 더 직관적인 좌표압축? 코드를 짜서 맞았다. B - 온라인으로 풀면 레이지 세그를 써서 2번 쿼리를 레이지하게 뿌리면 된다. Div1B에겐 오버킬이였고, 정해는 오프라인으로 1번 쿼리들마다 앞으로 올 2번 쿼리의 값의 최댓값으로 바꿔쓰는 식. 너무 복잡하게 생각한 듯 하다. 나중의 2번 쿼리가 앞에 있는 어떠한 1번 쿼리든지 덮어씌울 수 있는 포텐셜이 있다! 식으로 접근하면 이런 풀이에 ..

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, .....

RTG3A로 만난 문제이다. 풀이 모든 가능한 subsequence를 다 보는 가장 간단한 브루트포스는 \(O(n\cdot 2^n)\)이다. 팀연습 중엔 여기까지밖에 생각을 못했고, 에디토리얼을 보고 내가 이해하기 편한 식으로 풀이를 한번 풀어서 써보았다. 우선 아래의 토의를 위해 \(a_i\)의 비트 개수를 \(m\)이라 하자. 즉, 이 문제에서는 \(m = 20\). 먼저 \(a_i = 0 \text{ or } 1\)인 케이스를 생각해보자. 즉 \(a\)는 bitstring of length n. 이 상황에서 bitwise and가 0이 되는 경우의 수를 찾을려면, 먼저 0인 숫자가 하나라도 subsequence에 들어가면 bitwise and는 0이 된다는 것을 생각해보자. \(a\)에 1이 \(t..

RTG3 C 로 만난 문제이다. 시도 처음 봤을 때는 n이 작으니 어떻게든 모든 가능한 트리를 다 순회해보면 되지 않을까? 하는 생각이 들었다. 모든 가능한 parent assginment를 다 시도해보면 \((n-1)^{n-1}\)이라 안되고, 트리에 dfs in/out기록을 토대로 만들 수 있는 2n짜리 bracket sequence? 같은걸 순회해볼 생각도 했다. 이건 \( n\cdot 2^{2n-2} \) 정도의 비벼볼만한 시간복잡도가 나오는데 이렇게 카운트하면 children의 순서가 바뀌면 다른 트리로 카운트된다는 것을 깨닫고 그 중복을 없애볼 생각을 하다가 너무 어려워서 포기했다. 풀이과정 우선 풀이의 첫 몇줄에서 (\(dp_{i, bm}\) = i를 루트로 하고 bm(bitmask의 약자)..