푼 것들 중 의미있는(?) 것을 정리했다.
1. 아니메컵 1쿨
딱히 시간을 재고 풀진 않았다. M은 이상한 풀이밖에 생각이 안나서 에디토리얼을 보고 풀었다.
23년에 푼 문제다.
길이, 콜론 개수, 언더바 개수를 세고 그대로 계산하면 된다.
B (BOJ 27311. 치노의 라떼 아트 (Easy))
일단 #의 min x, max x, min y, max y를 가지고 정사각형을 이루는지 확인하자. 그리고 그 내부만 본다고 하자. 배열을 90도씩 돌려가면서 확인하면 일반성을 잃지 않고 '.'이 왼쪽 위에 있다고 가정할 수 있다. 이를 기준으로 (1) '.'이 정사각형을 이루는지, (2) 왼쪽 위에 '.'이 있는지를 확인하면 된다.
C (BOJ 27312. 운영진에게 설정 짜기는 어려워)
\( M \leq N \)이기 때문에 대각선 논법마냥 \( i \)번째 캐릭터와는 \( i \)번째 속성이 다르게 해주면 unique한 설정이 나온다. 쿼리는 \( M \)번 사용하며 \( a_{i} \geq 2 \)이므로 불가능한 경우는 없다.
볼 애니메이션의 개수를 고정하면 그리디한 전략을 쓸 수 있다. 먼저 배열 \( l \)을 오름차순 정렬하고 \( f(x) \) : 애니메이션을 \( x \)개 보는 것이 가능한가? 로 정의하면 \( l_{x-1} \)부터 앞의 k개씩 묶어서 보는 것이 최적임을 알 수 있다.
E (BOJ 27314. 러키☆한별)
만약 한별이가 출구에 가는 도중에 선물을 줄 수 있다면, 출구에서 선물을 줘도 무방하므로 출구까지만 한별이보다 빠르게 도착하거나 동시에 도착하는지만 확인하면 된다. 각 사람마다 출구까지의 최단거리를 bfs로 구하고 각 출구마다 한별이가 받을 수 있는 최대 선물의 개수를 계산하면 된다.
F (BOJ 27315. 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다)
에디토리얼이 있는 문제의 경우 \( D_{i} \)를 \( \left \lceil \frac{D_{i}}{2} \right \rceil \)로 바꿔주면 된다. 에디토리얼을 이해하는데 최소 \( \left \lceil \frac{D_{i}}{2} \right \rceil \)는 있어야 하기 때문이며, 에디토리얼을 이해한다면 아이디어 난이도는 \( \left \lfloor \frac{D_{i}}{2} \right \rfloor \)가 되므로 반드시 풀 수 있는 문제가 된다. \( P_{i} \)는 \( \left \lfloor \frac{P_{i}}{2} \right \rfloor \)로 바꿔주면 된다.
데이터가 있다면 에디토리얼 여부와 무관하게 \( P_{i} \)는 \( -1 \)로 설정하면 된다.
어떤 문제를 풀 수 있다면 \( P_{i} \)가 작은 문제부터 푸는 것이 이득이다. \( HD \)로 풀 수 있는 모든 문제를 pq에 \( P \) 오름차순으로 넣고 한 문제씩 풀면서 WA 개수를 구해주고 \( HD, HP \)를 갱신한 후 새롭게 풀 수 있는 문제를 쭉 넣으면 된다.
\( max(t_{i}) \) = \( m \)이라 하자. \( \text{(능력을 사용하는 횟수)} \) = \( O( \sqrt{m} ) \)임을 관찰한다. 능력을 \( i \)번 사용하는 데에 \( i(i+1) \) 정도의 시간이 들기 때문이다. 따라서 능력 사용 횟수를 state로 넣은 dp를 생각할 수 있다.
\( dp_{i,j} \) : 시각 \( i \)에서 \(j\)번째 능력을 사용할 수 있는 상황일 때 모든 고비를 넘길 수 있는가? 로 정의하면 능력을 사용하지 않는 경우 \( (i+1,j) \)로, 능력을 사용하는 경우 \( (i+2j, j+1) \)로 전이하면 된다. 전이가 가능한지 여부는 prefix sum 등으로 \( O(1) \)에 판별하면 된다. TL이 빡센 문제이다. 재귀로 짰더니 TLE가 나서 반복문으로 고쳤다.
연속해야 하므로 한 시간대에서 시작해서 마법을 몰빵하는 것이 최적이다. 시간대를 \(t = M-1 \)부터 시작하여 최대한 마법을 썼을 때 도달하는 위치를 관리하면서 \( t \)를 줄여가면, 마법의 사용 위치를 슬라이딩 윈도우처럼 최대 \( K \)개를 유지할 수 있다. 구현 시에는 \( i \)번 시간대와 \( i+1 \)번 시간대 사이에 속해있음을 나타내는 \( i \)값을 관리하면서 그 사이가 완벽하게 채워졌으면 \( i \)를 줄이고, \( K \)개가 꽉 찬 경우에는 가장 뒤의 마법을 하나씩 지우는 방식으로 구현할 수 있다.
I (BOJ 27318. 세상에서 가장 달달한 디저트 만들기)
부피가 쉬워보이니 부피부터 고려하자. \( f(n, m) \)을 \( (n,m) \)의 부피라고 정의하면 식을 잘 정리해서 \( (n^3 - 3n(n-2)^2 + 2(n-2)^3)^m = (12n-16)^m \)이 나온다. 이제 g(n,m)을 \( (n,m) \)의 겉넓이라고 정의하면 열심히 구하면 \( (12n-16)g(n,m-1) + (24n-48) - 96(n-1)^m \)이 나온다. 근데 이건 점화식이니까 \( O(m) \)이 걸린다. 이걸 일반항으로 바꾸려면 \( 12n-16 \)을 양변에 나누고 차수를 잘 맞춘다음 묶어주면 된다. 그러면 거듭제곱이 섞인 식이 나오고 이걸 모듈러 역원과 \( O(logN) \) 거듭제곱으로 잘 계산하면 된다.
꽤 오래 걸렸다.. 수학 공부 좀 더 해야겠다.
J (BOJ 27319. 치노의 라떼 아트 (Hard))
일단 \(N\)이 홀수면 당연히 안된다.
선분 \(AB\)로 나뉘었을 때 나뉜 도형이 볼록다각형이어야 하므로 180도보다 큰 각이 없어야 한다. 하지만 180도보다 큰 각이 없다면 꼭지점 \( A \)의 조건을 만족하지 못하므로 180도보다 큰 각이 정확히 하나 있어야 하며 걔가 \( A \)이고, 거기서 \( \frac{N}{2} \)칸 이동한 점이 \( B \)이다. 이제 선분 \(AB\)를 기준으로 나뉜 두 도형이 합동인지 확인하면 되는데, 합동의 정의를 충실히 따르면 (대응각, 대응변) 된다. 대응변은 그냥 길이 구하면 되고 대응각은 외적 쓰면 된다.
코코아가 지금 고른 2개의 책을 보더처럼 생각하자. 그러면 책을 1개 고르면 보더가 1개 사라지고 새로운 보더가 생기는 형태이다. 이제 아래와 같은 전략이 성립한다.
- 고를 수 있는 책 중 바로 다음 턴에 없어질 보더에서 가장 가까운 책을 고른다.
직관적으로 될 것처럼 보이고 실제로도 된다. 증명은 에디토리얼에 있다. 증명은 대충 다른 위치를 고르면 반드시 막을 수 있다 정도로 보이는 것 같다.
M (BOJ 27322. 한별이의 퍼펙트 수열과 쿼리 교실)
와 드디어 원본을 아는 제목이 나왔어요
루트질/비트셋으로 뭔가 하다가 세그로 갈아탔더니 세그 20개 쓰는 더러운 풀이만 나와서 에디토리얼 살짝 보고 풀었다. 옛날에 distributing candies 섭태인가? 그거 긁을 때 lazy를 특이하게 썼던 기억이 있는데 약간 그런 느낌이 나는 세그다.
노드 구조체는 다음과 같은 정보를 관리한다.
구간의 최솟값, 최댓값, 합, 값이 10 초과인 수들의 합, 구간의 1~10 / 10 초과 개수
lazy는 \( (l, r, p) \) 형태이며, \( A_{i} := max(l,min(A_{i},r)) + p\) 라는 의미이다. 즉 \([l,r]\) 범위로 제한시킨 후 \( p \)를 더한다. 저게 신기하게도 lazy가 먹히는 구조이다.
이렇게 해주면, 최소 최대는 그냥 lazy에 그대로 대입하면 되고, 구간의 1~10 개수를 아니까 이것들도 lazy에 대입해서 처리해준다. 10을 넘는 경우가 좀 까다로운데 이건 그냥 에디토리얼을 보자.
여기까지 해주면 갱신된 구간의 1~10 / 10 초과 개수, 10 초과인 수들의 합을 알 수 있고 이걸 토대로 전체 합도 계산할 수 있다.
lazy는 [l,r]이 아예 안겹치는 경우, 약간 겹치는 경우로 나눠서 합쳐주면 된다.
이제 쿼리에 따라 저 형태에 맞게 수를 잘 대입해서 갱신하고 구간 쿼리를 날리면 된다.
2. 연습 1
사실 B는 구글링의 도움을 받았다. 문제 하나하나의 퀄리티가 참 좋은 것 같다.
A (BOJ 26034. Keyboard Queries)
1번 쿼리는 결국 팰린드롬의 형태로 \( S_{l} = S_{r} \), \( S_{l+1} = S_{r-1} \), ...를 주는 것이다. 같은 문자를 union-find로 묶는다고 생각하고 접근하자.
먼저 Not equal의 경우부터 보면, 주어진 두 문자열의 길이가 같지 않은 경우뿐이다. 그렇지 않으면 확실하게 다르다고 확신할 수 없다.
따라서 길이가 같은 경우 Equal 또는 Unknown이다. Equal이려면 대응하는 위치가 union-find 상에서 같은 집합에 속해야 한다.
여기까지 보고 관찰을 하나 하자. 그건 바로 의미있는 merge의 횟수가 \( O(N) \)번이라는 것이다. 이건 union-find 특징상 자명하다.
따라서 유파를 관리하면서 1번 쿼리가 주어질 때마다 의미있는 위치만 갱신하면서 뭔가 하면 된다. 의미있는 위치라는 것은 결국 \( l,r \)이 주어졌을 때 팰린드롬 상 대응되면서 유파 집합은 다르게 속해 있는 위치이다. 따라서 세그먼트 트리의 인덱스에 유파 번호를 관리하면서 이분 탐색으로 저걸 만족하는 최초 위치를 찾을 수 있을 것 같다. 이걸 위해서 세그먼트 트리는 정방향/역방향 해싱을 관리해주고, merge 시에는 small to large로 집합 번호를 갱신해주면 \( O(NlogN) \)번 갱신이 일어나므로 \( O(Nlog^2N) \) 이다. 그리고 이분 탐색에 \( O(log^2N) \)이고 merge는 \( O(N) \)번 일어나므로 이것도 \( O(Nlog^2N) \)이다. 따라서 \( O(Nlog^2N) \)에 문제를 풀 수 있으며 TL이 좀 빡빡해서 약간 최적화가 필요하다.
(위의 시간복잡도 분석은 편의상 \( Q=N \)을 가정했다)
System of difference constraints라는 웰노운 문제이다. 백준에서 유명한 문제로는 BOJ 7577이 있다. 7577은 예전에 MITM으로 풀다가 TLE나서 던졌는데 이런 풀이가 있다는게 참 아름다운 것 같다.
일단 System of difference constraints가 뭐냐면, \( S = \text{ \{ } x_{1}, x_{2}, ... , x_{n} \text{ \} } \) 인 집합 \( S \)에 대하여 \( x_{j} - x_{i} \leq W_{k} \) 꼴의 조건이 \( m \)개 주어질 때 이 조건을 모두 만족하는 \( S \)를 찾는 문제이다. 따라서 LP의 일종인데 중요한 건 이걸 최단경로 문제로 환원해서 (벨만 포드로) 풀 수 있다.
\( x_{j} - x_{i} \leq W_{k} \)일 때 \( i \)에서 \( j \)로 가는 가중치 \( W_{k} \)의 간선을 만든다. 그리고 어떤 정점 \( u \)에서 벨만 포드를 쭉 돌리다가 음의 사이클이 나오면 해가 없고, 그렇지 않으면 \( x_{v} = x_{u} + dist_{u,v} \)라고 해주면 해가 된다. 음의 사이클이 있을 때 해가 없는 이유는 임의의 사이클 \( u_{1}, u_{2}, ... , u_{k} \)가 있을 때 저 사이클의 부등식을 싹 합하면 \( \sum W \geq 0 \)이 나와서 합이 음수면 당연히 만족하지 못하기 때문이다. 그게 아니면 \( x_{j} - x_{i} \leq W_{k} \)에서 아까 설정했던 \( x_{v} = x_{u} + dist_{u,v} \)를 대입해보면 \( dist_{u,j} \leq dist_{u,i} + W_{k} \)이 나오고 이건 우리가 설정한 간선 가중치 때문에(i에서 j로 가중치 W로 이음) 자명한 부등식이다.
여기까지가 사전지식(?)이고 사실 발상만 본다면 충분히 생각은 할만하다고 느꼈다. 암튼 그래서 원래 문제를 풀려면 일단 prefix sum을 변수로 지정한 뒤 (1) binary array의 prefix sum 상 자명한 부등식(인접 차이 1 이하), (2) 입력으로 준 쿼리를 풀어서 나온 부등식 요 2개를 설정해서 위 문제를 풀어주면 된다.
참고로 7577은 조건이 equal로 바뀐 것뿐이라서 거의 똑같이 풀린다.
C (BOJ 26415. Ghost)
이런 문제는 참 생각하기가 어려운 것 같다.
일단 40점 풀이를 알아보자. (40점 : 사실상 루트 빼고 이진 트리) 새로운 트리는 그냥 입력의 트리를 쓰자. \( |X_{i}| \leq 5 \)의 경우 그냥 루트를 제외하고 부모 간선을 저장한 뒤, 외곽 순환 도로끼리 이어줘야 하므로 순서상 인접한 리프 경로의 \( X \)에 두 리프를 넣어주면 된다. 이러면 어떤 정점의 degree가 3일 때 \( |X_{i}| = 5 \)로 최대이다. 문제는 이걸 \( |X_{i}| \leq 4 \)로 줄이는 게 참 어렵다. 아예 다른 접근이 필요한데, 일단 \( K \leq 4N \) 조건을 지금 전혀 활용하지 못하고 있으므로 트리를 새롭게 구성해주도록 하자. dfs를 하면서 리프부터 트리를 구성하면서 트리dp 하듯이 결과를 합쳐줄 것이다. 즉 dp의 결과가 트리라고 생각하자. \( dp_{i} : \) \(i\)를 루트로 하는 서브트리에 대하여 새로운 트리를 구성하며, \( X_{i} \)는 서브트리의 가장 왼쪽 리프, 가장 오른쪽 리프를 및 자기 자신을 담고 있음이 보장됨
이렇게 정의한 다음, 만약 자식이 \( v_{1}, v_{2} \)로 2개라면 적절히 합칠 수 있다. 그 적절히는 아래 그림과 같다.
암튼 저렇게 구성을 해주면 총 4개의 노드를 추가해서 자식을 합쳐줄 수 있다. 따라서 \( 4N \) 제한에 거의 딱 맞을 것이라고 예상할 수 있다. 그리고 생각해보면 저 전략을 일반적인 트리에서도 그냥 자식을 여러 번 합쳐준다고 생각하면 성립하게 된다. 따라서 그냥 이 풀이로 100점이 나온다.
꽤 어려웠다.
다음과 같은 사실을 관찰한다: E = 1을 제외하면 (리프를 고를 수 있다면) 리프만 고르는 것이 최적이다. 리프를 고르지 않는 최적해가 있다고 가정하면, 리프가 아닌 선택된 정점을 리프쪽으로 내리면 무조건 손해가 아니기 때문.
따라서 루트를 고정한다면 다음과 같은 풀이를 낼 수 있다.
아직 선택되지 않는 리프 노드 중 먹을 수 있는 가중치가 최대인 노드를 선택하고, 그 경로 상 남아있는 가중치를 지운다.
이는 euler tour + 레이지로 \( O(NlogN) \)에 풀 수 있다. 이러면 모든 정점을 루트로 하는 후보에 대해 계산해서 \( O(N^2logN) \)에 문제를 풀 수 있게 된다.
하지만 여기서 추가적으로 필요한 관찰이 있다. 바로 최적해에서 가능한 루트는 E = 2일 때의 최적해에서 고른 리프 정점 중 하나라는 것이다. 이건 귀납적으로 보일 수 있는데, \( k \leq 2 \)일 때 E = \( k+1 \)일 때의 최적해와 E = \( k \)일 때의 최적해를 고려해보자. 만약 두 최적해가 초기 상태로 할 수 있는 루트가 동일하다면 자명하게 E = \( k \)의 최적해에서 E = \( k+1 \)의 최적해로 갈 수 있다. 초기 루트가 동일하다는 것은, E = \( k \)일 때 선택된 정점 \( u_{1}, v_{1} \), E = \( k+1 \)일 때 선택된 정점 \( u_{2}, v_{2} \)에 대하여 \(u_{1} - v_{1} \) 경로와 \(u_{2} - v_{2} \) 사이에 공유되는 정점이 있도록 \( u_{1}, v_{1}, u_{2}, v_{2} \)를 적절히 고를 수 있다는 뜻이다. 만약 그렇게 고를 수 없다면, E = \( k+1 \)일 때의 최적해에서 고른 정점 중 E = \( k \)의 최적해에서 새롭게 선택했을 때 가중치가 가장 큰 정점을 가지고 오자. 그럼 E = \( k+1 \)일 때의 최적해도 결국 어떤 리프를 루트로 해서 골라서 나온 최적해일테고, 거기서 E = \( k \)의 최적해와 정점을 볼 때 경로가 하나도 겹치지 않은 것이므로 E = \( k \)가 E = \( k+1 \)에서 하나를 가져오면 E = \( k+1 \)이 마지막으로 먹은 가중치 이상을 먹게 되고 따라서 절대 손해를 보지 않는다.
따라서 E = 1,2인 문제를 따로 해결하고 E = 2일 때 최적인 리프 아무거나를 가지고 계산해주면 \( O(NlogN) \)에 풀 수 있다.
센트로이드로 풀 수 있다는데 왜 되는지 잘 모르겠다.. 다음에? 알아볼 예정
E (BOJ 19614. Travelling Salesperson)
일단 답은 반드시 \( n \)일거라고 찍고 시작했다.
처음엔 컴포넌트 한개만 남긴다음 BCC로 묶고 BCC를 2개 이하로 남긴 다음 BCC 내부에서 사이클을 만드는 방식으로 접근했으나 너무 복잡해지고 불가능한 경우가 있을 것 같아서 버렸다. 두번째로 BCC 대신 클리크를 잘 관리하는 방법을 고민해봤고 답을 발견한 줄 알았으나 생각을 잘못했다는 사실을 알게 되었다.
그래서 결론만 말하자면, IOI'23 Longest Trip 섭태 풀듯이 풀면 된다. 덱에서 path를 관리할건데, front에는 R 간선으로만, back에는 B 간선으로만 이을 것이다. 현재 덱에 front에 \( u \), back에 \( v \)가 있고 정점 \( w \)를 경로에 추가한다고 하자. 만약 \( u-w \) 간선이 R이라면 front에, \( v-w \) 간선이 B라면 back에 넣는다. 그렇지 않으면 \( u-w \) 간선이 B이고 \( v-w \) 간선이 R인 상황일텐데, 이 경우 \( u-v \)가 R이면 front에 \( u, v, w \) 순서로, B이면 back에 \( v, u, w \) 순서대로 넣는다. 이렇게 하면 반드시 길이 \( n \)인 경로를 만들 수 있다.
여기서 \( w \)가 항상 front 또는 back에 위치하므로, 어떤 \( i \)를 시작점으로 하고 싶다면 \( i \)를 마지막으로 추가하면 된다.
3. 연습 2 (CF R980 div1 virtual)
A
배열의 크기가 2니까 pair 취급하자. 같은 pair끼리는 inversion을 바꿀 수 없다. 어떤 pair를 배치하는 순간 배치하지 않은 pair에 대해 inversion 값이 고정된다. 이때 기여하는 값을 생각해보면 자기보다 작은 값이 적을수록 이득이다. 따라서 작은 수가 존재하는 pair가 먼저 배치되어야 이득이다. 따라서 (min, max)를 비교하여 오름차순으로 정렬해주면 된다.
B
\( b_{i} \leq i \)인데 skip하면 개손해다. 점수도 못먹고 앞으로 가기 때문이다. 따라서 \( b_{i} \)는 최대한 뒤로 갈 때 사용해야 한다. 또한 최대한 뒤로 갔을 때의 위치를 \( j \)라고 하면, \( j \) 이후로는 앞에서 먹지 않은 값들을 쭉 먹으면서 돌아오는 것이 최적이다. 이는 마지막 위치에만 영향을 받으므로 어떤 위치까지 가는 데 드는 최소 비용을 구해야 한다고 생각할 수 있다. 따라서 적절히 그래프로 환원한 뒤 다익스트라를 이용해 문제를 해결할 수 있다.
C (upsolved)
어떻게든 kmp까진 접근했지만 의문사당해서 시간 안에 풀지 못했다. 알고보니 사실 그냥 내가 생각을 잘못했다.
일단 문제 상황만 보면 막막하다. 뭔가 \( k \)의 배수 조건에서 힌트를 얻어보자. 쉽게 \( k = 2 \)인 경우를 생각해보면, 뭔가 이분 그래프와 관련이 있다는 사실을 알 수 있다. 생각해보면 사이클이 다 2의 배수이므로 이분 그래프 형태의 SCC 2개가 주어지는 것이다. 따라서 간선을 이으면서 이분 그래프를 유지할 수 있으면 되겠다는 사실을 알 수 있다. 이걸 좀 더 구체적으로 보면, 새롭게 추가되는 간선에 의해 parity에 영향을 주지 않으면 된다. 그러면 그래프를 아무리 왔다갔다 해도 state가 일정하기 때문에 가능하다는 사실을 알 수 있다.
이 풀이를 일반화시키자. 사이클이 다 \( k \)의 배수이므로 한 위치를 기준으로 어떤 정점까지 도달할 때 \( \text{ (이동 거리) } \text{mod } k \)가 일정하다. 이걸 간선을 이은 상황에서도 유지하고 싶다고 생각할 수 있다. 주어진 SCC를 각각 \( A, B \) 라고 하고 각각 한 정점에 대해 \(0\)부터 \(k-1\)까지의 색으로 k-coloring을 하자. \( A \)의 \(out\)에서 \( B \)의 \( in \)으로 갈 때 \(out\)의 color가 \(c\)였다면 \(in\)의 color는 \(c+1 \text{ mod } k \)여야 한다. 또한 \( B \)의 \(out\)에서 \( A \)의 \( in \)으로 갈 때도 마찬가지다. 이제 이게 되는지 확인해주면 되는데, 만약 color가 고정된 상황에서는 그냥 cnt 배열이 일치하는지 확인하면 된다. 하지만 생각해보면 color가 1씩 shift될 수 있으므로 이걸 kmp로 확인해줘야 한다.
후기) C를 못 푼것이 너무 아쉽다. 그런데 div1 only의 점수가 짜다고 알고 있었는데 이래도 2200 주는거 보고 좀 놀랐다. 그럼 평소에 div2, div1+2에서 1900만 먹는 나는 뭐가 되는거지
4.
랜덤 마라톤 하고 할 게 없어서 1차 선발 4번을 업솔빙했다. 분명 처음 풀이의 방향성은 내가 푼 XOR MST 별해처럼 그룹을 잘 묶어가면서 관리하는 거였는데 몇 시간 동안 디버깅을 거쳐가면서 풀이가 개조되더니 결국 꽤 다른? 풀이가 됐다. 별로 좋은 풀이는 아닌 것 같아서 설명은 생략.
다른 사람들 풀이를 대충 봤는데 멋진 풀이가 많았다. 저런 생각은 어케하지.. 아직 많이 부족한 것 같다.
5. 월간 향유회 2025. 01.
향유회는 항상 문제 퀄이 좋은 것 같다.
\(a\)가 고정일 때 \( a \oplus b = K \)인 \(b\)는 \( a \oplus K \)로 유일하다. 따라서 둘 중 하나를 고른다면 다른 한 쪽은 고를 수 없는 관계이다. \( i \)를 작은 수부터 늘려나가면서 \(A\)에 추가하고 \( i \oplus K \)를 못 넣게 하면 된다.
B (BOJ 33273. \( \textbf{multiple}\text{ sequence} \))
제한을 보면 어렵지 않게 dp를 떠올릴 수 있다. \( dp_{i,j} : \) 지금까지 채운 길이가 \( i \)이고 지금부터 채울 정수는 \( x_{j} \)일 때 가능한 최대 합 으로 정의하자. 이때 문제점은 \( x_{j} \)를 몇 개 골라야 할지가 고정되지 않았다는 점 때문에 전이할 상태가 대충 \( O(NM) \)개라는 점이다. 따라서 관찰이 필요하다. 우리가 원하는 것은 최대 합이기 때문에, 큰 수를 많이 넣을수록 최적이다. 배수 관계가 유지되어야 하므로 거꾸로 큰 수에서 작은 수로 배열을 채워나가자. 그러면 자명하게 \( x_{j} \)는 가능한 한 많이 넣어야 한다. \( x_{j} \) 다음에 넣을 수는 \(x_{j} \)보다 작기 때문이다. 따라서 전이할 상태가 \( O(M) \)개로 줄어들며, \( O(NM^2) \)에 풀 수 있다. 실제로는 약수 관계일 때만 전이하므로 상수는 아주 작다. (아마 약수의 개수는 \( O(x^\frac{1}{3}) \)이었던 걸로 기억한다. 아님 말고)
제목이 현실적이다.
아마 ad-hoc하게 풀어도 될텐데, 나는 머리가 안되서 분할 정복? 으로 풀었다.
\( f(N) \) 이 \( N * N \) board에서 최적해를 가져다주는 함수라 치자. 그러면 \( a + b = N \)일 때, \( f(N) \)을 \( f(a) \)와 \( f(b) \)를 이용해 구성할 수 있다. \( [0,a-1] * [0,a-1] \)에 \( f(a) \)를 채우고, \( [a,N-1] * [a,N-1] \)에 \( f(b) \)를 채운 뒤 \( [a,N-1] * [a,N-1] \)의 주대각선에 \( mex(f(a)) \)를 더하면 된다. 이제 \( N \)을 이진수 표현을 고려하면 크기를 절반 이하로 줄일 수 있으므로 대충 풀 수 있다. (사실 절반 이하로 줄일 필요가 있는지는 모르겠다. 어차피 한 성분은 한번만 방문해서..)
D (BOJ 33275. 소소고금)
제목의 의미가 궁금한데 모르겠다.
버츄얼 돌 때는 modular가 \( k \)라서 2의 역원이 없을 수도 있어서 못 풀었는데, 생각해보니까 \( k \)를 홀수로 만들고 풀면 된다!
일단 \( S[l..r] \)이 \( k \)의 배수일 조건을 생각해보자.(1-indexed) \( P_{i} \)를 \( S[1..i] \)를 이진수로 표현한 것이라고 할 때 \( P_{r} - 2^{r-l+1}P_{l-1} \equiv 0 \text{ (mod } k \text{)} \)이면 된다. \( 2^x \)의 역원이 있다 치고 정리하면 \( P_{r}2^{-r} \equiv P_{l-1}2^{-(l-1)} \text{ (mod } k \text{)} \)니까 충분히 counting 가능한 꼴이다. \( 2^n \)의 역원을 \( O(k) \)에 구할 수 있으니까 \( O(n+k) \)에 역원 전처리하고 카운팅하면 풀 수 있다. 문제는 \( k \)가 짝수인 경우인데, 이 경우 \( k = 2^xk' \)라 하고 생각해보면 \( k' \)의 배수면서 뒤에 0이 \( x \)개 이상 붙어있으면 된다. 따라서 각 인덱스에서 연속한 0의 개수를 구해놓고 케이스를 조금 나누면 풀 수 있다.
\( A, C \) 횟수에 제한이 없다고 생각하고 생각하자. 그럼 그냥 \( A \) 연산을 \( 2N-2 \)번 써서 \( B \)에다가 \( A_{1} \oplus A_{N}, A_{2} \oplus A_{N}, \text{ ... }, A_{N-1} \oplus A_{N} \)을 저장해놓고 \( Q \)에 \( k = N-1 \)로 날려서 풀 수 있다. 저렇게 하면 개수가 홀수인 부분 수열은 모두 XOR로 표현할 수 없고, 짝수인 부분 수열은 모두 XOR로 표현할 수 있기 때문이다. 하지만 이 풀이를 2번 쓰면 제한에 걸린다.
위 풀이가 \(C\)를 전혀 사용하지 않았으니 이번엔 다른 풀이를 생각해보자. 일단 \( A \)는 \( N \)번 써서 \( B \)에다가 그냥 배열 \(A\)를 복사한다. 여기서 이 문제의 독특한 제한을 이용해야 한다. 수열 \( A \)의 원소는 5억 이하인데, \( C \) 연산으로 날릴 수 있는 \( x \)의 범위는 21억 정도다. 30번, 29번 비트가 딱 비어있으니 충분히 의도된 사항이라고 생각할 수 있다. 이걸 이용하자.
연산이 xor이기 때문에, 최상위 비트가 클수록 최종 결과도 크다. 이 점을 이용하면 반드시 짝수개를 골랐을 때만 30번, 29번 비트가 켜지도록 잘 설정하자는 전략을 세울 수 있다. \( B_{N+1} \)에다가 \( 2^{30}, 2^{29} \)를 xor시켜 \( 2^{30}+2^{29} \)로 만들자. (풀이 쓰면서 알았는데, 나는 \( 2^{30}, 2^{29} \) 쿼리 따로 날렸는데 같이 날리면 1번만 날려도 된다.) 그리고 \( B_{i} \)에는 (\(1 \leq i \leq N \)) \( 2^{29} \)만 xor시키자. 그러면 최적해는 반드시 30번 비트가 켜져 있어야 하므로 \( B_{N+1} \)을 포함하며, 29번 비트도 켜져 있어야 하므로 \( B_{N+1} \)를 제외하면 \( B_{i} \)는 짝수 번 골라야 한다. (\( B_{N+1} \)에서 29번 비트를 켰고, 29번 비트는 모든 위치에서 켜져 있으므로 이 상태에서 짝수번 골라야 켜짐) 따라서 이 상태로 \( Q \)에 \( k = N+1 \)로 날리면 풀 수 있다. 하지만 이 풀이도 2번 쓰면 제한에 걸린다.
지금까지의 풀이를 정리하면,
- 1번 풀이는 \(A\)는 \( 2N-2 \)번, \(C\)는 0번, \( k = N-1 \)
- 2번 풀이는 \(A\)는 \(N\)번, \(C\)는 \(N+2\)번, \(k = N+1\)
정말 놀랍게도, 두 풀이를 같이 쓰면 제한에 딱 맞는다. 따라서 첫번째 풀이에서는 1번 풀이를, 두번째 풀이에서는 2번 풀이를 쓰면 풀 수 있다.
'일기' 카테고리의 다른 글
| 1월 PS (2) (1) | 2025.01.31 |
|---|---|
| 2025 국제정보올림피아드 대표학생 선발고사 1차 후기 (2) | 2025.01.27 |
| 1월 PS (1) (4) | 2025.01.25 |
| solved.ac Ruby V (2) | 2025.01.19 |
| 재미있는 문제 (0) | 2025.01.13 |
