그동안 그래프 이론, 군론 등을 공부하기 위해서 ps를 거의 안 했었는데, NYPC 본선이 얼마 안 남아서 다시 시작했다. 아래는 푼 문제들과 간단한 풀이이다.
26098. AND vs OR
https://www.acmicpc.net/problem/26098
26098번: AND vs OR
수열 $a_l,a_{l+1},\cdots,a_r$의 가치는 다음과 같이 정의된다. 길이가 $2$ 이하일 경우 수열의 가치는 $0$이다. 길이가 $3$ 이상일 경우 수열의 가치는 $(a_l \, \And \,a_r) - (a_{l+1} \, | \, a_{l+2} \, | \cdots | \, a_
www.acmicpc.net
가치가 양수인 구간 $[l, r]$에 대해서, $l<x<r$이면 $A_l>A_l \& A_r > A_{l+1} | A_{l+2} | \cdots | A_{r-1} > A_x$이고, 마찬가지로 하면 $A_r>A_x$이다. 따라서 $A_l > A_{l+1}, \cdots A_{r-1} < A_r$인 구간만 고려해줘도 충분한데, 이러한 구간의 수는 $O(N)$개이고 스택으로 구할 수 있다. 각 구간이 조건을 만족하는지 세그트리로 확인하고 $l$이 큰 쿼리부터 차례로 해결해나가는 과정으로 주어진 쿼리들을 처리할 수 있다.
27507. K볼록껍질
https://www.acmicpc.net/problem/27507
27507번: K볼록껍질
2차원 평면상에 있는 서로 다른 $N$개의 점 중에서 한 점을 지웠을 때, 나머지 $N-1$개의 점을 포함하는 볼록 껍질을 구성하는 꼭짓점의 개수가 $K$가 되어야 한다. 이때, 지울 수 있는 점의 수를 구
www.acmicpc.net
일단 볼록껍질을 구하자. 한 점 $x$에 대해서, 볼록껍질 상에서 인접한 점을 $p, n$이라 하자. $x$를 제거했을 때 볼록껍질에 새로 추가될 수 있는 점의 후보는 $x, p, n$이 이루는 삼각형 내부에 있다. $x_l$을 세 점의 $x$좌표 중 가장 작은 것, $x_r$을 가장 큰 것으로 정의하고 $x$좌표가 $[x_l, x_r]$ 사이에 있는 점들에 대해 삼각형에 포함되는지 일일히 확인한다. 이후 $x$를 제거한 자리에 생기는 볼록껍질을 새로 만들어주면 된다. 이렇게 모든 $x$에 대해 확인해도 하나의 점은 최대 네 번 세어지므로 충분히 빠르다.
28406. 회전초밥
https://www.acmicpc.net/problem/28406
28406번: 회전초밥
첫 번째 줄에 정수 $N$, $K$가 공백으로 구분되어 주어진다. $(1\leq N\leq 2\, 000;$ $2\leq K\leq 1\, 000\, 000)$ 두 번째 줄에 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다. $(0\leq a_i\leq K-1)$ 세 번째 줄에 $b_
www.acmicpc.net
더해지는 값은 $N(N+1)$을 주기로 반복된다. 따라서 첫 $N(N+1)$번의 초밥 분배에서 모든 사람의 접시 위에 있는 초밥 수가 같아지는 시점을 구하고, 몇 번의 주기($N(N+1)$번의 초밥 분배)가 시행되어야 모두 0이 되는지 구하면 된다.
이 과정이 상당히 까다롭다. $i$번 사람에게 가는 첫 $N+1$개의 초밥의 개수를 $X_i$라 하자. 그럼 $i$번 사람에게 가는 다음 $N+1$개의 초밥의 개수는 $X_{i+1}$가 된다. 정확히는, $i$번째 사람이 먹게 되는 $(t-1)(N+1)+1$번째 초밥부터 $t(N+1)$번째 초밥의 개수 합은 $X_{t+i-1}$이 된다. 이 사실을 이용하면 같아지는 시점을 구할 수 있다.
일단 어떤 $b$에 대해 $t\equiv b \pmod{N+1}$를 만족하는 모든 시점 $t$ 중에서 접시 위 초밥이 같아지는 시점이 있는지 구해 주자. 일단 주어진 배열에 대해 초밥을 분배하는 것을 $b$번 시행하고, 이때 새로운 배열에서 $X_i$를 구해 준다. 만약 $b+(N+1)t$ 시점에 $i$, $i+1$번 사람 초밥 수가 같았다고 한다면 $a_i+X_i+X_{i+1}+\cdots + x_{i+t-1} \equiv a_{i+1}+X_{i+1}+\cdots X_{i+t} \pmod{N+1}$, $X_{i+t} \equiv a_i - a_{i-1} +x_{i} \pmod{N+1}$이다. 인덱스는 모두 0-based, mod N+1로 서술되었다.
일단 $Y_i = a_i-a_{i-1}+x_{i}$라는 배열을 만들어주자. 우리의 목표는 모든 $i$에 대해 $Y_{i+t} = X_i$가 되는 $t$를 찾는 것이고, 이는 KMP로 $O(N)$ 시간에 가능하다. $b=0, 1, \cdots N$일때 다 해봐야하니 총 시간 복잡도는 $O(N^2)$이다.
UCPC를 출제한 친구로부터 이 문제가 본선에서 적어도 30팀에게는 풀릴 것이라고 예상되었고, 예상 티어는 P2라는 말을 들었다. 실제로는 한 팀에게도 풀리지 않았고, 난 다2를 기여했다.
27284. 이기적인 목봉 체조 (Hard)
https://www.acmicpc.net/problem/27284
27284번: 이기적인 목봉 체조 (Hard)
입력 순서대로 $1$번 훈련병부터 $N$번 훈련병이라고 하고, 하나의 그룹에 들어 있는 훈련병들을 중괄호 $\{\}$ 안에 넣어 표시하면, $\{1, 2, 3\}, \{4, 5, 6, 7, 8\}, \{9\}, \{10\}$ 으로 그룹을 묶으면 총 $35$
www.acmicpc.net
$N\times M$ dp를 생각할 수 있다. $dp[k][i]$를 $k$번째 구간이 $i$번 원소에서 끝나도록 분할했을 때 최댓값이라고 정의하고, $1 \le i \le N$인 $i$에 대해 $dp[k][i]$를 다 구해 놓았고, 이제 $dp[k+1][i]$들을 구해야 하는 상황을 보자.
$i$를 증가시키며 구한다. 각 $j\le i$에 대해 $[j, i]$번 구간을 $k+1$번째 구간으로 할 때 최댓값을 저장하는 세그먼트 트리를 만들자. $H_a<H_b$, $a<b<i$일 때 $S_a$는 dp 갱신에 있어 앞으로 무의미한 값이다. 무의미하지 않은 값들을 스택으로 관리할 수 있다. 한 유의미한 값에 대해 $[j, i]$를 선택했을 때 거기에 $S$가 더해지게 되는 $j$는 구간을 이룬다. 따라서 유의미한 값들을 세그먼트 트리로 관리하면 풀 수 있다.
6626. Measuring Problem Difficulty
https://www.acmicpc.net/problem/6626
6626번: Measuring Problem Difficulty
If you are the lucky one to advance to the ACM-ICPC World Finals, one of the situations you will face is the world finals competition itself. Wait, isn’t that the main reason to go there? In the beginning of each ACM-ICPC competition, there are two separ
www.acmicpc.net
각 문제의 세 명에 대한 평가를 좌표 $(x_i, y_i, z_i)$로 생각하자. $x_i<x_j, y_i<y_j, z_i<z_j$인 $(i, j)$ 쌍 문제를 찾는 것과 같다. 다음과 같이 풀 수 있다.
함수 $f(s, e)$를 $s \le z_i \le e$인 $i, j$들만 고려할 때 발생하는 쌍의 개수를 찾는 함수라 하자. 다음과 같이 구현할 수 있다.
우선 $m=(s+e)/2$로 두고, $i \le m < j$인 쌍의 개수를 전부 셀 것이다. 이는 점들을 $y_i$좌표 오름차순으로 정렬하고, 세그먼트 트리에서 스위핑으로 풀 수 있다.
다음으로, $f(s, m)$과 $f(m+1, e)$를 호출한다. 세 값을 다 더해서 리턴하면 된다.
19381. Ascending Tree
https://www.acmicpc.net/problem/19381
19381번: Ascending Tree
The first line contains two integers: $N$, the number of vertices in the tree, and $C_1$, the label assigned to the root. The vertices are numbered $1$ through $N$, and the root is vertex $1$ ($1 \le N \le 10^5$). The next $N - 1$ line describe non-root ve
www.acmicpc.net
BOJ 수열 1의 트리버전이다. 흔히 알려진 slope trick 알고리즘으로, 풀이가 거의 같다. 두개 넣고 하나 빼는 과정 이전에 모든 자식들의 우선순위 큐를 큰작으로 합쳐주면 된다.
14639. Replicate Replicate Rfplicbte
https://www.acmicpc.net/problem/14639
14639번: Replicate Replicate Rfplicbte
The first line of input contains two integers w (1 ≤ w ≤ 300) and h (1 ≤ h ≤ 300), where w and h are the width and height of the bounding box of the final pattern. Following that are h lines, each containing w characters, giving the final pattern.
www.acmicpc.net
처음부터 선대로 접근했는데, 안 쓰고도 되는지는 모르겠다.
체 $GF(2)$위의 $H \times W$ 크기의 행렬들의 집합을 생각하자. 두 행렬의 덧셈을 일반적인 행렬 덧셈으로 정의하면 이 집합은 벡터공간을 이룬다. 이를 $V$라 하자. 함수 $T$를 문제에서 정의된 오류가 발생하지 않았을 때의 변환으로 생각한다.
관찰 1. $A, B \in V$일 때, $T(A+B)=T(A)+T(B)$
행렬의 각 성분별로 생각하면 어렵지 않다. 또한, 자명하게 $T(cA)=cT(A)$이므로 $T$는 선형변환이다.
관찰 2. 주어진 배열에 대해서, 문제에서 설명된 변환(최대 하나의 오류가 있는 경우)이 일어나기 전의 배열이 존재한다면 유일하다.
현재 배열이 $B$이고, 변환이 일어나기 전의 배열이 $A$, 변환이 일어난 후 버그로 변한 셀의 행렬(변한 셀에 대한 성분만 1이고 나머지 모든 성분은 0인 행렬)을 $C$라 하자. 가능한 서로 다른 순서쌍이 $(A_1, C_1), (A_2, C_2)$로 두 개 있다 하자. 그러면 $B=T(A_1)+C_1=T(A_2)+C_2$, $T(A_1)+T(A_2)=T(A_1+A_2)=C_1+C_2$이다. 좌변의 행렬에 1인 성분이 있다면 반드시 4개 이상 있고, 우변의 행렬의 경우 가능한 1 성분의 개수는 0, 1, 2이다. 따라서 양변은 영행렬로 같고, $C_1=C_2$이다. 따라서 모순, 귀류법에 의해 성립한다.
이 사실을 이용하면 문제를 풀 수 있다. 주어진 배열에 대해서 한 번의 변환이 시행되기 전 배열이 존재하는지를 확인하고(존재하다면 유일하다), 있다면 변환 전으로 되돌리는 작업을 최대 $\max(H, W)$번 반복하면 된다.
각 작업에 대해서 뒤집힌 원소를 빨리 찾아야 한다. 일단 뒤집힌 원소가 없는 상황을 가정해 보자. 그러면 원래 배열의 첫 열은 자동결정되고, 마찬가지로 순서대로 모든 나머지 행들도 자동결정된다. 이 과정에서 모순이 없다면 변환이 시행되기 전 배열이 존재하는 것이다. 그런데 모순이 생겼다면, 그 행에서 뒤집힌 칸이 존재한다. 마찬가지 방법으로 뒤집힌 칸이 존재하는 열도 알 수 있고, 결과적으로 뒤집힌 칸을 알 수 있게 된다. 각 작업은 $O(HW)$에 가능하므로, 전체 시간복잡도는 $O((H+W)HW)$이다.
14240. 부분 수열의 점수
https://www.acmicpc.net/problem/14240
14240번: 부분 수열의 점수
수열 s = s1, s2, ..., sn의 점수는 Σi·si로 구할 수 있다. 수열 s의 연속된 부분 수열의 점수의 최댓값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
쉬운 풀이가 있는거같은데, 그냥 처음 생각한 풀이인 dnc를 짰다.
$i\le m < j$인 부분수열 $[i, j]$만 고려하자. $j$가 정해져 있을 때 $i$에 대한 $[i, j]$부분수열의 점수는 $i$에 대한 일차함수이다. 이러한 함수들을 다 구해 놓고 cht를 돌리면 된다. 다 구한 다음에는 재귀함수로 $[i, m]$, $[m+1, e]$구간에 대한 답을 구하면 된다.