Codeforces Round 828 (Div. 3)

Dashboard - Codeforces Round 828 (Div. 3) - Codeforces

 

C

방법 1

 

방법 2 - binary search

 

E1

제한이 다음과 같다.
1 ≤ a < x ≤ c ≤ 10⁵
1 ≤ b < y ≤ d ≤ 10⁵

10⁵ 이하의 자연수는 1초안에 충분히 순회할 수 있으므로(대략 1초에 10⁷ 연산) x를 brute force로 돌리고 y를 O(1) 만에 찾아도 된다.
변수를 바꿔서도 마찬가지.

 

E2

예제로부터 필요한 내용을 관찰하자.
a, b, c, d = 8, 9, 15, 18 라고 하자.

8 < x ≤ 15
9 < y ≤ 18 이므로
x ∈ {9, 10, 11, 12, 13, 14, 15}
y ∈ {10, 11, 12, 13, 14, 15, 16, 17, 18} 을 만족해야 한다.

이제 ab=8*9|xy 를 만족하게 x, y를 골라주자.
72|xy 가 성립하기 위해서는 72의 약수를 x와 y가 적절히 분담해줘야 한다.("72의 약수 d에 대해 d|x 이면 x에서 약수 d가 분담되었다"라고 표현하자.)
즉,
1|x and 72|y
2|x and 36|y
3|x and 24|y
4|x and 18|y
6|x and 12|y
8|x and 9|y
9|x and 8|y
12|x and 6|y
18|x and 4|y
24|x and 3|y
36|x and 2|y
72|x and 1|y
중 어느 하나가 성립해야 한다.

9|x and 8|y 이라는 가정하에 부등호
8 < x ≤ 15
9 < y ≤ 18
를 만족하는 x, y가 존재하는지는 다음과 같이 O(1) 만에 구할 수 있다.
x = [15/9]*9 = 9 (9의 배수 중 15이하인 가장 큰 정수를 생각하면 된다.)
y = [18/8]*8 = 16 (8의 배수 중 18이하인 가장 큰 정수를 생각하면 된다.)

따라서 ab의 약수를 빠르게 찾을 수 있다면 문제를 해결할 수 있다. 

a, b 약수를 따로따로 구하고(각각 O(a½), O(b ½)) 그 약수들을 곱하는 방식으로 ab의 약수를 찾아내자. 
(n의 약수를 구하는 알고리즘은 O(n½) 이지만 약수의 개수는 O(n⅓)이라는 사실을 이용해서 문제를 해결한다.)

 

F

방법 1 - O(N)

문제를 푸는데 필요한 중요한 관찰은 다음과 같다.

길이가 1인 sebsegment에서 mex > med 이다 iff segment가 0을 포함한다.
길이가 2인 sebsegment에서 mex > med 이다 iff segment가 0을 포함한다.
길이가 3인 sebsegment에서 mex > med 이다 iff segment가 0, 1을 포함한다.
길이가 4인 sebsegment에서 mex > med 이다 iff segment가 0, 1을 포함한다.
길이가 5인 sebsegment에서 mex > med 이다 iff segment가 0, 1, 2을 포함한다.
길이가 6인 sebsegment에서 mex > med 이다 iff segment가 0, 1, 2을 포함한다.
길이가 7인 sebsegment에서 mex > med 이다 iff segment가 0, 1, 2, 3을 포함한다.
...
길이가 k인 sebsegment에서 mex > med 이다 iff segment가 0, 1, ... [(k-1)/2]을 포함한다.

예를 들어 다음 배열에서 문제를 해결해보자. subsegment의 길이로 경우를 나누어 구한다.
[3 7 2 6 0 1 5 4]

i) 길이가 1
이 경우는 0 만을 포함하면 된다. 따라서 조건을 만족하는 subsegment는 [0] 하나이다.

ii) 길이가 2
이 경우는 0 만을 포함하면 된다. 따라서 조건을 만족하는 subsegment는 [6 0], [0, 1] 두 개이다.

iii) 길이가 3
이 경우는 0, 1을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 3인 subsegment는 [6 0 1], [0 1 5] 두 개이다.

iv) 길이가 4
이 경우는 0, 1을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 4인 subsegment는 [2 6 0 1], [6 0 1 5], [0 1 5 4] 세 개이다.

v) 길이가 5
이 경우는 0, 1, 2을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 5인 subsegment는 [7 2 6 0 1], [2 6 0 1 5] 두 개이다.

vi) 길이가 6
이 경우는 0, 1, 2을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 6인 subsegment는 [3 7 2 6 0 1], [7 2 6 0 1 5], [2 6 0 1 5 4] 세 개이다.

vii) 길이가 7
이 경우는 0, 1, 2, 3을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 7인 subsegment는 [3 7 2 6 0 1 5] 한 개이다.

viii) 길이가 8
이 경우는 0, 1, 2, 3을 포함하면 된다. subsegment에서 반드시 포함해야하는 원소들을 형광색을 칠하면 다음과 같다. 
[3 7 2 6 0 1 5 4]
형광색 원소들을 포함하면서 길이가 8인 subsegment는 [3 7 2 6 0 1 5 4] 한 개이다.

 

방법 2 - O(N)