티스토리 뷰
https://codeforces.com/contest/1284
한국인이라서 문제 안 읽고 예제만 본 다음에 풀었다. ㅋㅋㅋ
$A_{(y-1) \mod n} + B_{(y-1) \mod m}$을 출력하면 된다.
B. New Year and Ascent Sequence
Ascent가 없는 수열들을 개수를 세면 더 쉽다. 수열 자체에 Ascent가 있는 수열은 걸러내고, Ascent가 없다면 그 수열은 최댓값과 최솟값만 중요하다는 것을 알 수 있다. $\min s_i \geq \max s_j$인 (i, j) 쌍의 수를 세면 되는데, 이는 부분합 배열을 사용하면 해결할 수 있다.
[l, l+c]를 수의 범위로 가지는 framed segment의 개수를 세면 된다.
c를 고정하면, 이때 framed segment의 개수는 $c! \times (N-c+1) \times (N-c+1) \times (N-c)!$이다. 이 값을 모든 c에 대해 계산하여 합하면 답이다.
먼저 좌표압축을 해주고 시작하자.
관찰을 조금 해 보면, 크기가 2인 Conference 집합들이 venue-sensitive한지만 고려해도 충분함을 알 수 있다. 또 venue A에서 겹치고 venue B에서 안 겹치는 venue-sensitive 집합이 존재하는지만 판별해도 충분하다. venue A와 venue B 시간을 swap한 뒤에 같은 문제를 한 번 더 해결하면 되기 때문이다.
venue A에서 시간 x를 포함하는 Conference들의 집합 S를 생각해 보자. S에 속한 Conference들은 venue A에서 개최된다면 어떤 두 Conference를 골라도 시간 x에서 겹치게 되므로, venue B에서 어떤 두 Conference를 골랐을 때, 서로 겹치지 않는다면 이 두 Conference들을 골랐을 때 venue-sensitive하다. 반대로 venue B에서 어떤 두 Conference를 골랐을 때 항상 겹친다면, 어떤 시간 y가 있어서 모든 Conference들이 시간 y를 포함한다는 것을 알 수 있다.
이 관찰을 통해서 세그먼트 트리를 사용한 풀이를 생각할 수 있다. x를 1부터 좌표압축한 범위까지 옮기면서 집합 S가 venue B에서 어떻게 나타나는지를 관리할 것이다. 이렇게 하면 venue B에서의 시간 구간이 생기는 쿼리와 사라지는 쿼리를 수행해야 하는데, 세그먼트 트리에 +1해서 추가 쿼리를 처리하고, -1해서 삭제 쿼리를 처리할 수 있다. 이렇게 하면 세그먼트 트리의 최댓값이 S의 크기와 같으면, 시간 y가 존재한다는 말이 된다. 모든 x에 대해 시간 y가 존재한다면 답은 YES가 된다. 아니면 NO다.
E. New Year and Castle Construction
f(p)의 값을 직접 계산하여 답을 구하는 알고리즘을 사용할 것이다. p가 고정되어 있을 때, 가능한 사각형 집합은 $_{N}C_{4}$개이다. 이 중 조건을 만족하지 않는 사각형 집합을 세면, f(p)를 구할 수 있다. 이 때 조건을 만족하지 않는 사각형은, p를 지나는 직선 $l$에 대해 사각형 점 집합이 $l$의 한쪽에 몰려있도록 하는 $l$이 존재한다. 이제 p에 대해 나머지 점들을 각도정렬하고, 투포인터를 사용하면 쉽게 이런 사각형 집합의 수를 셀 수 있다.
처음에 사각형에 대해 사각형 안에 포함된 점의 수를 합치는 방식으로 접근해서 말렸고, 대회 시간이 끝나기 10분 전에 풀이를 생각했지만 구현을 마치지 못하고 대회가 끝났다. 문제에 주어진 대로 점에 대해서 풀었으면 쉬웠을텐데 ㅠㅠ
F. New Year and Social Network
나중에 풀어봐야지
G. Seollal
Matroid intersection이라고 한다. 모름
E까지 빨리 풀었으면 레드 갈 수 있었을텐데 아쉽다.