2021년 1월 23일 PS일지

1. 간선의 가중치가 음이 아닌 정수인 그래프에서의 최단경로 알고리즘

$0<= W_i <= C$인 그래프
C = 1이면 0/1 BFS를 적용할 수 있다.
0/1 BFS는 위 그래프에서 최단경로를 구할 때 다익스트라보다 나은 시간복잡도를 가진다.
$O(V+E)$
BFS를 돌리는데 가중치가 0인 간선을 이용하여 추가할 때는 큐의 앞에다 놓고, 1인 간선을 이용해 추가할 때는 큐의 뒤에다 놓는다. 시간복잡도가 O(V+E)가 보장되는 이유는, 모든 정점이 큐에 최대 한 번만 들어가고, 각 정점은 큐에서 '차수'만큼 다른 정점을 탐색하기 때문에 합쳤을 때 2E만큼의 시간이 소요되기 때문이다. 
이런 시간복잡도 분석도 재밌다.

이제 0/1 BFS가 아니라, 0~C BFS는 없을까? 이런 의문에 답하는 것이 이 글이다.
길이 C짜리 간선 (C는 2~5 정도로 매우 작다고 하자.)이 있다면 이 간선은 C개의 길이 1짜리 간선으로 나누는 것이다. C-1개의 새로운 정점이 추가될 것이다. 그러면 본 그래프는 정점이 최대 (C-1)E개 추가된 새로운 그래프로 모델링되고, 여기서 0/1 BFS를 적용하면 된다. 이때 시간복잡도는 $(O(C \times V + C \times E)) = O(C \times (V+E))$가 된다.

2. PST 연습문제

어제 풀던거 계속 풉니다
13538 XOR 쿼리

다른 쿼리는 다 쉽게 구현하겠는데 얘는 아무리 고민해도 어렵다.
x, $A_i$의 범위가 모두 1~5e5이므로 쉬울 법도 하건만
제 1안. 일반적인 세그 트리를 만든다. - i 번째 수가 Ai다
제 2안. Value Counting 세그 트리를 만든다. i라는 숫자가 Ai개 있다
두 개 다 가능할 법도 하면서 안된다
x와 xor했을 때 가장 큰 수를 구할 수 있는 적절한 전처리가 무엇일까?

이 글은 수열 Ai가 있을 때 max(Ai ^ X)를 minimize하는 X를 찾는 문제에 대한 설명이다. XOR에서 최대 최소를 찾는게 전혀 와닿지 않아서 위 글을 찾아봤는데, 정말 큰 힌트가 되었다. 물론 문제는 전혀 다르지만 XOR에 대해 깊은 생각을 하는 계기가 되었다.

이제 X와 XOR해서 Maximize될 조건을 생각해보자.
X가 예를 들어 0101110(2)라고 하면
X와 XOR해서 최대가 되려면 최상위 비트는 1, 그다음은 0, 다다음은 1, 이런 수와 XOR해서 결국은
11111 꼴을 만드는게 최상이다.
다시 말하면 1.... 이런 수와 0.... 이런 수중 X와 XOR했을 때 더 큰 수는 뒤와 무관하게 1.....이다. 최상위 비트가 대소를 결정하는 기준이기 때문이다. 

정리하면, X와 XOR했을 때 큰 제 1후보는 X와 최상위 비트가 다른 친구다. 그 중에서 또 제 1후보는 X와 차상위 비트가 다른 친구, 쭉쭉쭉.
그런데 그런 후보가 없다면 어쩔 수 없다. X와 최상위비트를 같은 친구를 고를 수 밖에. 하지만 그 후에도 같은 판단 기준을 적용할 수 있다. 이때 세그의 한 노드가 표현하는 구간을 생각해보자. 

N = 2^10 = 1024라 하면
1번 노드: 0~1023, 2번 노드: 0~511, 3번 노드: 512~1023
이처럼 N이 2의 거듭제곱 꼴일 때는 각 노드가 담당하는 수의 개수가 2의 거듭제곱꼴이 된다.
더 깊게 생각해보면 2번 노드는 1.... (2) , 3번 노드는 0.... (2) 꼴의 수들을 담당하는 것에서
각 노드로 i번째 비트의 켜진 여부를 확인할 수 있다.
높이 i에 있는 노드는(루트는 높이 0) i번째로 큰 비트가 켜져 있는지 확인할 수 있다. 

위 사실들을 전부 이용해 Value Counting Seg의 루트에서부터 내려가면서 X와 XOR했을 때 가장 큰 Value를 구할 수 있다. XOR 쿼리 문제의 남은 모든 쿼리도 Value Counting Seg로 해결할 수 있다.

오늘도 즐 PS!

3. Atcoder ABC 189

재미삼아 참가했다. 레이팅 기대 안함.
9시 시작 대회를 9:53부터 시작함 ㅋㅋ
A,B: Simple
C: 히가큰직 - 복습..이거 푼 사람 정말 대단하다.
D,E:
D: 1-sat dp
E: 오프라인 쿼리 문제, (x,y)를 (x',y')으로 변환할 때 선형결합의 계수를 O(1)에 구할 수 있음.
F: 같이 에디토리얼 봄. f(i>=n)=0이고 거꾸로 채우는 기댓값 dp. suffix sum을 이용함.

앳코더는 복잡한 알고리즘 하나 없이 깔끔하게 참신한 문제를 출제한다는 점에서 정말 대단하다.