PS 이야기

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z$ 배열을 문자열 $s$의 Z-function이라고 부른다. 예를 들어, 문자열 "aaaaa"의 경우, $z = [0, 4, 3, 2, 1]$이 되며, 문자열 "aaabaab"의 경우, $z = [0, 2, 1, 0, 2, 1, 0]$이 되고, 문자열 "abacaba"의 경우, $z = [0, 0, 1, 0, 3, 0, 1]$이 된다. Z-function을 $O(n^2)$ 시간복잡도로 naive 하게 구하면 아래와 같이 코딩할 수 있다. vector z_function(const..

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다. 실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다. 직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다. 더보기 #include using namespace std; #define MAXN 100005 typedef __int64_t lld; typedef __int128_t lll; i..

문제 및 채점: oj.uz 번호가 0부터 $N-1$까지 매겨진 버섯 $N$ 개가 있다. 버섯은 두 종류로 구분할 수 있는데 눈으로 구분하기 힘들다. 기계를 사용하여 임의의 버섯들을 선택하여 순서를 정해 일렬로 기계에 넣을 수 있다. 기계에 넣으면 인접한 버섯 중에 종류가 다른 경우가 몇 개인지 확인하여 알려준다. 기계를 잘 사용하여 버섯 0과 같은 종류의 버섯 수가 몇 개인지 구하는 문제다. 10점 풀이 1 이상 $N-1$ 이하인 $i$에 대해 기계에 $[0, i]$ 순서로 버섯을 넣어 버섯 $i$가 버섯 0과 같은 종류인지 확인할 수 있다. 이때, 기계 사용을 최대 $19999$번 하게 된다. 더보기 #include #include "mushrooms.h" using namespace std; int ..

문제 및 채점: oj.uz $K$ 개 종류의 비스킷이 있고, 각 종류는 번호가 1부터 $K$까지 매겨져 있다. $i$번 종류의 비스킷의 맛 점수는 $2^{i-1}$이며, $i$번 종류의 비스킷은 $a[i]$ 개 있다. 비스킷 일부를 선택하여 비스킷 바구니 $x$ 개에 나눠 담을 건데, 각 비스킷 바구니에 담긴 비스킷 맛 점수의 합을 동일하게 해야 한다. 이렇게 나눌 때 만들 수 있는 바구니에 담긴 비스킷 맛 점수의 합의 수를 구하는 문제다. 다음과 같은 DP 배열을 정의하자. $$D[i] = \text{1번부터 }i\text{번 비스킷까지 사용했을 때 만들 수 있는 합의 수}$$ 초기값은 $D[0] = 1$이 된다. $i$ 번 비스킷까지 사용하여 만들 수 있는 합 중 가장 큰 수를 $b$라고 하자. 그러..

문제 및 채점: oj.uz $N$ 개의 정점으로 이루어진 트리가 주어진다. 각 정점에 $0$ 이상 $K$ 이하의 수를 서로 다르게 적는다. 수 $i$가 적힌 정점을 정점 $i$라고 하자. 정점 $s$에 인접한 정점에 적힌 수들이 배열 $c$로 주어질 때, 정점 $s$에서 정점 $t$로 가기 위해 어느 인접한 정점으로 이동하면 되는지 구하는 질문이 주어진다. 문제는 정점에 수를 적는 함수와, 주어지는 질문을 해결하는 함수 두 개를 작성하는 것이다. 단, 정점에 적는 수 이외에 전역 변수와 같이 외부 메모리를 참조하여 질문을 해결할 수 없다. 서브태스크 1, 2, 3, 4 이 서브태스크에 대한 풀이는 따로 서술하지 않겠다. 서브태스크 1, 2, 3은 주어지는 트리의 모양이 일자, 완전 이진 트리 등 정해진 ..

문제 및 채점: oj.uz 서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다. 풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시..

문제 및 채점: oj.uz 티켓은 $N$ 개의 색 중 한 가지 색을 띄며, 각 색마다 $M$ 개의 티켓이 있다. 티켓에는 수가 적혀있는데, 티켓에 적힌 수는 서로 다를 수 있다. $K$ 번의 라운드를 진행할거고 각 라운드마다 $N$ 개의 서로 다른 색의 티켓을 뽑고, 어떤 수 $b$를 임의로 정해 $b$와 $N$ 개의 티켓에 적힌 수와 차이값을 구해 모두 더한 값을 $S$라 하자. 이때, $S$의 값이 최소가 되도록 수 $b$를 정한다. 한 라운드에 쓰인 티켓은 소멸되기 때문에 한 티켓은 최대 한 라운드에서만 사용 가능하다. 각 라운드마다 티켓을 적절히 골라 모든 라운드의 $S$ 값들을 다 더한 값을 최대화하는 문제다. 편의상 $N$은 짝수다. 우선, 각 라운드에서 $S$ 값을 계산할 때 문제에서 정의한..

문제 및 채점: oj.uz 정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq 3$이다. $p$ 배열의 내용만 주어졌을 때, 원래 그래프를 복원하는 것이 가능한지 확인하고, 가능하다면 그래프를 복원하는 문제다. 서브태스크 1 (11 점) $p[i][j] = 1$이다. 트리에서 각 정점 사이에 경로는 항상 한 개만 존재한다는 사실을 생각해보자. 즉, 모든 트리에 대해 $p[i][j] = 1$이기 때문에, 아무 트리로 그래프를 복원하면 된다. 아래는 만들 수 있는 단순한 트리 중 하나다. 서브태스크 2 (10 점) $p[i][j] = 0\ \mathrm{or}\..

1. S OR T 스페이스(S)와 탭(T)을 입력한 순서가 주어졌을 때, 총 몇 칸 띄어지게 되었는지 구하는 문제다. 단, 탭 크기는 4다. 문자열을 입력받아서 S가 나오면 칸 수를 1 늘려주고, T가 나오면 칸 수를 현재 칸 수보다 큰 4의 배수로 만들어주면 된다. 더보기 A = input() S = 0 for c in A: S += 1 if c == 'T': while S%4 != 0: S += 1 print(S) 2. 카트라이더 별 모으기 3개의 별이 있고 각 별을 획득할 수 있는 기록 제한이 주어졌을 때, 주어진 기록이 몇 개의 별을 획득할 수 있는지 구하는 문제다. 이 문제에서 시간이 기록은 'aa:bb:cc'꼴로 주어지는데, 이 기록 문자열을 정수로 변환해도 되고, 정수로 변환하지 않고 문자열..

문제 및 채점: 사이트 A. New Elements: Part 1 질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다. 서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] < C[j], J[i] > J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있..