79brue의 PS 블로그

BOJ 15986. &+ +&먼저 모든 $A[i] \wedge B[j]$의 합을 구해 보자. $Acnt[x]$를 $A$의 원소들 중 $2^x$의 비트가 $1$인 것의 개수라고 하고, 마찬가지로 $Bcnt[x]$를 정의하자. 비트별로 따로따로 생각하면 답이 $\sum Acnt[i] Bcnt[i] 2^i$임을 쉽게 알 수 있다. 다음으로 모든 $A[i] + B[j]$의 AND 값을 구해 보자. 이것도 역시 비트별로 생각할 것이다. 즉, 모든 $A[i] + B[j]$ 값에 $2^i$의 비트가 켜져 있는지를 검사할 것이다. 먼저 $i=0$일 때부터 시작해 보자. $2^0$의 비트가 켜져 있으려면 $A$는 모두 홀수, $B$는 모두 짝수거나 그 반대여야 한다. $i$가 더 커지는 경우에는 어떻게 검사할 수 있을까..

D5 이상 랜덤 ICPC 문제 10개를 뽑았다.3. Big Brother반평면 교집합 기초 연습문제다. 어딘가에서 라이브러리를 긁어와서 풀었다.7. Fair Distribution$N=1$인 경우는 사전에 N을 출력하고 종료하는 식으로 처리해 주자. $N \ge 2$일 때를 생각해 보자. 각 빌딩의 높이를 $G_i + R_i x$ 꼴로 표현할 수 있다. $x$는 임의의 양의 정수가 될 수 있다. 그런데 모든 빌딩의 높이를 $lcm(R_1, \cdots, R_N)$의 배수만큼 올려놓고 생각할 수 있어서 사실상 $x$는 모든 정수라고 생각해도 문제없다. 일단 처음에 신경써야 할 것은 $gcd(R_1, R_2, \cdots, R_N)$의 값이다. 만약 배분한 $G$값의 합의 차이가 이 $gcd$ 값의 배수가 ..

요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 10개 뽑아 풀어 보았다. 괜찮은 문제도 있었던 반면 풀기 싫은 문제도 많이 있었다. 1. ? 정말 풀기 싫은 문제가 뽑혀서 안 풀고 넘어갔다. 무슨 문제였는지는 공개하지 않는다. 2. Монотонная подпоследовательность 길이가 $n$인 순열 중 LIS나 LDS의 길이 최댓값이 $k$인 것을 찾는 문제이다. Erdos-Szekeres Theorem에 의하면 길이가 $(r-1)(s-1)+1$ 이상인 수열은 길이 $r$의 증가부분수열이나 길이 $s$의 감소부분수열이 있다. $r=s=k+1$을 넣으면, $k^2+1$ 이상의 길이를 가진 수열은 길이 $k+1$ 이상의 IS/DS가 있다. 따라서 $n >..

BOJ 15481. 그래프와 MST 일단 원래 그래프의 MST를 구한다. 그리고 각 간선에 대해, 해당 간선의 양끝점을 잇는 경로에서 가장 큰 가중치를 가지는 간선을 빼 주고 해당 간선을 넣으면 이것이 가장 싼 MST가 된다. 구현은 LCA와 sparse table을 잘 이용하면 HLD + segment tree 없이도 할 수 있다. 시간 복잡도는 $\mathcal{O}(M \log N)$이다. BOJ 30896. 두 팀으로 나누기 두 팀의 $\min(A_i)$와 $\sum B_i$를 각각 $a_1$과 $a_2$, $b_1$과 $b_2$라고 하자. $a_1$과 $a_2$ 중 하나는 $\min_{1 \le i \le N} A_i$이다. WLOG $a_1$이라고 하자. $a_2$를 정하는 방법은 최대 $10..

친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다. BOJ 8473. Monopoly 좌표평면에 $N$개의 점이 주어질 때, 택시 거리가 $c$ 이하인 점들을 간선으로 연결하자. 연결 성분의 개수와 가장 큰 연결성분의 크기를 구하면 된다. 일단 좌표평면을 45도 회전해 생각하면 택시 거리는 체비셰프 거리 $\max(\Delta x, \Delta y)$ 가 된다. 이렇게 변형하면 한 점과 간선으로 직접 연결될 수 있는 점의 영역을 가로/세로 $2c$인 정사각형으로 생각할 수 있다. 이제 이러한 영역 안의 점을 빠르게 찾을 수 있는 방법을 생각해 보자. 위의 좌표 변환을 통해 다음처럼 문제를 변형할 수 있다. 각 점 $(a, b)$가 있고, $x$ 범위가 $[a-c,..

이제 곧 ICPC에 참가해야 하기 때문에 ICPC 입문을 조금 해 보기로 했다. 입문 셋으로 ICPC Seoul Regional 2022를 골랐다. 시간은 딱히 재지 않고 문제를 쉬운 것부터 풀어보았다. J. Parentheses Tree 입력으로 주어지는 괄호 문자열을 파싱하는 문제이다. 스택으로 트리를 만들고 DFS를 돌리는 방법도 있지만 시간이 오래 걸릴 수 있다. 트리를 만드는 과정에서 깊이를 관리하면 상수가 더 작고, 따로 스택을 관리할 필요도 없다(실제 트리의 구조를 만들지 않아도 되므로). 시간 복잡도는 $O(|S|)$이다. F. Frog Jump KOI 2019 중등부 2번 문제에 비슷한 게 있었던 것 같다. 서로 겹치는 구간들의 번호가 인접하기 때문에, 이들을 그룹으로 묶어 준다. 이렇게..

KOI 2023 2차 대회 문제들을 풀었다. 초/중/고등부에서 서로 다른 문제는 7개였다. BOJ 28323. 불안정한 수열 어떤 구간 $[l, r]$에 대해 그 안에 있는 수들의 홀짝성이 모두 같다면 이 구간에서는 수를 최대 하나밖에 뽑을 수 있다. 따라서 홀짝성이 같은 인접한 수들은 하나만 남겨도 문제가 없고, 이렇게 합치고 난 뒤 모든 인접한 수들을 고를 수 있고, 이때 남은 수의 개수가 답이 된다. 즉, 첫 수를 고르고, 그 이후로 홀짝성이 바뀔 때마다 고르는 게 최적이다. BOJ 28324. 스케이트 연습 맨 마지막부터 보면서, $i$번 위치에서 속도는 $i+1$번 위치 속도에서 1 늘릴 수 있으면 늘리고, 아니면 최대 제한으로 설정하는 것이 최적이다. 따라서 단순한 순회 한 번으로 $\math..

최근 몇 달 동안 SciOI 2023 준비 외에는 PS를 거의 안 했는데, 방학을 맞은 김에 재활용으로 문제 몇 개를 풀어보기로 했다. 랜덤 플래티넘 디펜스를 했다. (곧 SciOI 2023 후기가 올라갈 수도 있을 것 같다.) BOJ 4284. A Walk Through the Forest 간단한 다익스트라 + DP 문제다. 집에서부터 시작해서 다익스트라를 돌리고, 집에서 거리가 멀어지는 순으로 정점들을 정렬한 뒤 가능한 가짓수를 DP로 계산하면 된다. 시간 복잡도는 $\mathcal{O}(N+M \log M)$이다. BOJ 29769. 음악회 평균의 최댓값은 수열의 최댓값이다. 즉 수열에서 최댓값이 가장 많이 연속한 구간 중 가장 긴 것 중 가장 왼쪽에 있는 구간을 찾으면 된다. 수열 A 이외에 수열..