https://atcoder.jp/contests/agc038/tasks
ABCDEF 6문제 중 ABD 3문제를 풀었다. 레이팅이 오르긴 했지만, C를 못 푼 것이 아쉽다. 정수론이라서 풀려는 시도조차 안 했는데, 쉬운 문제였다....
A. 01 Matrix
쉬운 문제였지만 나는 모르겠어서 B를 먼저 풀었다.
위 왼쪽의 A*B크기 직사각형과 아래 오른쪽의 (H-A)*(W-B)크기 직사각형은 0으로 채우고 나머지는 1로 채우면 된다.
B. Sorting a Segment
주어진 수열에서, 길이 $K$의 구간을 선택해서 그 구간을 정렬한다. 이 연산을 1번만 시행하여 얻을 수 있는 결과를 구하는 문제다.
위치 $i$에 이 연산을 시행하면 $[i, i+K-1]$ 구간이 정렬된다고 하자.
$i$에 연산을 시행한 것과 $j$에 연산을 시행한 결과가 같으려면 $(i < j)$
1. $j\leq i+K-1$(구간이 겹친다) : $[i, j+K-1]$ 구간에서 작은 원소들은 $[i, j-1]$에 정렬된 순서로 있고, 큰 원소들은 $[i+K, j+K-1]$에 정렬된 순서로 있다.
2. $j > i+K-1$(구간이 겹치지 않는다) $[i, i+K-1]$과 $[j, j+K-1]$ 구간이 둘 다 이미 정렬된 상태이다.
1의 경우, $i, i+1, ..., j$에 연산을 시행한 결과는 모두 같다. 따라서 $i$와 $i+1$에 연산을 시행한 결과가 같은지를 모든 $i$에 대해 구하면 된다. 이는 구간 최댓값과 구간 최솟값을 통해 확인할 수 있다.(Segment Tree 또는 Sliding Window 사용)
2의 경우는 1에서 구한 구간 최댓값과 최솟값이 증가하는지 확인하면 된다. 나는 이를 연속한 수의 차이를 구한 후 최솟값이 0보다 큰지 확인하였다. (마찬가지로 Segment Tree 또는 Sliding Window 사용)
C. LCMs
주어진 수열에 대해, $lcm(a_i, a_j)$의 합을 구하는 문제이다. ($0\leq i < j < N$)
$lcm(a_i, a_j) = a_i * a_j / gcd(a_i, a_j)$이므로 각 $k$에 대해, $gcd(a_i, a_j) = k$인 $i, j$의 $a_i * a_j$의 합을 구하자. 이는 에라토스테네스의 체를 응용하여 구할 수 있다.
우선, $0 \leq i < j < N$을 $0\leq i < N, 0\leq j < N$으로 바꾸자. 이렇게 구한 결과에서 $\sum a_i$를 뺀 후 2로 나누면 답이 된다.
배열 s에 대해 s[k] = ($a_i$가 k의 배수인 $a_i$들의 합)이라 하자. 이는 에라토스테네스의 체를 응용하면 구할 수 있다. 각 s[k]의 값들을 제곱하면 ($a_i, a_j$가 k의 배수인 $i, j$에 대해 $a_i*a_j$의 합)이 된다. 여기서 ($gcd(a_i, a_j)$가 k보다 큰 k의 배수인 $i, j$에 대해 $a_i*a_j$의 합)을 빼주면 된다. 마찬가지로 에라토스테네스의 체를 응용하면 구할 수 있다.
에라토스테네스의 체는 시간복잡도가 $O(NloglogN)$이다. 따라서 이 문제 역시 $O(NloglogN)$으로 풀 수 있다.
D. Unique Path
정점이 $N$개이고 간선이 $M$개인 어떠한 연결 그래프에 대한 정보가 $Q$개 주어진다 : $A_i$와 $B_i$를 잇는 경로가 유일하다/2개 이상이다. $C_i$가 0이면 경로가 유일하고, 1이면 2개 이상인 것이다.
이러한 그래프가 존재하는지 판별하는 문제이다.
연결 그래프는, scc들 사이를 트리 형태가 연결한다. 두 정점 사이에 경로가 유일하다는 것은 이 두 정점이 같은 트리부분에 속한다는 것을 의미한다. 따라서 경로가 유일한 $A_i, B_i$를 같은 component로 묶어준다. 같은 component 안에 있는 $A_i, B_i$에 대해 $C_i$가 1이면 이러한 그래프는 없다.
이제 특정 component들 사이를 잇는 경로가 2개 이상 존재하도록 엣지를 이어야 한다. 엣지 개수의 최댓값은 (component의 개수)C2이다. 엣지 개수의 최솟값은 $C_i$가 1인 $i$가 존재하면 $N$, 그렇지 않으면 $N-1$이다. $M$이 엣지 개수의 최솟값과 최댓값 사이인지 판별하면 된다.
한 가지 더 확인할 점은, component가 2개이면서 경로가 2개 이상 존재할 수 없다는 것이다.
위에서 설명한 조건들을 모두 확인해주면, 답을 $O(N)$으로 구할 수 있다.
E. Gachapon
포함 배제의 원리를 이용한 어려운 확률 문제이다. 추가 예정
F. Two Permutations
flow를 이용하는 문제이다. 내가 모르는 알고리즘(flow, string matching 등) 중의 하나였는데, 이 문제를 풀기 위해 공부했다.
두 permuation $P$와 $Q$가 주어진다. 두 permuation $A$와 $B$를 만들어야 한다. 모든 $i$에 대해 $A_i = i$ 또는 $A_i = P_i$여야 하고, $B$에 대해서도 마찬가지로 $B_i = i$ 또는 $B_i = Q_i$여야 한다. 이러한 $A$와 $B$에 대해 $A_i \neq B_i$인 $i$의 개수의 최댓값을 구하자.
permuation $P$를 그래프로 나타내면 여러 사이클들이 생기게 된다. 각 사이클의 원소들은 값이 모두 $P_i$이거나 모두 $i$이다. $i$가 $P$에서 속하는 사이클을 $x(i)$라 하고, $Q$에서 속하는 사이클을 $y(i)$라 하자. $P$의 어떤 사이클 $x$에 대해 원소들의 값이 모두 $i$이면 $v(x) = 0$, 그렇지 않으면 $v(x) = 1$이라 하자. $P$의 어떤 사이클 $y$에 대해서는 반대로 원소들의 값이 모두 $i$이면 $v(y) = 1$, 그렇지 않으면 $v(y) = 0$이라 하자.
이제 $A_i = B_i$인 $i$의 개수를 최소화하자.
1. $P_i= i, Q_i = i$ : $A_i = B_i$이다.
2. 위의 경우에 해당되지 않고 $P_i = i$ : $v(y(i)) = 1$이면 $A_i = B_i$
3. 위의 경우에 해당되지 않고 $Q_i = i$ : $v(x(i)) = 0$이면 $A_i = B_i$
4. 위의 경우에 해당되지 않고 $P_i = Q_i$ : $v(x(i))$와 $v(y(i))$의 값이 다르면 $A_i = B_i$
5. 위의 경우에 해당하지 않음 : $v(x(i)) = 0$이고 $v(y(i)) = 1$이면 $A_i = B_i$
이는 min-cut으로 바꿀 수 있다. 각 $v$에 0이 배정되면 source쪽 component에 연결하고, 1이 배정되면 sink 쪽 component에 연결한다고 생각하면 위 5가지 경우가 각각 간선이 된다.
정점과 간선이 모두 $O(N)$개이고 간선의 최대 유량이 모두 1이므로 Dinic의 알고리즘을 활용하면 $O(N \sqrt{N})$으로 해결할 수 있다.
