2024년 6월 PS 일지

요약

BOJ

시험기간 등 위기가 많았지만, 매일 다이아 한 문제 이상 풀기에 성공했다. 스트릭이 매일 오전 6시에 초기화되는데, 오전 5시 30분이 넘어 겨우 맞은 날이 6월에만 적어도 3번은 되는 것 같다.

개인적으로 재미있었던 문제는 다음과 같다.

1. 좋은 수열(31442)
2. Bit Shift Registers (22048)
3. Led-led Paths (16659)
4. Gross LCS (24691)
5. Library 3 (32002)

코드포스

7월을 하루 앞두고 코포 레이팅도 IGM을 회복하는데 성공했다. 이제 크게 망하지 않으면 2500~2700의 퍼포먼스가 안정적으로 나오는 것 같은데, 다이아스트릭의 영향이 있는 것 같다. 이대로만 간다면 연말에는 2700을 찍을 수 있지 않을까?

 

18913. Graph Coloring

https://www.acmicpc.net/problem/18913

각 정점에 0 7개, 1 7개로 이루어진 길이 14의 서로 다른 이진 문자열들을 대응하자. $\binom{14}{7}$이 3000보다 커서 가능하다.

 

이후 $i$에서 $j$로 가는 간선이 있으면 그 간선의 색을 $i$의 문자열에서는 0이고 $j$의 문자열에서는 1인 인덱스로 정하면 된다. 이러면 $i$에서 $j$로 가고, $j$에서 $k$로 가는 간선의 색이 같은 경우가 없다.

 

어떤 문제의 ptsd가 떠오르는 문제이다...

 

11808. 마리오와 사악한 키노피오

https://www.acmicpc.net/problem/11808

이동할 정점들을 선택하면, 정점들의 이동 순서를 잘 정하여 이동할 길이가 다음 값이 되도록 할 수 있다.

• 각 간선에 대하여 그 간선을 제거했을 때 나뉘는 컴포넌트에 선택된 정점이 각각 $a$, $b$개 있다 하자. 모든 간선에 대한 $min \{ a, b\}$의 합만큼 이동하는 경우가 최대이다

이렇게 하면 다음과 같은 dp를 세울 수 있다.

• $dp[i][j]$ : $i$를 루트로 하는 서브트리에서 $j$개 정점을 선택했을 때, $i$를 루트로 하는 서브트리 간선들만 고려할 때 발생하는 비용의 최댓값

크기가 $A$인 서브트리와 $B$인 서브트리의 $dp$값들을 $O(min \{ A, K\} min \{ B, K\})$ 시간에 합칠 수 있다. 따라서 전체 시간복잡도는 $O(NK)$이다.

흔히 검은 돌 dp라 불리는 방법이다.

 

3408. Non-boring Sequences

https://www.acmicpc.net/problem/3408

고정된 $l$에 대하여 $[l, i]$ 꼴들의 구간이 조건을 만족하는지 다음과 같이 확인할 수 있다.

각 수 $x$에 대하여 $x$가$[l, N]$ 구간에서 처음 등장하는 인덱스를 $l_x$, 두 번째로 등장하는 인덱스를 $r_x$라 하자. 모든 $x$에 대하여 빈 배열 $X$의 $[l_x, r_x)$ 구간에 1을 더해주자.

 

만약 배열 $X$의 $[l, N]$ 부분구간에서 값이 $0$인 인덱스 $ind$가 있다 하자. 그럼 주어진 배열에 $[ind, N]$ 부분구간에는 유일하게 등장하는 숫자가 없다는 뜻이다.

 

이제 처음에 고정한 $l$을 점차 줄여가면서 배열 $X$를 레이지 세그먼트 트리로 관리하면 문제를 풀 수 있다.

 

16670. King Kog’s Reception

https://www.acmicpc.net/problem/16670

4년 전 겨울학교에서 봤던 문제이다. 그땐 못 풀었었는데 지금 보니까 바로 풀렸다.

세그트리로 풀 수 있다. 같은 시간에 예약한 두 손님은 없으므로, $[l, r]$시간에 대한 노드에 다음 값을 저장한다.

• $l$번 시간 이전에 예약한 손님이 없다 가정했을 때, $r$번 손님이 식사를 마치는 시점
• $l$번 손님부터 $r$번 손님의 총 식당 이용 시간

추가와 제거는 세그트리의 기본 연산으로 가능하고, 쿼리의 경우 $[1, i]$ 구간을 잡으면 된다.

 

18772. Delightful (Easy)

https://www.acmicpc.net/problem/18772

다음 관찰이 필요하다.

• 1자리 3진법 수 $X$, $Y$에 대하여 $(X \& Y)$가 $X$와 같고, $(X | Y)$가 $Y$와 같다면 $X \le Y$이다.
• 1자리 3진법 수 $X$, $Y$에 대하여 $X ^ (~Y)$의 값은 두 수가 같다면 2, 아니면 0이나 1이다.
• 0과 1로만 이루어진 수 $X$에 대해 $X = X | (X >> 1)$, $X = X | (X >> 2)$, $X = X | (X >> 4)$... 을 반복하면 $X$는 $000 \cdots 000111 \cdots 111$ 꼴이 된다.

위 관찰들을 사용해 가장 큰 $ndp(X)$개의 비트는 0, 나머지는 모두 2인 비트를 만들 수 있다. 이를 반전시킨 뒤, 각 자리의 합을 구하면 된다. 이것도 방법이 많지만, 난 그냥 일일히 더하는 방법을 사용했다.

 

8480. Excursion

https://www.acmicpc.net/problem/8480

배열 $S$를 $W$의 누적합이라 하고 dp식을 세워 보면 $dp[i] = min \{ dp[j]+{S_j}^{2} +(-2 S_j) S_i \} +{S_i}^2$ 이 된다. ($(j, i]$를 하나의 구간으로 잡는 경우이다) 이때 $j$는 $D$ 조건을 만족시키는 범위여야 한다. 이는 cht가 되는 형태이다.

 

하나의 $dp[i]$를 구하고, 한번에 $(i, j]$ 구간을 잡을 수 있는 모든 $j$에 대해 $dp[j]$ 값을 갱신시키는 방법을 생각해보자. 그러나 이는 너무 느리므로 버킷질을 사용한다.

$B$를 적당히 $N^{0.5}$정도로 잡고, 직선들의 집합 $S_1, S_2, \cdots, S_{ceil(N/B)}$를 정의한다. $S_i$에는 $i$번째 버킷에 해당되는 값들에 대해 모두 추가되는 직선을 담을 것이다.

 

그럼 $dp[i]$를 다음 값들 중 하나로 구할 수 있다.

• $i$가 포함된 버킷의 $S_x$에서의 직선
• $i$와 같은 버킷에 있는 위치에서 $i$로 갱신되는 $dp$값

첫 번째는 $S_x$를 직선 기울기대로 전처리해 둔다면 cht에서 사용되는 방법으로 이분탐색할 수 있고, 두번째는 후보가 $N/B$개 정도이므로 다 해보면 된다.

 

루트개의 $S$들을 전처리하기 위해 정렬이 필요하여 총 시간 복잡도는 루트로그개인데 로그가 정렬에 붙어서 꽤 빠르다.

 

24691. Gross LCS

https://www.acmicpc.net/problem/24691

우선 한 $x$에 대해 $A_i +x=B_J$를 만족하는 쌍의 수를 $K$개라 하면, 세그먼트 트리를 사용하여 $O (K \log N)$ 시간 복잡도에 $x$에 대한 답을 구할 수 있다. 증가하는 부분 수열의 길이를 구하는 문제와 동일하다.

 

$K$개의 쌍을 찾는 과정은 어렵지 않다. $x$를 줄여가면서 슬라이딩 윈도우처럼 쌍들을 관리해주면 되는데, 집합에 $(A_i, B_j)$ 꼴의 수를 넣고, 집합에서 $B_j-A_i$가 가장 큰 것부터 골라서 $A_i$를 더 작은 것으로 바꿔주는 방법을 쓰면 된다. A_i가 중복되는 경우를 유의해야 한다.

 

이렇게 짜면 메모리 제한 안에 동작한다.

 

22048. Bit Shift Registers

https://www.acmicpc.net/problem/22048

우선 $a \le b$이면 $0 \le b-a$이고, 이는 비트 연산에서 $b + (~a)+1$과 같다. 따라서 이 값을 계산하고 부호비트가 켜져있는지 여부로 대소를 판단할 수 있다. 이후의 풀이는 모두 이 사실을 이용한다.

 

$s=0$의 경우, 최솟값만 찾으면 된다. 우선 첫 번째 레지스터를 홀수번째 수들(1, 3, 5, ...)만 켜져 있는 레지스터, 짝수번째 수들(0, 2, 4, ...)만 켜져 있는 레지스터로 분리한다. 이후 홀수번째 수들만 켜져 있는 레지스터를 $K$만큼 오른쪽으로 시프트한다. 이렇게 하면 정수 $n$에 대하여 두 레지스터의 $2nk$부터 $2nk+k-1$번째 위치에는 각각 원래 배열의 $2n, 2n+1$번째 수가 저장되어 있게 된다.

이후 처음의 대소비교를 이용하여 첫 번째 레지스터에서의 값이 더 컸다면 1, 그렇지 않다면 0이 저장되어 있게 하는 레지스터를 만들 수 있다. 이를 사용하면 $N$개의 수 중 큰 $N/2$개를 거를 수 있다. 이 과정을 로그번 반복하면 된다.

 

$s=1$의 경우, 기본적으로는 다음과 같은 정렬 알고리즘을 사용한다.

$i$를 1부터 $N$까지 증가시키며 다음을 반복한다.

• $i$가 홀수인 경우, 각 $2j, 2j+1$번째 수를 비교하여 큰 수가 앞에 있다면 교환한다.
• $i$가 짝수인 경우, 각 $2j+1, 2j+2$번째 수를 비교하여 큰 수가 앞에 있다면 교환한다.

위 과정은 병렬로 처리할 수 있고, 따라서 약 30번 정도의 연산으로 각 $i$에 대한 작업을 처리할 수 있다.

 

구현이 좀 긴데, 열심히 잘 짜면 맞는다. 나는 3번 서브태스크를 예외처리해주어야 했다.

 

31968. Jobs

https://www.acmicpc.net/problem/31968

일의 순서관계를 따지면 트리를 이룬다. 주어진 구조는 연결이 아니지만, 0번 정점에서 각 트리의 루트까지 간선을 이어 트리로 만들자.

$s$가 증가함에 따라 답이 증가하게 되는데, 어떤 $a_1, a_2, \cdots a_k, b_1, b_2, \cdots, b_k$가 있어서 $s \in [a_i, a_{i+1} )$이면 답이 $b_i$가 된다.

이러한 정보는 특정 서브트리만 봤을 때도 만족하므로, 이러한 정보들을 dfs를 하며 각 정점을 루트로 하는 서브트리에 대한 정보를 smaller to larger로 구해주면 된다.

 

20297. Confuzzle

https://www.acmicpc.net/problem/20297

트리의 각 정점 $v$에 대해 $dp[v][c]$를 $v$에서 $v$의 자손 중 값이 $c$인 가장 가까운 정점으로 하자. $v$의 값이 $c$라면 0으로 한다. 모든 $c$ 인덱스를 가지고 있을 필요는 없고, map 등을 사용하여 필요한 인덱스만 가지고 있으면 된다. $v$의 자손 개수만큼의 인덱스만을 가지고 있으면 된다.

 

이후 dfs를 돌면서 $dp[v][c]$를 smaller to larger로 구하고, 그와 동시에 해당 정점에 대해 그 정점을 lca로 가지는 경로들을 고려하면 된다.

 

16659. LED-led Paths

https://www.acmicpc.net/problem/16659

주어진 그래프가 DAG이므로 위상정렬이 존재한다. 위상정렬 순서대로 $1 \le a, b, c \le 40$인 $(a, b, c)$ 순서쌍을 사전순으로 대응한다. $v$에 대응된 순서쌍을 $a_v, b_v, c_v$라 하자. $u$에서 $v$로 가는 간선이 있다면 $u$는 $v$보다 위상정렬에서 먼저 등장하고, $a_u < a_v, b_u<b_v, c_u<c_v$ 셋 중 하나는 만족한다. $i$번째 명제가 참이라면 $u$에서 $v$로 가는 간선을 $i$로 색칠해준다. 이렇게 하면 길이가 40을 넘는 단색의 경로가 없다.

 

21768. AND PLUS OR

https://www.acmicpc.net/problem/21768

정해보다 비효율적인 풀이고, 별로 알아도 도움이 되는 것이 없어서 풀이 요약을 하지 않는다. 백준 대회 페이지에 공식 에디토리얼이 있는 것으로 알고 있다.

 

5820. 경주

https://www.acmicpc.net/problem/5820

풀이는 원래 알고 있었는데 스트릭 초기화가 20분 남은 시점에서 풀게 이거밖에 안 보여서 짰다

센트로이드 기본 문제이다. 센트로이드 $c$를 잡고 dfs를 해서 각 정점까지 거리를 구해주고, $c$와 인접한 정점 각 정점 $v$에 대해서 $c$에서 $x$로 가기 위해 $v$를 꼭 거쳐야 한다면 $x$를 $v$번 그룹이라 하자.

 

그러면 각 정점 $v$에 대해서 $v$와 다른 그룹에 속하는 $x$에 대해 $dis(c, v)=L-dis(c, x)$인 $x$들만 고려해주면 되는데, 이는 set, map 등의 자료구조로 풀 수 있다.

 

이렇게 한 뒤 센트로이드를 트리에서 제거하고, 분해된 서브트리들에 대해서도 재귀적으로 작업을 시행하면 된다.

 

28105. 분탕

https://www.acmicpc.net/problem/28105

교환되는 쌍을 $[l_1, r_1], \cdots [l_n, r_n]$이라 하자. ($l_i \le l_j$ iff $i \le j$)

Dilworth's theorem에 의해 LDS의 길이가 2인 수열은 2개의 increasing chain으로 분해된다. 만약 $i < j$일 때 $l_i > l_j$인 $(i, j)$가 있다 가정하면, $l_i, l_j, r_i, r_j$ 위치의 네 수는 감소하고, 2개의 chain으로 분해하는 것이 불가능하다. 따라서 $i<j$이면 $l_i < l_j, r_i < r_j$이다.

 

$(l, r)$ 쌍들이 있을 때, 각 $i$에 대해 $i=l_x$인 $x$가 존재한다면 $i$에 문자 L을 쓰고, 아니라면 R을 쓰자. L $n$개와 R $n$개로 이루어진 문자열이 주어졌을 때 $(l, r)$ 순서쌍들을 찾는 방법은 앞의 L부터 보면서 가장 가까운 R 문자와 대응시켜 순서쌍을 만드는 것이다. 해가 존재하면 반드시 이런 형태의 해임을 보일 수 있다. 따라서 LR로 이루어진 문자열과 돌의 수열이 일대일대응되므로, LR로 이루어진 문자열의 수만 세도 된다.

 

이제 문제를 해결하자. 편의상 $X<Y$라 하자. 그러면 $X$번 위치에는 L이, $Y$번 위치에는 R이 써있어야 한다. $[X+1, Y-1]$ 구간에 있는 R 문자의 수를 $x$개라 하자. 그러면 $[1, X-1]$ 구간에는 L이 R보다 정확히 $x$개 많아야 한다. 만약 $x$개보다 많다면 $Y$번째 위치의 R이 $X$ 앞의 L에게 대응되고, 반대의 경우는 $X$위치의 L이 $Y$ 앞의 R과 대응될 것이다.

 

따라서 경우의 수는 $[1, X-1]$에 L과 R을 적절히(임의의 시점에서 등장한 L 수가 R 수보다 같거나 많도록) 배치하는 방법, $[Y+1, N]$에 L과 R을 배치하는 방법, $[X+1, Y-1]$에 $x$개의 R, $Y-X-1-x$개의 L을 배치하는 방법의 곱이다. 이를 $x$를 0부터 $Y-X-1$까지 증가시키며 더하면 된다.

 

31512. Matrix Fraud

https://www.acmicpc.net/problem/31512

주어진 조건으로부터 다음 사실을 관찰할 수 있다.

• 각 column에 대해 1은 연속해서 등장한다.
• 각 column에 대해 1이 등장하는 위치를 구간 $[l_i, r_i]$로 표현하면, $l$과 $r$ 모두 단조증가하여야 한다.

즉, matrix $A$가 조건을 만족한다면, $A$의 transpose도 조건을 만족한다.

따라서 우리는 $R \ge C$임을 가정할 수 있고, $dp[i][j][k]$를 $i$ row에서 $s_i=j, e_i=k$를 만족하도록 $1, 2, \cdots, i$ row를 색칠하는 방법으로 정의하면 누적합 등의 전처리로 $dp$테이블을 $O(RC^2)$에 채울 수 있다.

 

어떻게 보면 시간복잡도에 루트가 들어가서 느릴 것 같지만 생각보다 빠르게 돌았다.

 

17670. 난

https://www.acmicpc.net/problem/17670

$i$를 1부터 $N$까지 증가시키며 다음을 반복한다.

• 앞에서부터 먹는다고 가정할 때, 골라지지 않은 사람 중 만족도의 $i/N$ 만큼을 먹기 위한 양이 최소인 사람을 고른다.
• 고른 사람에게 $i/N$을 먹기 위한 최소 위치까지 잘라서 준다.

풀이의 정당성은 $N$에 대한 귀납법으로 쉽게 보일 수 있다.

 

이 외에도 다양한 방법이 있지만, 출력의 $B \le 10^9$ 조건을 만족할 방법을 찾기는 힘들다.

 

31442. 좋은 수열

https://www.acmicpc.net/problem/31442

정말 재미있고 신기한 문제이다. 개인적으로 투스텝, 인터렉티브 유형이 아닌 문제 중 aliens, split the attractions 다음으로 재밌는 것 같다.

일단 관찰이 많이 필요하다. 우선 한 쿼리에 대해 $O(N)$에 해결하는 방법을 찾자.

 

우선 모든 1들이 전부 합쳐져야 $N$이 등장하므로, 주어진 연산에서 $z=0$이어야 한다.

 

수열에서 1 이상의 수 개수를 $A$개, 0의 수를 $B$개라 하면 한 번의 연산에서 확정적으로 0이 하나 제거되니 $B$는 하나 감소하고, 총 두 개의 수가 제거되므로 $A$나 $B$ 중에서 하나가 감소한다. 이때 최종 결과는 $[N, 0]$, $[0, N]$이 되어야 하는데, 두 경우 모두 $A=B=0$이다. 따라서 각 연산마다 $A$와 $B$는 반드시 1씩 줄어들어야 한다. 따라서 $x, y$가 $x+y$로 합쳐지는 과정에서 $A$가 줄어들어야 하고, 연산 실행 전 $x$와 $y$는 모두 1 이상이어야 한다는 것을 알 수 있다.

 

1 이상인 원소를 그냥 다 1로 쓰자. 그러면 0과 1이 $N$개 있는 문자열에서 다음 두 연산을 합하여 총 $N-1$번 사용할 수 있는지 묻는 문제가 된다.

• 수열에서 $1, 1, 0, 0$을 제거하고 $0, 1$로 바꾼다.
• 수열에서 $1, 1, 0, 1$을 제거하고 $1, 1$로 바꾼다.

$N-1$번 사용하는 것이 가능한지의 여부는 $N-2$번 사용하여 수열을 $[1, 1, 0, 0]$으로 만들 수 있는 것과 동치이므로, 이에 대해 생각하자.

 

귀납적으로 생각해 보면 다음 사실을 관찰할 수 있다.

• 1을 +1로, 0을 -1로 생각하면 누적합 배열이 마지막 원소를 제외하고는 항상 양수이다.

이제 편의상 1을 +1로 생각하여 +로, 0을 -1로 생각하여 -로 쓰겠다.

 

수열이 조건을 만족한다면, 수열에서 $[+, +, -, -]$, $[+, +, -, +]$ 부분수열이 등장하는 가장 앞 위치를 찾아 연산을 시행한 수열도 조건을 만족한다. 이 역시 귀납적으로 증명할 수 있다.

 

주어진 수열의 누적합 배열이 처음, 마지막을 제외하고 전부 2 이상이었다 가정하자. 이러면 마지막으로 등장한 -의 수가 짝수일 경우 가능, 그렇지 않을 경우 불가능하다.

 

누적합 배열에 1이 있었을 경우도 사실 비슷하다. 누적합 배열의 1 앞에 있는 -의 수가 전부 홀수개일 경우 가능, 그렇지 않을 경우 불가능하다.

 

이를 다음 값을 저장하는 세그먼트 트리를 사용하면 반전 쿼리를 빠르게 처리할 수 있다.

구간을 $[l, r]$이라 하면,

• $sum$: 구간 원소의 합
• $up$: $[l, i]$ 부분수열의 합 중 가장 큰 값
• $down$: $[l, i]$ 부분수열의 합 중 가장 작은 값
• $chk1$: +가 연속해서 등장하는 maximal한 구간들 중 끝점을 포함하지 않는 구간만 고려하자. 이 +들의 끝점 위치의 누적합이 $up$과 같고 +의 수가 짝수개였다면 false, 아니면 true
• $chk2$: $chk1$과 반대로 정의된다
• $chk3$: 구간의 수가 모두 같으면 true, 아니면 false이다

 

구현이 좀 복잡하다.

 

31999. 캐시 메모리 정하기

내가 ai4youej님과 낸 문제이다. 지문은 ai4youej님이 써주셨다.

https://www.acmicpc.net/problem/31999

일단 각 수를 호출하기 위해 기본적으로 $Y$의 비용이 들고, 캐시 메모리에 저장되어 있다면 $Y-X$만큼 할인받는다. 이 값에 대해서 생각하자.

 

한 $l$에 대해서 $X_k$를 $[l, k]$ 구간을 캐시에 저장했을 때 할인되는 값과 $[l, k-1]$구간을 캐시에 저장했을 때 할인되는 값의 차라 하자. 이러면 $X_k$는 다음을 만족한다.

• $A_k$가 $[l, k]$에서 한번만 등장한다면 $(Y-X)B_{A_k}-K$
• 아닐 경우, $-K$

$l$이 하나 줄어들 때 딱 하나의 $X_k$만 첫 번째 경우에서 두 번째 경우로 바뀐다. $l$을 감소시키며 이 변화를 찾아서 바꿔주고 prefix sum의 maximum을 구하는 것을 반복하면 되는데, 금광세그로 가능하다.

 

16232. 없던 일처럼

https://www.acmicpc.net/problem/16232

$X$개의 값들에 대해 전부 $Y$개의 쿼리들($k$보다 작으면 $a$, 아니면 $b$를 더하는 것)을 처리하는 경우, 세그먼트 트리를 사용해 $O(X+Y \lg X)$ 시간에 풀 수 있다.

$i$번째로 출력해야 하는 것은 $0$에 $[1, i)$ 쿼리를 처리한 값에 $(i, N]$ 쿼리를 처리하면 나오는 값이다. 0에 prefix 쿼리들을 시행하면 무엇이 되는지는 $O(N)$에 구할 수 있고, 그 값들에 각각의 suffix 쿼리를 시행하면 무슨 값이 되는지는 분할정복을 통해 구할 수 있다. 전체 시간복잡도는 $O(N \lg ^2 N)$이다.

 

31967. 오름차순

https://www.acmicpc.net/problem/31967

일단 $[l, r]$ 구간을 오름차순으로 만들기 위한 최소 개수의 연산들은 $[l-1, r]$ 구간을 오름차순으로 만들기 위한 최선의 연산들에 포함된다는 것을 알 수 있다. 

또한 주어진 배열을 구간들로 분할할 수 있는데, $X_i < X_{i+1}$이면 $i$와 $i+1$을 다른 구간에 속하도록 하자. 이렇게 구간을 나누게 되면, 배열 맨 앞에 한 수가 추가되어 오름차순으로 만들기 위해 추가적인 연산을 시행해야 한다면, 같은 구간 안에 있는 수들은 같은 수의 연산만 시행하면 된다.

그래서 배열 앞에 한 수를 추가하며 구간에 연산을 시행하고, 구간이 합쳐지는 것을 스택으로 관리하면 원소에 연산이 몇번 시행되는지 알 수 있다. 이를 레이지세그로 관리하면 된다.

 

18716. Instructions (Easy)

https://www.acmicpc.net/problem/18716

풀이의 수들은 왼쪽이 큰 자리수, 오른쪽이 작은 자리수를 의미하는 것으로 작성되었다.

 

주어진 수에 8을 더해야 하는데, 오른쪽으로 세칸 밀고 1을 더한 후, 왼쪽으로 민다고 생각할 수 있다.

 

1을 더하는 것은 suffix에 연속한 1들을 추출해내고, 그 1들을 모두 0으로 바꾼 후 연속한 1들의 바로 왼쪽에 0을 1로 바꾸면 된다. (100111 -> 101000)

 

연속한 1을 추출하는 것은 suffix의 1들을 제외한 모든 1을 0으로 만들면 되는데, 주어진 수를 1, 2, 4, 8, ...씩 왼쪽으로 시프트하고 오른쪽에 추가된 빈 칸을 전부 1로 채운 뒤 and 연산하면 된다.

이 수를 반전시켜 원래의 수와 and연산하면 1을 지울 수 있다.

 

suffix에 1이 연속해 있는 꼴의 수를 한번 왼쪽으로 시프트한 수와 1과 xor연산을 하면 정확히 1이 더해진 수가 되는데, 이를 이용해 연속한 1들의 왼쪽에 1을 덧붙이는 것을 할 수 있다. (000111 ^ 001110 ^ 1 = 001000)

 

7623. 무한 게임

https://www.acmicpc.net/problem/7623

$D = \{ b-a | a \in A, b \in B\}$라 하자.

집합 $A$에 있는 수를 더하고 $B$에 있는 수를 빼는 것을 번갈아 시행해 나올 수 있는 수는 다음과 같다.

• $a+d_1+d_2 + \cdots + d_k$, $a \in A, d_i \in D$
• $0+d_1+d_2 + \cdots + d_k$, $a \in A, d_i \in D$

첫 번째 경우는 마지막 연산이 $A$를 더하는 것이고, 두 번째 경우는 마지막 연산이 $B$를 빼는 것이다.

 

일단 $D$의 모든 수가 0 이상이거나 0 이하이면 양의 무한대나 음의 무한대 지점으로 가는 것이 불가능하다. 이 경우를 미리 예외처리하자.

$g$를 $D$에 있는 모든 수의 $gcd$라 하자. 그러면 $D$에 있는 수들의 합으로 표현될 수 있는 수들의 집합은 $g$의 배수 집합과 동일하다.

따라서 $A$에 있는 수들 중 $g$로 나눈 나머지가 $1, 2, \cdots, g-1$인 수가 전부 있다면 모든 정수를 만드는 것이 가능하고, 아니라면 불가능하다.

 

30604. 오백나한도

https://www.acmicpc.net/problem/30654

$A_i$ 중 가장 작은 수를 $X$라 하자. $0$ 이상 $X$ 미만인 $i$에 대해 $dist_i$를 $Xd+i$만큼 나한들이 걸을 수 있는 최소 $d$라 하자. 그러면 $dist_0 = 1$이고, 각 $i, j$에 대해 다음이 성립한다.

• $dist_{(i+A_j) \mod X} \le dist_{i}+floor(\frac{i+A_j}{X})$

따라서 다익스트라를 통해 모든 $dist$값을 구할 수 있다. $dist_{K \mod X} \le K/X$라면 해가 있다는 뜻이고, 역추적을 통해 답을 출력하면 된다.

 

역추적이 좀 귀찮다.

 

28402. 두 트리

https://www.acmicpc.net/problem/28402

두 트리에서 아무 정점을 루트로 잡고 dfs를 해 dfs ordering을 구하고, 각 정점 $v$에 대해 $l_iv$를 $i$번 트리에서의 ordering, $r_iv$를 $i$번 트리에서 $v$번 정점의 자손 중 dfs ordering의 최댓값이라 하자.

 

그럼 $v$가 $P_i$에 속한다는 것은 $v \le [l_i1, r_i1]$이라는 것이고, $Q_i$에 속한다는 것은 $v \le [l_i2, r_i2]$라는 것이다. 따라서, 모든 $i$에 대하여 2차원 평면의 $(l_i1, l_i2)$에 가중치 $A_i$의 점을 찍었을 때, $m_i$는 $[l_i1, r_i1] \times [ l_i2, r_i2]$ 사각형에 있는 점들 중 최대 가중치가 된다. 이는 이차원세그, 분할정복 등으로 해결할 수 있다.

 

18830. 하이퍼 수열과 하이퍼 쿼리

https://www.acmicpc.net/problem/18830

11차원 누적합을 짜면 되는 문제인데 누적합 배열을 구하는 것은 sos dp와 똑같이 해줄 수 있고, 쿼리 처리는 imos법과 같은 방식으로 포함배제를 해주면 된다. 주어진 배열의 차원을 $d=11$이라 하면 시간 복잡도는 $O(dN+2^d Q)$이다.

 

13169. Xor of Sums

https://www.acmicpc.net/problem/13169

수들의 집합을 두 개의 집합으로 나누어 그 집합에서의 $S_I$을 전부 구해주자. 첫 번째 집합과 두 번째 집합에서 나올 수 있는 $S_I$들을 담은 집합을 각각 $X$, $Y$라 하자. 그럼 구해야 하는 것은 $X$와 $Y$에서 원소를 하나씩 골라 더해서 만든 수들의 xor 합이 된다.

 

이제 각 비트 $i$에 대해서 $x+y$ ($x \in X, y \in Y$)꼴의 수 중 $i$번 비트가 켜져있는 것의 개수를 구하면 된다.

$X$와 $Y$의 모든 원소에서 $i$번째 비트보다 큰 비트는 모두 0으로 만들게 되면 각 $x \in X$에 대해 $x+y$의 $i$번째 비트가 켜져있게 되는 $y$는 두 개의 서로소인 구간의 합집합으로 나온다. 따라서 처음에 $X$와 $Y$를 정렬해 놓으면 이분탐색을 통해 각 구간에 해당하는 원소가 몇 개 있는지 알 수 있다.

 

19550. 빛의 전사 크리퓨어

https://www.acmicpc.net/problem/19550

한 지점에 빔을 발사하면 원을 그 지점을 기준으로 펼 수 있게 되고, 이러면 끝나는 지점이 가장 앞인 고무줄의 끝점에 다음 빔을 쏘는 것이 최적임을 보일 수 있다. 따라서 각 지점에 대해서 그 지점에 빔을 쏘았을 때 다음으로 쏘는 지점을 계산할 수 있고, 한 지점에서 시작해서 한 바퀴를 돌 때까지 다음 지점을 따라가면 주어진 시작점에 대해 최적해를 구할 수 있다.

모든 시작점에 대해서 다 해봐야 하는데, 이는 sparse table을 사용하여 최적화할 수 있다.

 

32002. Library 3

https://www.acmicpc.net/problem/32002

결국 쿼리 함수가 의미하는 것은 $(A_i, B_i)$들을 전부 간선으로 이었을 때 생기는 그래프에서 (사이클 크기)-1들의 합이 된다.

 

쿼리로 날린 한 $A$에서 두 원소를 교환했을 때 답이 증가한다면 두 원소는 원래의 배열에서 다른 사이클에 있었다는 의미이고, 아니면 같은 사이클에 있었다는 것이 된다. 이를 이용해 모든 원소가 같은 사이클에 오도록 하는 $A$를 구해 주자. 각 $i$에 대해 $i-1$과 $i$를 바꾼 배열을 쿼리로 날려 $i-1$과 $i$가 같은 사이클에 있는지 확인하고, 아니라면 두 수를 교환하면 된다.

 

위 조건을 만족하는 $A$에서 서로 다른 $a, b, c, d$를 잡고 $A$에서 $a$와 $b$를 맞교환, $c$와 $d$를 맞교환한 배열을 쿼리로 날리자. 만약 이 쿼리의 리턴값이 $A$와 같다면 사이클상에서 $a$, $b$를 잇는 직선과 $c$, $d$를 잇는 직선이 교차한다는 것이고, 아니라면 교차하지 않는다는 것이다.

 

이를 이용해 전체 사이클을 구할 수 있다. 처음 $0, 1, 2$는 항상 사이클에서 순서대로 등장하고(방향은 중요하지 않다), 3, 4, ...의 수들은 이분탐색을 통해 들어갈 위치를 구할 수 있다.

 

사이클을 구했다면 처음에 구한 $A$와 비교하여 답을 두 개의 후보로 추릴 수 있고, 쿼리를 넣어 0이 나오는 쪽을 답으로 정하면 된다.