2023.08.13 problem solving

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다.

2차 교육

• B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다.
• D: $S < X$ 거나 $S, X$ 의 홀짝성이 다르면 답이 존재하지 않는다. 이 경우들을 예외처리 후 답에 대한 이분탐색을 한다. $i$ 번째 비트를 켠 $a_j$ 의 개수를 $b_i$ 라고 하면, (1) $0 \le b_i \le N$, (2) $S = \sum b_i 2^i$, (3) $b_i$ 의 홀짝성이 $X$ 를 매칭해야 한다 - 라는 세 조건을 $b_i$ 가 만족해야 함을 알 수 있다. $b_i$ 가 고정되면 이것이 답의 후보가 되는지를 그리디하게 알 수 있다. $i$ 감소순으로 보는데, $b_i$ 를 $M$ 미만이 된 숫자들에 우선적으로 몰아주고 필요할 때만 아닌 숫자들에 몰아주는 (이 과정에서 impossible해질수 있음) 방법을 사용하면 된다. $b_i$ 의 "base sequence" $init_i$ = ($x$ 의 $i$ 번째 비트) + 2 ($(S-X)/2$ 의 $i$ 번째 비트) 라 두자. 답이 되는 모든 $b_i$ 수열은 이 수열에 $b_i := b_i - 2, b_{i-1} := b_{i-1} + 4$ 를 반복 적용하면서 구성할 수 있다. $dp[i][j]$ 를 $M$ 미만인 수가 $j$ 개 일 때 $b_{i-1}$ 에 carry되는 수 (4 더해지는) 최솟값 이라고 정의하자. $j \le 5 + \log V$ 인 엔트리만 봐도 됨을 증명 가능하기에 각 TC가 $O(\log^3 V)$ 에 해결
• G: $Z$를 $(i_1, j_1), (i_2, j_2)$ 중 $i_1 \leq i_2, j_1 \leq j_2$, $M_{i_1, j_1} > M_{i_2, j_2}$ 를 만족하는 셀 쌍이라 하고, $W$ 를 $(i_1, j_1), (i_2, j_2)$ 중 $i_1 < i_2, j_1 >j_2$, $M_{i_1, j_1} > M_{i_2, j_2}$ 를 만족하는 셀 쌍이라 하자. $X = Z + W, Y = Z + (\binom{N}{2})^2 - W$ - 고로 $Z, W$ 의 개수를 역산할 수 있다. 숫자들을 $1, 2, \ldots, N^2$ 순으로 배정하는데, 각 숫자가 들어가야 할 위치 후보는 4개이다: $(i, j)$ lexicographically min / max, $(j, i)$ lexicographically min / max. 저기다 배정을 한 후, 해당 배정에 대한 $Z, W$ 의 구간을 구하자. it turns out - 그 구간들의 (2차원으로 봤을 때) cover 가 전체 $Z, W$ 구간과 동일. 그래서 저 4개의 branch중에, 답으로 가는 branch가 있고 그걸 찾아서 반복 배정하면 된다

3차 교육

• C: 단순 구현인데 priority queue 관리하면서 최적화.
• G: 50% 확률로 틀리는 7짜리 반례 패턴을 20번 정도 반복. (i, N + 1 - i) 를 반복해서 찍으면 구간 매칭 문제라고 볼 수 있다, 를 활용하면 좋음
• H: 적절한 케이스워크로 2개의 suffix array에 대한 2d query 문제로 바꿀 수 있고 여기부터는 fenwick tree 선에서 해결.
• K: $lcm(a, b) > n$ 이면 trivial solution이 된다. 아니면 겹치는 위치가 발생할 수 밖에 없는데 이것이 주는 손해의 최소를 DP로 $O(n)$ 에 해결.