2118 - 두 개의 탑

https://www.acmicpc.net/problem/2118

문제를 푸는 데 가장 크게 작용한 아이디어는

문제의 정답 $\le$ 전체 길이의 합 / 2

라는 사실이었다.

두 지점 사이의 거리는 "$x$ = [a, b) 사이의 부분 합" 라고 할 때 $x$ 와 전체 길이의 합 - $x$ 중 더 작은 것이 된다.
이러한 부분합들 중 가장 큰 것이 문제의 정답이다.

부분합을 구하려는 데 계속 $O(N^2)$ 밖에 안 떠올랐다. 시계방향과 반시계방향 두 경로 중 더 작은것을 선택하는 것 때문이었다.
"문제의 정답 $\le$ 전체 길이의 합 / 2" 이니까 전체 길이 합의 절반보다 작지만 가장 큰 수만 찾으면 되겠구나 생각하고 이진탐색을 궁리해보았다.

계산하고 하는 거리 [a, b) 는 a $\le$ b인 것들만 확인해도 충분했다. 예를 들어, [5, 3) 을 확인하고 싶다면 전체 거리의 합에서 [3, 4) 를 빼면 되기 때문이다. (한쪽 방향에 대해서만 본다면)

시계방향/반시계방향에 대해 위 계산을 범위를 좁혀가면서 했다.

3896 - 소수 사이 수열

에라토스테네스의 체를 써서 2~1299709 까지 소수를 모두 저장하고 입력되는 정수 k에 대해 upper_bound(k) - lower_bound(k) 를 했다.

여기서 말한 upper_bound(k) 는 k와 같거나 k보다 작지 않은 가장 작은 수를 의미하고, lower 는 그 반대이다.

C++ 라이브러리에 있는 std::upper_bound 랑 std::lower_bound 로는 원하는 위치가 나오지를 않았다. 라이브러리 함수는 수가 같은 경우엔 그 다음 iterator를 반환하고 있었다. 그래서 직접 구현했다.

1377 - 버블 소트

문제의 코드는 작은 수를 오른쪽(큰 수)으로 옮겨가면서 정렬이 다 되었을 때 종료한다. 반복문에서 i의 증가 횟수는 이동한 수의 개수와 같은 데,

한 원소가 자신의 위치로 이동하는 최소 거리들 중 최대값과 같다.
다시 말하면, 가장 멀리 (오른쪽으로) 이동하는 원소의 거리이다.

Lower/Upper bound 를 사용하는 이유는 [ 3, 1, 7, 5, 3 ] 의 경우 3이 이동해야 하는 최소거리는 현재 3의 위치마다 다르기 때문이다.

3 1 7 5 3
1 3 3 5 7

첫번째 3의 경우에는 오른쪽으로 1만 이동하면 되고, 마지막 3은 왼쪽으로 2만 이동하면 된다. 첫번째 3의 입장에서는 lower_bound 를, 마지막 3의 입장에서는 upper_bound 를 사용하면 그 거리가 나온다.