By MilkClouds in PS — 2022년 3월 30일

3월의 PS일지(2/2선)

D: 삼각형의 세 선분에 의한 회전도형의 부피를 적절히 더하고 빼면 된다.
G: 계단 수는 가장 작은 수와 그것보다 1 큰 수를 한 쌍씩 지워버려도 똑같이 계단 수다. 가장 큰 원소보다 1 작은 수를 처리할 때는 가장 큰 원소와 같은지만 판단하면 된다.
H: $GGG\langle a_0, a_1, \ldots a_m \rangle$은 $a_n=a_0+\sum_{i}^{n}b_n$이 된다. $b_n$은 $GGG\langle a_1, \ldots a_m \rangle$에 대응된다. 비슷하게 계속 전개해 나가면 $a_n=a_0+na_1+\dfrac{n(n+1)}{2}a_2+\dfrac{n(n+1)(n+2)}{3}a_3+\ldots$가 된다. 따라서 $f(0)=a_0$을 구하고, $f(x)-a_0$을 $x$로 나누고, $x=0$을 대입하면 $a_1$이 나오고, 여기서 $a_1$을 빼고 $\dfrac{n+1}{2}$로 나누고 $x=0$을 대입하면 $a_2$가 나오고, ... 을 반복하면 된다. 다항식의 나눗셈이지만 연산이 간단하고 나누는 항이 무조건 1차식이므로 FFT 없이 단순구현해야 한다. FFT 했다가 TLE 받았었다. $\sum \dfrac{n(n+1)(n+2)}{3}$ 같은 꼴이, n+3 같은 항이 하나 더 붙고 분모의 3이 4로 바뀌는 건, 고등학교 때 내가 관찰했었던 점이다.
G: 수식을 열심히 세우자.

절반씩 분할정복하자.

서로소 $a, n$에 대해 $a^{\phi(n)}=1 \mod n$임은 잘 알려져 있고, $a, n$이 서로소가 아니라도 $a^{2\phi(n)}=a^{\phi(n)} \mod n$이다. 이를 이용해 구하는 문제다.

A: 소수가 그렇게 sparse하게 분포하고 있지는 않으니 대충 양쪽 끝부분 1000개쯤 매칭시켜 gcd==1 검사하면 되지 않을까 해서 풀었고 그렇게 됐다.
B: 특정 지점 이전까지의 (1개수)-(0개수) 최댓값 $M$과 최솟값 $m$을 저장해 두고 그 지점까지의 (1개수)-(0개수)에서 $M, m$을 빼어 전체 구간에서 특정 subarray를 반전시켰을 때 최대한으로 변하는 개수를 구해두면 된다. 얼마나 변할지는 1 간격으로 연속적으로 변하므로 최댓값과 최솟값만 구해 사이 간격을 세면 답이 나온다.
C: $0,1,2,3, \ldots,N-2, N$의 경우 $N$을 $N-1$로 만들었을 때 Alice가 이긴다. 이 때 $N-2$와 $N$이 2 차이나는 것에 착안해, 만약 최대 원소가 두번째로 큰 원소보다 2 이상 크다면, 만약 두번째로 큰 원소보다 최대 원소를 작게 만들었을 때 상대가 지게 된다면 그렇게 하면 되고(이게 가능하냐/아니냐도 문제인데, 처음 든 예시가 이게 불가능한 예시이며 이 때 Alice는 이긴다), 그렇지 않다면 두번째의 큰 원소보다 최대 원소가 1 크게 해서 상대에게 넘겨주면 자신이 이기는 판이 나온다. 만약 최대 원소가 두번째로 큰 원소보다 1 크다면, 둘은 처음 내린 결론에 의해 무조건 2 이상 차이가 나지 않게 할 것이므로 배열의 최댓값은 1씩만 줄어들 것이다. 결론적으로, $N-1$과 $max(A)$의 parity에 승패가 의존한다.
D: 특정 원소가 몇번 더해지냐를 고려하면, $1, 0, 0, 0$ 다음에 $1,1,1,1,$ 다음에 $1,2,3,4$ 다음에 $1,3,6,10$ 이렇게 $\sum n^k$꼴이 나온다. 어떤 원소 이전의 값까지 모든 합과 그 원소의 이전 시점의 값의 합으로 어떤 원소가 몇 번 더해지냐가 결정되는데, 아래와 같은 재귀적인 구조가 나타난다. 분할정복을 이용해 반복적으로 더해지는 값을 효율적으로 더하면 $n\log{n}$에 풀 수 있다.

출처: https://codeforces.com/blog/entry/100999

E: 0번째 날부터 N번째 날까지, N+1개의 날짜를 노드로 삼아 네트워크 플로우 그래프를 만든다. 이 때, $L[i]-1$부터 $R[i]$까지를 잇는 cap 1, cost $C_i$의 간선을 요리사로 취급할 수 있고, $j$날부터 $j-1$날까지를 잇는 cap $A[j]$, cost $-D$의 간선을 하루가 지나갈 때 최대 $A[j]$개 빵을 $D$ 가격에 팔아재끼는 거라 생각할 수 있다. 단, 요리사가 너무 많아 팔 수 있는 빵의 개수를 초과할 수 있는데, 이 경우 빵을 0원에 팔아넘기는 것과 같으므로 $j$날과 $j-1$날을 잇는 cap $M-A[j]$, cost $0$의 간선도 추가해야 한다.

이렇게 한 후 min cost circulation 문제를 풀면 되는데, 나는 이 문제를 풀면서 "circulation 문제"라는 걸 처음 봤고... 이걸 익숙한 min cost flow 문제로 고치려면, $A[j]$개를 매일 무조건 팔아재끼는 걸로 하되 $j$번째 날부터 $j+1$ 날을 잇는 cap $A[j]$, cost $D$의 간선에 $f$만큼 flow가 흐르면 $f$개 빵을 사며 $Df$만큼 이익을 덜 얻는 것으로 파악할 수 있다. (~~공매도?~~) 최대 유량 알고리즘은 유량을 최대한 채우려고 할 것이므로 손해를 감수하고서라도 사려고 할 텐데, 이를 보호하기 위해 요리사가 $L[i]-1$날부터 $R[i]$날까지 빵을 만들면 $j\rarr j+1$ 간선에 유량이 덜 흐르며 빵을 덜 사게 할 수 있다. source에서 최대 공급 유량(=흐를 유량)을 $M$으로 설정한 후에 min cost를 돌리면 된다.

A: i<j<k일 때 주어진 관계가 성립하고, 최대/최소 값의 index를 구해 출력하면 된다.
B: 몇번을 적용하든 결국 그 직전 선택한 원소만 영향을 준다는 것을 이용하면 된다. (2번 이상 전에 적용한 연산은 cancel된다.)
C: 만약 0과, 2 이상의 원소만 존재한다면 mod max(A) 연산을 반복하여 모든 원소를 0으로 만들 수 있다. 1이 존재한다면 mod max(A)-1 연산을 반복하여 모든 원소를 1로 만들 수 있을 수도 있는데, 만약 인접한 원소가 존재한다면 불가능하다. k와 k+1를 같게 만드는 게 이러한 방법 외에도 전혀 불가능한지 검토를 해봐야 하는데, 그냥 k와 k+1을 제외한 모든 자연수로 mod n을 해봤을 때 둘이 같아지지 않으므로 둘이 같아질 수 없다. (같게 만드는 유일한 방법이 mod k+1, mod k를 순차적으로 해서 둘을 모두 0으로 만드는 것인데 그럼 배열에 1이 존재할 때는 배열의 모든 원소를 같게 만드는 게 불가능하다.) 불가능한 경우만 NO를 출력하면 된다.
D: $n\ge k(k+1)/2$이며 $n \equiv k(k+1)/2 \mod k$인 $k$를 찾아야 한다. 만약 $k$가 짝수라면 $k^2/2 \mod k\equiv 0$이므로 $n\equiv k/2 \mod k$여야 하고, 이러한 $k$는 $2n$의 약수 중 $n$을 못 나누는 짝수이다. 이러한 $k$ 중 가장 작은 $k$는" $n$의 약수 중 최대의 2의 거듭제곱수"에 2를 곱한 수이다. 이러한 $k$를 $k_1$으로 두자. 만약 $n \ge k_1(k_1+1)/2$라면 $k_1$을 그대로 출력하면 되지만, 그렇지 않을 수도 있다. 그런 경우 $2n=k_1k_2$를 만족하는 $k_2$가 존재하는데, $k_1(k_1+1)/2>n$이므로 $k_1+1>k_2$, $k_1-1\ge k_2$, $k_2(k_2+1)/2 \le k_2k_1/2 = n$이다. 따라서 $k_2$가 대신 조건을 만족한다. $n$이 2의 거듭제곱수일 때 $k_2=1$이므로 이때만 불가능하다.
E: 어떤 노드를 기준으로 자르든 정점의 가중치의 합이 일정한 트리를 만들어야 한다. 이는 2-color 컬러링 후에, 색상에 따라 +deg[v]나 -deg[v]를 할당하면 된다. 아래 풀이를 참고하자. 핵심 아이디어는, 어떤 자식에 대한 서브트리 합 Sv이든, S1-Su와 똑같은 값을 가지므로, Su+Sv=S1으로 일정하다는 것이다. S1=0으로 두면 Su+Sv=0이고, 이렇게 되려면 $Su=\pm deg[u]$여야 한다.

F: 정점에 할당된 값 $a_n$이 주어지고, 두 정점 사이 거리함수 $d(u, v, t)$가 주어진다. 이 때 이 정점에 임의의 간선 집합이 주어져 트리가 만들어질 때, MST의 거리값 총합이 upper bounded되어 있는지 파악해야 한다. 주어진 거리함수 $b[u]=a[u]+t$로 두면 $d(u, v, t)=b[u]b[v]-t^2$이고, 따라서 $t$가 주어져 있을 때 MST의 거리값을 최소화한다는 목표를 가진다면 $b[u]$가 음수면 최대의 $b[v]$, 반대로 양수면 최소의 $b[v]$를 찾아야 한다. $b[u]$, 다시 말해 $a[u]$ 기준으로 정렬한 후에 $b[u]$가 음수인 노드는 $N-1$에, 양수인 노드를 $0$에 연결하면 전체 $N-1$의 edge가 생기며, 모든 노드가 $0$ 또는 $N-1$에 연결되어 있으므로, 이 그래프는 트리가 된다. 또한 주어진 $t$에 대해 최소의 MST 값을 가질 것이다. 이제 $t$를 적절히 바꿔가며(MST의 거리값 총합은 $t$에 대한 일차함수인데, 이게 바뀌는 event는 최대 $N$개 생길 것이며 각 event는 $O(1)$에 처리 가능하다) upper bounded되어 있는지, 되어 있다면 최댓값이 얼마인지 찾아야 한다.

긴 정수열에 대해 $n$자리까지만 나타낸 값이 $a[n]$이면, $i$번째부터 $j$번째 자리까지 정수는 $a[j]-a[i-1]$에 10의 승수를 곱한 꼴이다. 10의 승수는 애초부터 $\mod 7$에 0이 아니므로, $a[j]=a[i-1] \mod 7$인 $i,j$ 개수가 원하는 수가 되도록 만들면 된다. 대충 $a$를 $[0, 1, 1, 1, 1, 1, 1, \ldots, 1, 2, 2, 2, 2, 2, 2, \ldots, 3, 3, 3]$ 처럼 만들면 된다. (맨 처음의 0은 "0자리수의 $\mod 7$로, 편의상 도입한 수)

A: 왠지 ~~~A 꼴로 생겼으며 얘를 2배 시켰을 때 B~~~가 나오게 할 수 있을 것 같다. 대충 $500000000B+A$를 출력하면 된다.
B: 인접한 노드는 최대 4개이며 색상은 5개이므로 무조건 인접한 색깔과 distinct한 색깔을 칠할 수 있음이 보장된다. 완전탐색 비슷하게 돌리며 주변에 없는 색깔 아무거나 할당하면 된다.
C: N이 홀수면 무조건 이기고, 짝수면 하나 지웠을 때 XOR=0으로 만들 수 있으면 이기고 아니면 진다.
D: 화살마다 최대 거리가 $D$가 되도록 최대한 밀접하게 분포하게 하는 게 최선이라는 건 자명하고, $0$을 중심으로 좌우에 $(N+1)/2$개와 $N/2$개가 분포될 것이다. 또한 $0$에서 가장 가까운 화살의 거리가 $D$보다 멀어지면 suboptimal함도 직관적으로 파악할 수 있다. (전체 분포를 $D$만큼 밀면 중심에 더 치우친, 더 optimal한 분포가 나온다) 이제 이벤트 기반으로 슬라이딩을 하고 싶은데, 이걸 $N$ 기준으로 하면 $M$까지 고려되면서 $NM$이 소모될 듯 싶고 좀 번거롭다. $N$ 대신 $M$ 기준으로, 다시 말해 화살 대신 지역 기준으로 생각하자. $x>0$에서 $0$에 가장 가까운 화살의 거리가 $i(i<=D)$일 때 각각의 지역에 몇 개 화살이 걸치며 어떻게 분포가 변하는지 파악하면 된다. 만약 $ND$가 $R[j]$보다 크다면 화살이 그 구역을 넘어서까지 박힌다는 뜻으로, $i$를 적절히 변화시키면 $[0, R[j]]$에 박히는 화살의 개수가 변한다. (하나 줄어듦) 하지만 $ND<R[j]$면 $i$를 아무리 변화시켜서 $i=D$까지 간다고 한들 $[0, R[j]]$에 박히는 화살 개수는 안 변한다. $i$가 $D$까지밖에 못 변하므로 각 구역에 대해 이벤트는 최대 1개고 그 이벤트에 대해 $O(1)$가 소모되게 할 수 있다.
양수, 음수 부분에 대해 같은 일을 반복해주고 두 결과를 합치면 된다. 꽤 멋진 구현본을 아래 첨부한다.

import sys
input = sys.stdin.readline
N, M, D = map(int, input().split())
r = [*map(int, input().split())][1:]
s = [*map(int, input().split())]
for i in range(M - 1):
    s[i] -= s[i + 1]
def f(n):
    ret = [0] * (D + 1)
    for i in range(M):
        ret[0] += s[i] * min(n, (r[i] // D + 1))
        if r[i] < n * D:
            ret[r[i] % D + 1] -= s[i]
    for i in range(D):
        ret[i + 1] += ret[i]
    return ret
a, b = f(N + 1 >> 1), f(N >> 1)
ret = 0
for i in range(D):
    ret = max(ret, a[i] + b[D - i])
print(ret)

E: 맨 처음에는 $abs(i-j) \mod 3$에 따라 색깔을 할당할까 싶었는데, 그렇게 하면 삼각형의 세 변 색깔이 모두 달라야 한다는 원칙은 만족하지만 세 색깔의 사용 횟수가 같지 않다. 좀 다르게, 간선 $(i, j)(i<j)$에 대해 오직 $i$에만 (결정론적으로) 의존하는 색깔을 할당하자. 그럼, $a<b<c$인 $a,b,c$에 대해 $(a,b),(b,c),(c,a)$의 색은 $a, b, a$에 의존하게 되어 무조건 겹치는 색이 생긴다.
삼각형 세 변 색깔이 다른 건 됐고, 이제 세 색깔 사용 횟수를 같게 하고 싶다. 참고로, ${}_N {C}_2$는 루카스 정리에 의해 $N=0,1 \mod 3$일 때만 $3$의 배수이다. $N=6$이면 각 색에 대해 $((1, 5), (2,4), (3,))$번 사용되도록 하면 되고, $N=7, 9, 10$일 때도 비슷하게 구성할 수 있다. $N\ge 12$이면 $N-6$에 대한 결과에 $((N-1,N-6),(N-2,N-5),(N-3,N-4))$를 합하면 된다.

A: 0과 0 사이에는 11을 끼워넣어야 하며 이것만으로 문자열 전체가 조건을 만족한다.
B: 1 이외의 홀수 gcd를 만드는 것은 불가능하다. 또한 n이 홀수이면 경우의 수가 0이다. n/2 팩토리얼의 제곱을 출력하면 된다.
C: 1은 한번만 출현해야 하고, 배열은 1씩 증가하거나 0 이상의 수가 감소하면 된다.
D: 최상위 비트, 최상위 비트부터 한단계 아래 비트"까지", 최상위 비트부터 두단계 아래 비트까지, ..., 최상위 비트부터 최하위 비트까지, 수의 분포를 저장해둔다. 이후 최상위 비트부터, 만약 있어야 하는 수의 분포가 실제 분포와 다르면 xor을 해주면 된다.
E: 가장 큰 수가 적힌 곳에서 시작하면 이기고, 가장 큰 곳에 도달할 수 없는 곳에서 시작하면 지는 것은 명확하다. 이제, 이기고 지는 것이 아직 명확하지 않은 곳(가장 큰 수에 도달할 수 있지만 가장 큰 수가 적혀 있지는 않은 곳)에 대해 생각해보자. 아직 이기고 지는 게 정해지지 않은 장소 중 가장 큰 수가 적혀 있는 장소와 원래 가장 큰 수가 적힌 곳에 모두 도달하지 못하는 곳에서 시작하면 무조건 진다. 여기서 지는 게 확정된 장소를 빼준 후, 비슷하게 아직 이기고 지는 게 정해지지 않은 장소 중 가장 큰 수와 이전의 "무조건 이기는 곳"에 모두 도달하는 곳에서 시작하면 무조건 진다. 이런 식으로 반복적으로 어떤 칸에서 시작했을 때 이기고 지는 여부를 확정지으면 된다. 결국은 여러 L1 circle의 교집합에서 시작하면 이기고 아니면 지게 결과가 나오고, 이는 큰 수부터 priority queue에 넣으며 L1 circle의 교집합을 O(1)에 구하면 된다. pq에서 나온 수가 지는 걸로 확정되어 있으면 제끼고 아니라면 기존의 교집합에 그 점 근방의 L1 circle을 교집합시키면 된다.
F: 상당히 놀라운 문제인데, 만약 이산적인 특성에 따라 애당초 01 개수를 못 맞추는 경우가 아니라면 무조건 2개 세그먼트 이내에서 전체 01 개수 비율과 비율이 같은 부분을 골라줄 수 있다. 증명은 간단한데, 일단 길이가 m으로 고정된 substring을 생각하면, 이것은 시작 지점이 하나 이동할 때 1 개수는 무조건 하나 이하 변한다. 그리고 만약 모든 길이 m substring의 1 개수가, 전체 01 개수 비율에 따른 m 길이 구간의 1 개수보다 적다면, 애당초 전체 01 개수 비율이 못 미쳤을 것이다. 비슷하게 클 때도 모순을 이끌어낼 수 있다. 길이가 m인 substring을 circular하게 고려해주다, 원래 배열에서 한 구간으로 나타나면 그대로 출력하고 두 구간으로 나뉘면(양끝 segment로 나뉘는 경우) 나눠 출력하면 된다. 오름차순 출력임에 유의

You might also like...